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

Learning Different Separations in Branch and Cut: A Survey 4th

学校读者我要写书评

暂无评论

Learning Different Separations in Branch and Cut: A Survey

4th International Conference on Intelligent Systems and Pattern Recognition, ISPR 2024

作者： Ayachi Amar, Chaima Bouanane, Khadra Aiadi, Oussama LINATI Laboratory Ouargla Algeria University Kasdi Merbah Ouargla Ouargla30000 Algeria

ISBN: (纸本)9783031821554

Selecting cutting planes for solving mixed-integer linear programming (MILP) is a critical task as it directly impacts the efficiency and effectiveness of the optimization process. By carefully choosing a set of cuts, it becomes possible to significantly reduce the size of the search space, thereby enhancing the algorithm’s ability to find optimal or near-optimal solutions within a reasonable computational time frame. In this paper, we examine recent advancements in utilizing Machine Learning (ML) techniques for the selection of cutting planes (separation) in MILP. Despite the existence of various types of separations, the task of selecting a set of cuts to augment the linear programming (LP) relaxation at a particular node of the Branch-and-Bound (B&B) tree remains a challenge, both in terms of formal methods and heuristic approaches. ML presents a promising direction for enhancing the cut selection process by leveraging data to identify promising cuts that expedite the resolution of MILP problems. Focusing on recent developments in research, we investigate common methodologies for data gathering, evaluation techniques, and ML model architectures. We review empirical findings in the literature to assess the extent of progress achieved and conclude by suggesting potential directions for future investigation. In conclusion, the integration of ML techniques holds great promise for advancing the field of MILP by improving the efficiency and effectiveness of cut selection processes, ultimately leading to better solutions for complex optimization problems © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： mixed-integer linear programming

A fast approximate scenario addition method for two-stage robust mixed-integer programs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Goerigk, Marc Henke, Dorothee Kager, Johannes Schäfer, Fabian Thielen, Clemens Business Decisions and Data Science University of Passau Germany Professorship of Optimization and Sustainable Decision Making Campus Straubing for Biotechnology and Sustainability Technical University of Munich Germany Campus Straubing for Biotechnology and Sustainability Technical University of Munich Germany Department of Mathematics School of Computation Information and Technology Technical University of Munich Germany

This paper presents a new scenario addition method for two-stage robust mixed-integer programs with finite uncertainty sets. Our method combines and extends speed-up techniques used in previous scenario addition methods (also called column- and-constraint generation methods) and introduces several new techniques. In particular, it uses dual bounds for second-stage problems in order to allow a faster identification of the next promising scenario to be added to the master problem. Moreover, adaptive time limits are imposed to avoid getting stuck on particularly hard second-stage problems, and a gap propagation between master problem and second-stage problems is used to stop solving them earlier if only a given non-zero optimality gap is to be reached overall. This makes our method particularly effective for problems where solving the second-stage problem is computationally challenging. To evaluate the method’s performance, we compare it to two recent scenario addition methods from the literature on two applications: a robust capacitated location routing problem and a robust integrated berth allocation and quay crane assignment and scheduling problem. The first problem features a particularly hard second stage, and we show that our method is able to solve considerably more and larger instances in a given time limit. Using the second problem, we verify the general applicability of our method, even for problems where the second stage is relatively easy. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Location-Allocation of Relief Service Facilities: A Case Study for Bogotá - Colombia 11th

学校读者我要写书评

暂无评论

Location-Allocation of Relief Service Facilities: A Case S...

11th Workshop on Engineering Applications, WEA 2024

作者： Chacón-Tibaduiza, Natalia Guzmán-Cortés, Diana C. Figueroa-García, Juan Carlos Franco, Carlos School of Engineering Science and Technology Universidad del Rosario Bogotá Colombia Faculty of Engineering Universidad Distrital Francisco José de Caldas Bogotá Colombia School of Management and Business Universidad del Rosario Bogotá Colombia

ISBN: (纸本)9783031745973

Effective resource allocation during natural disasters and response strategies are crucial to mitigate impacts and save lives. This paper presents a comprehensive mathematical model, which is designed to optimize disaster response operations. The proposed model integrates various components, including the demand for different types of relief services, facilities distributed by zones, as well as the assessment of resource requirements, and optimization of the location capacities per zone. We propose the use of mixed-integer linear programming (MILP), where we propose three different objective functions. The model was tested over a real case in Bogotá-Colombia and we evaluate different scenarios to analyze the performance of the model and obtained results. The proposed framework offers a strategic tool for policymakers and emergency managers to enable data-driven decision-making in disaster preparedness and response planning. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： mixed-integer linear programming

Optimal Placement of Nature-Based Solutions for Urban Challenges

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pinto, Diego Maria Russo, Davide Donato Sudoso, Antonio M. Institute for Systems Analysis and Computer Science "Antonio Ruberti" National Research Council Via dei Taurini 19 Rome00185 Italy Department of Computer Control and Management Engineering "Antonio Ruberti" Sapienza University of Rome Via Ariosto 25 Rome00185 Italy

