检索结果-内蒙古大学图书馆

A Prescriptive Machine Learning Approach to mixed-integer Convex optimization

INFORMS JOURNAL ON COMPUTING 2023年第6期35卷 1225-1241页

作者： Bertsimas, Dimitris Kim, Cheol Woo MIT Sloan Sch Management Cambridge MA 02139 USA MIT Operat Res Ctr Cambridge MA 02139 USA

We introduce a prescriptive machine learning approach to speed up the process of solving mixed-integer convex optimization (MICO) problems. We solve multiple optimization instances and train a machine learning model in advance, which we use to solve new instances. Previous works have shown that the predictions of classification algorithms enable us to solve optimization problems much faster than commercial solvers. What distinguishes this paper from the previous work is that we use a prescriptive algorithm, Optimal Policy Trees (OPT), instead of classification algorithms. Whereas classification algorithms aim to predict the correct label and consider all other labels equally undesirable, a prescriptive approach takes into account all the available decision options and their counterfactuals. We first introduce an algorithm that is purely based on OPT and also its extension. We compare their performance with Optimal Classification Trees (OCT) on various tion, facility location, and hybrid vehicle control. We also experiment on real-world instances taken from the mixed integer Programming Library. OPT-based methods have a significant edge on finding feasible solutions, whereas OCT-based methods have a slight edge on the degree of suboptimality. The proposed extension of the pure OPT algorithm improves on the suboptimality of the solutions the algorithm produces.

关键词： mixed-integer optimization prescriptive analytics artificial intelligence decision trees computational methods

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems

引用

COMPUTATIONAL optimization AND APPLICATIONS 2020年第2期75卷 493-513页

作者： Kobayashi, Ken Takano, Yuich Fujitsu Labs LTD. Artificial Intelligence LabNakahara-ku 4-1-1 Kamikodanaka Kawasaki Kanagawa 2118588 Japan Univ Tsukuba Fac Engn Informat Syst 1-1-1 Tennodai Tsukuba Shi Ibaraki 3058577 Japan

We consider a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite (psd) constraint is relaxed, and the resultant mixed-integer linear optimization problem is solved repeatedly, imposing at each iteration a valid inequality for the psd constraint. We prove the convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added during a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problem: random instances, computing restricted isometry constants, and robust truss topology design. Our experimental results demonstrate that, for many problem instances, our branch-and-cut algorithm delivered superior performance compared with general-purpose MISDO solvers in terms of computational efficiency and stability.

关键词： mixed-integer optimization Semidefinite optimization Cutting-plane algorithm Branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Binary decision rules for multistage adaptive mixed-integer optimization

引用

MATHEMATICAL PROGRAMMING 2018年第2期167卷 395-433页

作者： Bertsimas, Dimitris Georghiou, Angelos MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA MIT Ctr Operat Res 77 Massachusetts Ave Cambridge MA 02139 USA McGill Univ Desautels Fac Management Montreal PQ H3A 1G5 Canada

Decision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameterised binary decision rule structure and derive the exact reformulation of the decision rule problem. In the cases where the resulting optimization problem grows exponentially with respect to the problem data, we provide a systematic methodology that trades-off scalability and optimality, resulting to practical binary decision rules. We also apply the proposed binary decision rules to the class of problems with random-recourse and show that they share similar complexity as the fixed-recourse problems. Our numerical results demonstrate the effectiveness of the proposed binary decision rules and show that they are (i) highly scalable and (ii) provide high quality solutions.

关键词： Adaptive optimization Binary decision rules mixed-integer optimization

来源：评论

学校读者我要写书评

暂无评论

Towards simulation based mixed-integer optimization with differential equations

引用

NETWORKS 2018年第1期72卷 60-83页

作者： Gugat, Martin Leugering, Guenter Martin, Alexander Schmidt, Martin Sirvent, Mathias Wintergerst, David Friedrich Alexander Univ Erlangen Nurnberg FAU Lehrstuhl Angew Math 2 D-91058 Erlangen Germany Friedrich Alexander Univ Erlangen Nurnberg FAU Discrete Optimizat D-91058 Erlangen Germany Energie Campus Nurnberg D-90429 Nurnberg Germany

We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with black-box nonlinearities, where the latter, for example, may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinear equalities. The latter yield nonconvex feasible sets for the optimization model but we have to restrict ourselves to convex and monotone constraint functions. Under these assumptions, we prove that our algorithm finitely terminates with a global optimal solution of the mixed-integer nonlinear problem. Additionally, we show the applicability of our approach for three applications from optimal control with integer variables, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter we also present promising numerical results of our method applied to real-world instances that particularly show the effectiveness of our method for problems defined on networks.

关键词： decomposition method gas transport networks mixed-integer optimization optimization with differential equations simulation based optimization

来源：评论

