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

Learning to select cuts for efficient mixed-integer programming

PATTERN RECOGNITION 2022年 123卷 108353-108353页

作者： Huang, Zeren Wang, Kerong Liu, Furui Zhen, Hui-Ling Zhang, Weinan Yuan, Mingxuan Hao, Jianye Yu, Yong Wang, Jun Shanghai Jiao Tong Univ Shanghai Peoples R China UCL London England Huawei Technol Noahs Ark Lab Shenzhen Peoples R China

Cutting plane methods play a significant role in modern solvers for tackling mixed-integer programming (MIP) problems. Proper selection of cuts would remove infeasible solutions in the early stage, thus largely reducing the computational burden without hurting the solution accuracy. However, the major cut selection approaches heavily rely on heuristics, which strongly depend on the specific problem at hand and thus limit their generalization capability. In this paper, we propose a data-driven and generalizable cut selection approach, named CUT RANKING , in the settings of multiple instance learning. To measure the quality of the candidate cuts, a scoring function, which takes the instance-specific cut features as inputs, is trained and applied in cut ranking and selection. In order to evaluate our method, we conduct extensive experiments on both synthetic datasets and real-world datasets. Compared with commonly used heuristics for cut selection, the learning-based policy has shown to be more effective, and is capable of generalizing over multiple problems with different properties. CUT RANKING has been deployed in an industrial solver for large-scale MIPs. In the online A/B testing of the product planning problems with more than 10 7 variables and constraints daily, CUT RANKING has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： mixed-integer programming Cutting plane Multiple instance learning Generalization ability

来源：评论

学校读者我要写书评

暂无评论

Data Mining Approach for Feature Based Parameter Tunning for mixed-integer programming Solvers

引用

Procedia Computer Science 2017年 108卷 715-724页

作者： Matheus G. Vilas Boas Haroldo G. Santos Rafael de S.O. Martins Luiz H.C. Merschmann Federal University of Ouro Preto Department of Computing Ouro Preto Brazil Federal University of Ouro Preto Department of Information Systems and Computing João Monlevade Brazil Federal University of Lavras Department of Computer Science Lavras Brazil

integer programming (IP) is the most successful technique for solving hard combinatorial optimization problems. Modern IP solvers are very complex programs composed of many different procedures whose execution is embedded in the generic Branch & Bound framework. The activation of these procedures as well the definition of exploration strategies for the search tree can be done by setting different parameters. Since the success of these procedures and strategies in improving the performance of IP solvers varies widely depending on the problem being solved, the usual approach for discovering a good set of parameters considering average results is not ideal. In this work we propose a comprehensive approach for the automatic tuning of integer programming solvers where the characteristics of instances are considered. Computational experiments in a diverse set of 308 benchmark instances using the open source COIN-OR CBC solver were performed with different parameter sets and the results were processed by data mining algorithms. The results were encouraging: when trained with a portion of the database the algorithms were able to predict better parameters for the remaining instances in 84% of the cases. The selection of a single best parameter setting would provide an improvement in only 56% of instances, showing that great improvements can be obtained with our approach.

关键词： feature based parameter tunning mixed-integer programming data mining regression algorithms coin-or branch cut

来源：评论

学校读者我要写书评

暂无评论

Economical sizing and multi-azimuth layout optimization of grid-connected rooftop photovoltaic systems using mixed-integer programming

引用

APPLIED ENERGY 2023年第1期335卷

作者： Alharbi, Abdulaziz Awwad, Zeyad Habib, Abdulelah de Weck, Olivier MIT Ctr Complex Engn Syst KACST Riyadh Saudi Arabia MIT Dept Aeronaut & Astronaut Cambridge MA 02139 USA

Solar energy is expected to be a significant contributor to meet the increasing global energy demand. Rooftop photovoltaic (PV) systems account for a substantial portion of the global solar energy potential. However, optimizing the size and layout of these systems remains challenging. Existing approaches either focus on maximizing energy generation, heavily restrict the space of potential layouts, ignore inverter-type implications, or neglect practical aspects, such as minimizing self-shading. This paper presents a mixed-integer programming (MIP) model to address these limitations for PV systems installed on flat rooftops. The proposed model optimizes the net present value (NPV) and can produce multi-azimuth layouts while accounting for practical considerations, including mitigating self-shading, and ensuring rooftop walkability. The proposed model is adapted for systems that utilize micro-inverters or string-inverters. Two case studies are conducted to evaluate the performance of the proposed model. In one case study, the model is applied to a residential area. It is numerically shown that in some instances of capital costs and billing policies, the use of multi-azimuth layouts could significantly improve the NPV compared to the use of single-azimuth layouts with parallel rows of panels. The proposed model solutions are compared to an existing optimized installation in the second case study. The proposed model multi-azimuth layout solution improves the NPV by 10.17%. When restricted to single-azimuth layouts, the proposed model produces the same design as that of the existing installation in only a few seconds.