Increased urbanization and climate change intensify urban heat islands and degrade air quality, making current mitigation strategies insufficient. Nature-based solutions (NBSs), such as parks, green walls, roofs, and street trees, offer a promising means to regulate urban temperatures and enhance air quality. However, determining their optimal placement to maximize environmental benefits remains a pressing challenge. Leveraging Operational Research (OR) tools, we propose a mixed-integer linear programming (MILP) model that integrates multiple factors, including urban challenges, physical constraints, clustering techniques, convolution theory, and fairness considerations. This model determines the optimal placement of NBSs by addressing metrics such as ground temperature, air quality, and accessibility to green spaces. Through several case study analyses, we demonstrate the effectiveness of our approach in improving environmental and social indicators. This research holds implications for policy and practice, empowering urban planners and policymakers to make informed decisions regarding NBS implementation. Such decisions ensure that investments in urban greening yield maximum environmental, social, and economic benefits. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

An Efficient mixed-integer Formulation and an Iterative Method for Optimal Control of Switched Systems Under Dwell Time Constraints

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Abbasi-Esfeden, Ramin Nurkanovic, Armin Diehl, Moritz Patrinos, Panagiotis Swevers, Jan Department of Mechanical Engineering KU Leuven Leuven Belgium Department of Mechanical Engineering Flanders Make@KU Leuven Leuven Belgium University of Freiburg Freiburg Germany KU Leuven Leuven Belgium

This paper presents an efficient mixed-integer Nonlinear programming (MINLP) formulation for systems with discrete control inputs under dwell time constraints. By viewing such systems as a switched system, the problem is decomposed into a Sequence Optimization (SO) and a Switching Time Optimization (STO)—the former providing the sequence of the switched system, and the latter calculating the optimal switching times. By limiting the feasible set of SO to subsequences of a master sequence, this formulation requires a small number of binary variables, independent of the number of time discretization nodes. This enables the proposed formulation to provide solutions efficiently, even for large numbers of time discretization nodes. To provide even faster solutions, an iterative algorithm is introduced to heuristically solve STO and SO. The proposed approaches are then showcased on four different switched systems and results demonstrate the efficiency of the MINLP formulation and the iterative algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Chance-Constrained Trajectory Planning with Multimodal Environmental Uncertainty

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ren, Kai Ahn, Heejin Kamgarpour, Maryam ECE Department University of British Columbia VancouverBC Canada ECE Department Seoul National University Korea Republic of Switzerland

We tackle safe trajectory planning under Gaussian mixture model (GMM) uncertainty. Specifically, we use a GMM to model the multimodal behaviors of obstacles’ uncertain states. Then, we develop a mixed-integer conic approximation to the chance-constrained trajectory planning problem with deterministic linear systems and polyhedral obstacles. When the GMM moments are estimated via finite samples, we develop a tight concentration bound to ensure the chance constraint with a desired confidence. Moreover, to limit the amount of constraint violation, we develop a Conditional Value-at-Risk (CVaR) approach corresponding to the chance constraints and derive a tractable approximation for known and estimated GMM moments. We verify our methods with state-of-the-art trajectory prediction algorithms and autonomous driving datasets. © 2025, CC BY.

关键词： mixed-integer linear programming

On a geometric graph-covering problem related to optimal safety-landing-site location

学校读者我要写书评

暂无评论

arXiv 2025年

作者： D’Ambrosio, Claudia Fampa, Marcia Lee, Jon Sinnecker, Felipe Ecole Polytechnique France Universidade Federal do Rio de Janeiro Brazil University of Michigan Ann ArborMI United States

We propose integer-programming formulations for an optimal safety-landing site (SLS) location problem that arises in the design of urban air-transportation networks. We first develop a set-cover based approach for the case where the candidate location set is finite and composed of points, and we link the problems to solvable cases that have been studied. We then use a mixed-integer second-order cone program to model the situation where the locations of SLSs are restricted to convex sets only. Finally, we introduce strong fixing, which we found to be very effective in reducing the size of integer programs. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Certified Inductive Synthesis for Online mixed-integer Optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zamponi, Marco Incerto, Emilio Masti, Daniele Tribastone, Mirco IMT School for Advanced Studies Lucca Italy GSSI Gran Sasso Science Institute L’Aquila Italy

In fields such as autonomous and safety-critical systems, online optimization plays a crucial role in control and decision-making processes, often requiring the integration of continuous and discrete variables. These tasks are frequently modeled as mixed-integer programming (MIP) problems, where feedback data are incorporated as parameters. However, solving MIPs within strict time constraints is challenging due to their NP-complete nature. A promising solution to this challenge involves leveraging the largely invariant structure of these problems to perform most computations offline, thus enabling efficient online solving even on platforms with limited hardware capabilities. In this paper we present a novel implementation of this strategy that uses counterexample-guided inductive synthesis to split the MIP solution process into two stages. In the offline phase, we construct a mapping that provides feasible assignments for binary variables based on parameter values within a specified range. In the online phase, we solve the remaining continuous part of the problem by fixing the binary variables to the values predicted by this mapping. Our numerical evaluation demonstrates the efficiency and solution quality of this approach compared to standard mixed-integer solvers, highlighting its potential for real-time applications in resource-constrained environments. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

IDP FOR 2-PARTITION MAXIMAL SYMMETRIC POLYTOPES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hong, Su Ji Nasr, George D. Department of Applied Mathematics and Statistics Johns Hopkins University United States Department of Mathematics Augustana University United States

We provide a framework for which one can approach showing the integer decomposition property for symmetric polytopes. We utilize this framework to prove a special case which we refer to as 2-partition maximal polytopes in the case where it lies in a hyperplane of R3. Our method involves proving a special collection of polynomials have saturated Newton *** Codes 52B05, 52B15 © 2025, CC BY.

关键词： mixed-integer linear programming