学校读者我要写书评

暂无评论

Genetic Algorithm Designed for Solving Linear or Nonlinear mixed-integer Constrained optimization Problems

Genetic Algorithm Designed for Solving Linear or Nonlinear M...

引用

International Conference on Advances in Soft Computing, Intelligent Systems and Applications (ASISA)

作者： Jalota, Hemant Thakur, Manoj Indian Inst Technol Mandi Mandi 175001 Himachal Prades India

ISBN: (纸本)9789811052729;9789811052712

Genetic algorithms (GA) initially were not developed to handle the integer restriction or discrete values to the design variables. In the recent years, researchers has focused their work on developing/modifying GAs for handling integer/discrete variables. We have modified the BEX-PM algorithm developed by Thakur et al. [1] to solve the nonlinear constrained mixed-integer optimization problems. Twenty test problems have been used to conduct a comparative study to test the effectiveness of proposed algorithm (MI-BEXPM) with other similar algorithms (viz. MILXPM, RST2ANU, and AXNUM) in this class available in the literature. The efficacy of the results acquired through MI-BEXPM is compared with other algorithms on two well-known criteria. The performance of MI-BEXPM is also analysed and compared for solving real-life mixed-integer optimization problems with other methods available in the literature. It is found that MI-BEXPM is significantly superior to the algorithms considered in this work.

关键词： Real-coded genetic algorithms Bounded exponential crossover Power mutation mixed-integer optimization Constraint optimization

来源：评论

学校读者我要写书评

暂无评论

mixed-integer optimization Problems with Applications to Manufacturing Scheduling and Distributed Energy System Operation

Mixed-Integer Optimization Problems with Applications to Man...

引用

作者： Yan, Bing University of Connecticut

学位级别：Ph.D., Doctor of Philosophy

Over the past decades, mixed-integer optimization problems have attracted a lot attentions. Two popular topics are the scheduling problems of semiconductor manufacturing, and operation problems of distributed energy systems. On the one hand, the increasing pressure to meet demand is forcing semiconductor manufacturers to seek efficient scheduling methods. On the other hand, with world’s increasing energy demand and growing environmental concerns, efficient utilization of energy is essential. Lithography, with a limited number of expensive resources, is a major bottleneck in memory chip manufacturing. Because of its complex characteristics and large sizes of practical problems, developing effective scheduling approaches is challenging. In this thesis, a mixed-integer linear formulation is established for high-volume and low-variety manufacturing through novel resource-based modeling instead of traditional lot-based. To solve this problem efficiently by branch-and-cut, a two-phase approach is established based on convex hull *** solution methodology for litho machine scheduling can also be used for other mixed-integer linear problems such as distributed energy system (DES) operation. Energy demands and energy supplied by different devices are characterized by different levels of quality, which is measured by exergy in thermodynamics. Exergy is destroyed in various processes, with limited amount of exergy in fossil fuels, it is therefore important to match demand and supply in quantity and quality to avoid exergy waste. Flexible DESs provide a desirable infrastructure. An exergy-based optimization approach is therefore developed for DES operation to reduce energy costs and the exergy losses by considering the whole energy supply chain from energy resources to user demands. To capture the complicated interactions among energy devices and capture the exergy loss of each energy device, exergy networks are established with detailed device and water network models.

关键词： mixed-integer optimization semiconductor manufacturing scheduling exergy loss distributed energy system microgrid operation design branch-and-cut convex hull Surrogate Lagrangian relaxation

来源：评论

学校读者我要写书评

暂无评论

MISO: mixed-integer surrogate optimization framework

引用

optimization AND ENGINEERING 2016年第1期17卷 177-203页

作者： Mueller, Juliane Univ Calif Berkeley Lawrence Berkeley Natl Lab Ctr Computat Sci & Engn Berkeley CA 94720 USA

We introduce MISO, the mixed-integer surrogate optimization framework. MISO aims at solving computationally expensive black-box optimization problems with mixed-integer variables. This type of optimization problem is encountered in many applications for which time consuming simulation codes must be run in order to obtain an objective function value. Examples include optimal reliability design and structural optimization. A single objective function evaluation may take from several minutes to hours or even days. Thus, only very few objective function evaluations are allowable during the optimization. The development of algorithms for this type of optimization problems has, however, rarely been addressed in the literature. Because the objective function is black-box, derivatives are not available and numerically approximating the derivatives requires a prohibitively large number of function evaluations. Therefore, we use computationally cheap surrogate models to approximate the expensive objective function and to decide at which points in the variable domain the expensive objective function should be evaluated. We develop a general surrogate model framework and show how sampling strategies of well-known surrogate model algorithms for continuous optimization can be modified for mixed-integer variables. We introduce two new algorithms that combine different sampling strategies and local search to obtain high-accuracy solutions. We compare MISO in numerical experiments to a genetic algorithm, NOMAD version 3.6.2, and SO-MI. The results show that MISO is in general more efficient than NOMAD and the genetic algorithm with respect to finding improved solutions within a limited budget of allowable evaluations. The performance of MISO depends on the chosen sampling strategy. The MISO algorithm that combines a coordinate perturbation search with a target value strategy and a local search performs best among all algorithms.

