18 results on '"Gleixner, Ambros"'
Search Results
2. Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework
- Author
-
Eifler, Leon and Gleixner, Ambros
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,65K05, 90C11, 90-08 ,Mathematics - Optimization and Control - Abstract
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. more...
- Published
- 2023
Catalog
3. Online Learning for Scheduling MIP Heuristics
- Author
-
Chmiela, Antonia, Gleixner, Ambros, Lichocki, Pawel, and Pokutta, Sebastian
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control ,Machine Learning (cs.LG) - Abstract
Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%., Comment: Published in the Proceedings of CPAIOR 2023 more...
- Published
- 2023
- Full Text
- View/download PDF
4. Enabling Research through the SCIP Optimization Suite 8.0
- Author
-
Bestuzheva, Ksenia, Besançon, Mathieu, Chen, Wei-Kun, Chmiela, Antonia, Donkiewicz, Tim, van Doornmalen, Jasper, Eifler, Leon, Gaul, Oliver, Gamrath, Gerald, Gleixner, Ambros, Gottwald, Leona, Graczyk, Christoph, Halbig, Katrin, Hoen, Alexander, Hojny, Christopher, van der Hulst, Rolf, Koch, Thorsten, Lübbecke, Marco, Maher, Stephen J., Matter, Frederic, Mühmer, Erik, Müller, Benjamin, Pfetsch, Marc E., Rehfeldt, Daniel, Schlein, Steffan, Schlösser, Franziska, Serrano, Felipe, Shinano, Yuji, Sofranac, Boro, Turner, Mark, Vigerske, Stefan, Wegscheider, Fabian, Wellner, Philipp, Weninger, Dieter, and Witzig, Jakob more...
- Subjects
90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control - Abstract
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this paper is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Further, the paper gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP., Comment: arXiv admin note: substantial text overlap with arXiv:2112.08872 more...
- Published
- 2023
- Full Text
- View/download PDF
5. Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
- Author
-
Bestuzheva, Ksenia, Völker, Helena, and Gleixner, Ambros
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control ,90C23, 90C26, 90C30, 90C57, 90-08, 14-04 - Abstract
Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches., 4 pages, 0 figures, published in proceedings of the Hungarian Global Optimization Workshop HUGO 2022 more...
- Published
- 2022
6. PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support
- Author
-
Gleixner, Ambros, Gottwald, Leona, and Hoen, Alexander
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control - Abstract
Presolving has become an essential component of modern MIP solvers both in terms of computational performance and numerical robustness. In this paper, we present PaPILO, a new C++ header-only library that provides a large set of presolving routines for MIP and LP problems from the literature. The creation of PaPILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware, and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. PaPILO's parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, PaPILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel's TBB library aids PaPILO to efficiently exploit recursive parallelism within expensive presolving routines such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO's capabilities and insights into important design choices. more...
- Published
- 2022
7. The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
- Author
-
Gasse, Maxime, Cappart, Quentin, Charfreitag, Jonas, Charlin, Laurent, Ch��telat, Didier, Chmiela, Antonia, Dumouchelle, Justin, Gleixner, Ambros, Kazachkov, Aleksandr M., Khalil, Elias, Lichocki, Pawel, Lodi, Andrea, Lubin, Miles, Maddison, Chris J., Morris, Christopher, Papageorgiou, Dimitri J., Parjadis, Augustin, Pokutta, Sebastian, Prouvost, Antoine, Scavuzzo, Lara, Zarpellon, Giulia, Yang, Linxin, Lai, Sha, Wang, Akang, Luo, Xiaodong, Zhou, Xiang, Huang, Haohan, Shao, Shengcheng, Zhu, Yuanming, Zhang, Dong, Quan, Tao, Cao, Zixuan, Xu, Yang, Huang, Zhewei, Zhou, Shuchang, Binbin, Chen, Minggui, He, Hao, Hao, Zhiyu, Zhang, Zhiwu, An, and Kun, Mao more...
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Optimization and Control (math.OC) ,Statistics - Machine Learning ,FOS: Mathematics ,Computer Science - Neural and Evolutionary Computing ,Machine Learning (stat.ML) ,Neural and Evolutionary Computing (cs.NE) ,Mathematics - Optimization and Control ,Machine Learning (cs.LG) - Abstract
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning as a new approach for solving combinatorial problems, either directly as solvers or by enhancing exact solvers. Based on this context, the ML4CO aims at improving state-of-the-art combinatorial optimization solvers by replacing key heuristic components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate solver configuration. Three realistic datasets were considered: balanced item placement, workload apportionment, and maritime inventory routing. This last dataset was kept anonymous for the contestants., Neurips 2021 competition. arXiv admin note: text overlap with arXiv:2112.12251 by other authors more...
- Published
- 2022
8. Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
- Author
-
Bestuzheva, Ksenia, Gleixner, Ambros, and Achterberg, Tobias
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,90-08, 90C11, 90C20, 90C26, 90C57 ,Mathematics - Optimization and Control - Abstract
The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods., Comment: 16 pages, 0 figures, submitted to the 24th Conference on Integer Programming and Combinatorial Optimization more...
- Published
- 2022
- Full Text
- View/download PDF
9. The SCIP Optimization Suite 8.0
- Author
-
Bestuzheva, Ksenia, Besan��on, Mathieu, Chen, Wei-Kun, Chmiela, Antonia, Donkiewicz, Tim, van Doornmalen, Jasper, Eifler, Leon, Gaul, Oliver, Gamrath, Gerald, Gleixner, Ambros, Gottwald, Leona, Graczyk, Christoph, Halbig, Katrin, Hoen, Alexander, Hojny, Christopher, van der Hulst, Rolf, Koch, Thorsten, L��bbecke, Marco, Maher, Stephen J., Matter, Frederic, M��hmer, Erik, M��ller, Benjamin, Pfetsch, Marc E., Rehfeldt, Daniel, Schlein, Steffan, Schl��sser, Franziska, Serrano, Felipe, Shinano, Yuji, Sofranac, Boro, Turner, Mark, Vigerske, Stefan, Wegscheider, Fabian, Wellner, Philipp, Weninger, Dieter, and Witzig, Jakob more...
- Subjects
90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control - Abstract
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack., 114 pages, 8 figures more...
- Published
- 2021
10. Learning to Schedule Heuristics in Branch-and-Bound
- Author
-
Chmiela, Antonia, Khalil, Elias B., Gleixner, Ambros, Lodi, Andrea, and Pokutta, Sebastian
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Discrete Mathematics (cs.DM) ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control ,Machine Learning (cs.LG) ,Computer Science - Discrete Mathematics - Abstract
Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances. more...
- Published
- 2021
11. A Computational Study of Perspective Cuts
- Author
-
Bestuzheva, Ksenia, Gleixner, Ambros, and Vigerske, Stefan
- Subjects
G.4 ,90-04, 90-08, 90C11, 90C26, 90C30, 90C57 ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control - Abstract
The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. more...
- Published
- 2021
- Full Text
- View/download PDF
12. First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method
- Author
-
Gleixner, Ambros, Kempke, Nils-Christian, Koch, Thorsten, Rehfeldt, Daniel, and Uslu, Svenja
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,90C05 (Primary), 90C06 (Secondary) ,Mathematics - Optimization and Control - Abstract
In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix., 6 pages, 3 figures, under review (Operations Research Proceedings) more...
- Published
- 2019
13. Conflict-Driven Heuristics for Mixed Integer Programming
- Author
-
Witzig, Jakob and Gleixner, Ambros
- Subjects
Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control - Abstract
Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l. more...
- Published
- 2019
14. A Safe Computational Framework for Integer Programming applied to Chv��tal's Conjecture
- Author
-
Eifler, Leon, Gleixner, Ambros, and Pulaj, Jonad
- Subjects
Optimization and Control (math.OC) ,05-XX COMBINATORICS (For finite fields, see 11Txx), 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING ,FOS: Mathematics ,Combinatorics (math.CO) - Abstract
We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chv��tal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result, we are able to provide a first machine-assisted proof that Chv��tal's conjecture holds for all downsets whose union of sets contains seven elements or less. more...
- Published
- 2018
- Full Text
- View/download PDF
15. Exact Methods for Recursive Circle Packing
- Author
-
Gleixner, Ambros, Maher, Stephen, Müller, Benjamin, and Pedroso, João Pedro
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Optimization and Control (math.OC) ,FOS: Mathematics ,Mathematics - Optimization and Control ,Computer Science - Discrete Mathematics - Abstract
Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig--Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. more...
- Published
- 2017
- Full Text
- View/download PDF
16. Verifying Integer Programming Results
- Author
-
Cheung, Kevin K. H., Gleixner, Ambros, and Steffy, Daniel E.
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Optimization and Control (math.OC) ,FOS: Mathematics ,Computer Science - Mathematical Software ,90C11 ,Mathematical Software (cs.MS) ,Mathematics - Optimization and Control ,Computer Science - Discrete Mathematics - Abstract
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates., Zuse Institute Berlin, Takustr. 7, 14195 Berlin, November 2016, http://nbn-resolving.de/urn:nbn:de:0297-zib-61044 more...
- Published
- 2016
17. Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes
- Author
-
Beckenbach, Isabel, Eifler, Leon, Fackeldey, Konstantin, Gleixner, Ambros, Grever, Andreas, Weber, Marcus, and Witzig, Jakob
- Subjects
FOS: Computer and information sciences ,Optimization and Control (math.OC) ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Data Structures and Algorithms (cs.DS) ,Dynamical Systems (math.DS) ,Mathematics - Dynamical Systems ,60J05, 60J22, 82B30, 90C11, 90C27 ,Mathematics - Optimization and Control - Abstract
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. more...
- Published
- 2016
18. Towards an accurate solution of wireless network design problems
- Author
-
D’andreagiovanni, Fabio, Gleixner, Ambros, Centre National de la Recherche Scientifique (CNRS), Heuristique et Diagnostic des Systèmes Complexes [Compiègne] (Heudiasyc), Université de Technologie de Compiègne (UTC)-Centre National de la Recherche Scientifique (CNRS), and D'Andreagiovanni, Fabio more...
- Subjects
Computer Science - Networking and Internet Architecture ,Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Optimization and Control (math.OC) ,FOS: Mathematics ,[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC] ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Mathematics - Optimization and Control ,ComputingMilieux_MISCELLANEOUS - Abstract
The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models., Comment: This is the authors' final version of the paper published in: R. Cerulli, S. Fujishige, A.R. Mahjoub (Eds.), Combinatorial Optimization - 4th International Symposium, ISCO 2016, LNCS 9849, pp. 135-147, 2016, DOI: 10.1007/978-3-319-45587-7_12. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45587-7_12 more...
- Published
- 2016
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.