关键词： Optimization mixed-integer programming Photovoltaic system sizing optimization Photovoltaic system layout optimization

来源：评论

学校读者我要写书评

暂无评论

Optimal Operational Planning of a Gas Turbine Combined Heat and Power Plant Based on the mixed-integer programming

引用

IFAC Proceedings Volumes 1988年第11期21卷 371-377页

作者： K. Ito R. Yokoyama S. Akagi T. Yamaguchi Y. Matsumoto Dept. of Mech. Eng. for Indu. Mach and Syst. Faculty of Eng. Osaka Univ. Suita Osaka Japan Technical Research Center. The Kansai Electric Power Co. Inc. Amagasaki Hyogo Japan

A planning method is proposed for determining the optimal operational policy of a gas turbine combined heat and power plant connected with distributed heat supply plants at several districts. For the purpose of the efficient planning, a hierarchical approach is adopted. At the first level, the optimal operational policy is determined for each heat supply plant so as to minimize the required amount of input energy. At the second level, the optimal operational policy is determined for the combined heat and power plant so as to minimize its operational cost. These optimization problems are formulated respectively as a mixed-integer quadratic programming problem and a mixed-integer linear one, and they are both solved by applying the branch and bound method. Lastly, the effectiveness of the proposed method is ascertained through a case study.

关键词： Computer-aided systet design power generation heat systems gas turbines optimization hierarchical systems district heating and cooling optimal operation mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

A Survey on mixed-integer programming Techniques in Bilevel Optimization

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2021年 9卷

作者： Kleinert, Thomas Labbe, Martine Ljubic, Ivana Schmidt, Martin Friedrich Alexander Univ Erlangen Nurnberg Discrete Optimizat Cauerstr 11 D-91058 Erlangen Germany Energie Campus Nurnberg Further Str 250 D-90429 Nurnberg Germany Univ Libre Bruxelles Dept Comp Sci Blvd TriompheCP212 B-1050 Brussels Belgium Inria Lille Nord Europe Parc Sci Haute Borne 40Av Halley Bat APk Plaza F-59650 Villeneuve Dascq France ESSEC Business Sch Paris F-95021 Cergy Pontoise France Trier Univ Dept Math Univ Ring 15 D-54296 Trier Germany

Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and practice. The scientific interest in computational bilevel optimization increased a lot over the last decade and is still growing. Independent of whether the bilevel problem itself contains integer variables or not, many state-of-the-art solution approaches for bilevel optimization make use of techniques that originate from mixed-integer programming. These techniques include branch-and-bound methods, cutting planes and, thus, branch-and-cut approaches, or problem-specific decomposition methods. In this survey article, we review bilevel-tailored approaches that exploit these mixed-integer programming techniques to solve bilevel optimization problems. To this end, we first consider bilevel problems with convex or, in particular, linear lower-level problems. The discussed solution methods in this field stem from original works from the 1980's but, on the other hand, are still actively researched today. Second, we review modern algorithmic approaches to solve mixed-integer bilevel problems that contain integrality constraints in the lower level. Moreover, we also briefly discuss the area of mixed-integer nonlinear bilevel problems. Third, we devote some attention to more specific fields such as pricing or interdiction models that genuinely contain bilinear and thus nonconvex aspects. Finally, we sketch a list of open questions from the areas of algorithmic and computational bilevel optimization, which may lead to interesting future research that will further propel this fascinating and active field of research.

关键词： Bilevel optimization mixed-integer programming Applications Branch-and-bound Branch-and-cut Survey

来源：评论

学校读者我要写书评

暂无评论

Research on obstetric ward planning combining lean thinking and mixed-integer programming

引用

INTERNATIONAL JOURNAL FOR QUALITY IN HEALTH CARE 2021年第3期33卷 mzab101-mzab101页

作者： Mu, Dongmei Li, Hua Zhao, Danning Ju, Yuanhong Li, Yuewei Jilin Univ Sch Publ Hlth 1163 Xinmin St Changchun 130000 Jilin Peoples R China Jilin Univ First Hosp Dept Clin Res 1 Xinmin St Changchun 130000 Jilin Peoples R China Jilin Univ First Hosp Dept Abdominal Ultrasound 1 Xinmin St Changchun 130000 Jilin Peoples R China Jilin Univ Sch Nursing 965 Xinjiang St Changchun 130000 Jilin Peoples R China