关键词： mixed-integer optimization Surrogate models Black-box optimization Radial basis functions Derivative-free Global optimization

来源：评论

学校读者我要写书评

暂无评论

Design of Near Optimal Decision Rules in Multistage Adaptive mixed-integer optimization

引用

OPERATIONS RESEARCH 2015年第3期63卷 610-627页

作者： Bertsimas, Dimitris Georghiou, Angelos MIT Sloan Sch Management Cambridge MA 02139 USA MIT Ctr Operat Res Cambridge MA 02139 USA Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland

In recent years, decision rules have been established as the preferred solution method for addressing computationally demanding, multistage adaptive optimization problems. Despite their success, existing decision rules (a) are typically constrained by their a priori design and (b) do not incorporate in their modeling adaptive binary decisions. To address these problems, we first derive the structure for optimal decision rules involving continuous and binary variables as piecewise linear and piecewise constant functions, respectively. We then propose a methodology for the optimal design of such decision rules that have a finite number of pieces and solve the problem robustly using mixed-integer optimization. We demonstrate the effectiveness of the proposed methods in the context of two multistage inventory control problems. We provide global lower bounds and show that our approach is (i) practically tractable and (ii) provides high quality solutions that outperform alternative methods.

关键词： adaptive optimization decision rules mixed-integer optimization

来源：评论

学校读者我要写书评

暂无评论

A Solver for Multiobjective mixed-integer Convex and Nonconvex optimization

引用

JOURNAL OF optimization THEORY AND APPLICATIONS 2024年第2期203卷 1736-1766页

作者： Eichfelder, Gabriele Stein, Oliver Warnow, Leo Tech Univ Ilmenau Inst Math Po 100565 D-98684 Ilmenau Germany Karlsruhe Inst Technol KIT Inst Operat Res D-76128 Karlsruhe Germany

This paper proposes a general framework for solving multiobjective nonconvex optimization problems, i.e., optimization problems in which multiple objective functions have to be optimized simultaneously. Thereby, the nonconvexity might come from the objective or constraint functions, or from integrality conditions for some of the variables. In particular, multiobjective mixed-integer convex and nonconvex optimization problems are covered and form the motivation of our studies. The presented algorithm is based on a branch-and-bound method in the pre-image space, a technique which was already successfully applied for continuous nonconvex multiobjective optimization. However, extending this method to the mixed-integer setting is not straightforward, in particular with regard to convergence results. More precisely, new branching rules and lower bounding procedures are needed to obtain an algorithm that is practically applicable and convergent for multiobjective mixed-integer optimization problems. Corresponding results are a main contribution of this paper. What is more, for improving the performance of this new branch-and-bound method we enhance it with two types of cuts in the image space which are based on ideas from multiobjective mixed-integer convex optimization. Those combine continuous convex relaxations with adaptive cuts for the convex hull of the mixed-integer image set, derived from supporting hyperplanes to the relaxed sets. Based on the above ingredients, the paper provides a new multiobjective mixed-integer solver for convex problems with a stopping criterion purely in the image space. What is more, for the first time a solver for multiobjective mixed-integer nonconvex optimization is presented. We provide the results of numerical tests for the new algorithm. Where possible, we compare it with existing procedures.

关键词： Branch-and-bound Branch-and-cut Multiobjective optimization mixed-integer optimization Nonconvex optimization Box enclosure

来源：评论

学校读者我要写书评

暂无评论

A mixed-integer approximation of robust optimization problems with mixed-integer adjustments

引用

optimization AND ENGINEERING 2024年第3期25卷 1271-1296页

作者： Kronqvist, Jan Li, Boda Rolfes, Jan KTH Royal Inst Technol Dept Math Lindtstedtsvagen 25 S-10044 Stockholm Sweden ABB Corp Res Ctr Wallstadter Str 59 D-68526 Ladenburg Germany

In the present article we propose a mixed-integer approximation of adjustable-robust optimization problems, that have both, continuous and discrete variables on the lowest level. As these trilevel problems are notoriously hard to solve, we restrict ourselves to weakly-connected instances. Our approach allows us to approximate, and in some cases exactly represent, the trilevel problem as a single-level mixed-integer problem. This allows us to leverage the computational efficiency of state-of-the-art mixed-integer programming solvers. We demonstrate the value of this approach by applying it to the optimization of power systems, particularly to the control of smart converters.

关键词： mixed-integer optimization Robust optimization Adjustable Robustness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：