Background: In recent years, there are many studies on scheduling methods of patient flow, nurse scheduling, bed allocation, operating room scheduling and other problems, but there is no report on the research methods of how to plan ward allocation from a more macroscopic perspective. Objective: Refine and stratify the obstetric ward to provide more accurate medical service for pregnant women and improve the work efficiency of obstetricians and midwives. The problem of how to allocate the number of each type of ward is modeled as a mixed integer programming problem, which maximizes the patient flow of pregnant women in obstetric hospitals. Methods: The obstetric wards are divided into observation ward, cesarean section ward and natural delivery ward according to lean thinking. CPLEX is used to solve the mixed-integer programming problem of ward allocation. In R software, multivariate Generalized Linear Models (GLM) regression model is used to analyze the influence of each factor on patient flow. Results: The maximum patient flow of each case was obtained by CPLEX, which was 19-25% higher than that of patients without refinement, stratification and planning. GLM regression analysis was carried out on the abovementioned data, and the positive and negative correlation factors were obtained. Conclusion: According to lean thinking, obstetric wards are divided into three types of wards. Obstetricians and midwives work more efficiently and get more rest time. Pregnant women also enjoy more detailed medical services. By modeling the delivery ward allocation problem as a mixed-integer programming problem, we can improve the capacity of the service in obstetric hospitals from a macro perspective. Through GLM regression model analysis, it is conducive to improve the obstetric hospital capacity from the perspective of positive and negative correlation factors.

关键词： obstetric ward planning lean thinking mixed-integer programming clinical pathway CPLEX

来源：评论

学校读者我要写书评

暂无评论

Branch-and-Bound for Biobjective mixed-integer Linear programming

引用

INFORMS JOURNAL ON COMPUTING 2022年第2期34卷 909-933页

作者： Adelgren, Nathan Gupte, Akshay Edinboro Univ Dept Math & Comp Sci Edinboro PA 16444 USA Princeton Univ Andlinger Ctr Energy & Environm Princeton NJ 08544 USA Univ Edinburgh Sch Math Edinburgh EH9 3FD Midlothian Scotland

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and

关键词： branch-and-bound mixed-integer programming multiobjective optimization Pareto optima fathoming rules

来源：评论

学校读者我要写书评

暂无评论

SelfSplit parallelization for mixed-integer linear programming

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 93卷 101-112页

作者： Fischetti, Matteo Monaci, Michele Salvagnin, Domenico Univ Padua DEI Padua Italy Univ Bologna DEI Bologna Italy

SelfSplit is a simple static mechanism to convert a sequential tree-search code into a parallel one. In this paradigm, tree-search is distributed among a set of identical workers, each of which is able to autonomously determine-without any communication with the other workers-the job parts it has to process. SelfSplit already proved quite effective in parallelizing Constraint programming solvers. In the present paper we investigate the performance of SelfSplit when applied to a mixed-integer Linear programming (MILP) solver. Both ad-hoc and general purpose MILP codes have been considered. Computational results show that SelfSplit, in spite of its simplicity, can achieve good speedups even in the MILP context. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Parallel computing Enumerative algorithms mixed-integer programming Computational analysis

来源：评论

学校读者我要写书评

暂无评论

Area aggregation in map generalisation by mixed-integer programming

引用

INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE 2010年第12期24卷 1871-1897页

作者： Haunert, Jan-Henrik Wolff, Alexander Leibniz Univ Hannover Inst Kartog & Geoinformat Hannover Germany Tech Univ Eindhoven Fac Wiskunde Informat NL-5600 MB Eindhoven Netherlands

Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.

关键词： map generalisation aggregation combinatorial optimisation mixed-integer programming NP-hardness

来源：评论

学校读者我要写书评

暂无评论

mixed-integer linear programming for scheduling unconventional oil field development

引用

OPTIMIZATION AND ENGINEERING 2021年第3期22卷 1459-1489页

作者： Soni, Akhilesh Linderoth, Jeff Luedtke, James Rigterink, Fabian Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA ExxonMobil Upstream Integrated Solut Irving TX USA

The scheduling of drilling and hydraulic fracturing of wells in an unconventional oil field plays an important role in the profitability of the field. A key challenge arising in this problem is the requirement that neither drilling nor oil production can be done at wells within a specified neighborhood of a well being fractured. We propose a novel mixed-integer linear programming (MILP) formulation for determining a schedule for drilling and fracturing wells in an unconventional oil field. We also derive an alternative formulation which provides stronger relaxations. In order to apply the MILP model for scheduling large fields, we derive a rolling horizon approach that solves a sequence of coarse time-scale MILP instances to obtain a solution at the daily time scale. We benchmark our MILP-based rolling horizon approach against a baseline scheduling algorithm in which wells are developed in the order of their discounted production revenue. Our experiments on synthetically generated instances demonstrate that our MILP-based rolling horizon approach can improve profitability of a field by 4-6%.

关键词： mixed-integer programming Rolling horizon Production scheduling Shale oil Hydraulic fracturing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：