90C11 Mixed integer programming
Refine
Year of publication
Document Type
- ZIB-Report (93)
- Doctoral Thesis (5)
- Master's Thesis (3)
- Habilitation (1)
Keywords
- mixed integer programming (20)
- Mixed Integer Programming (9)
- mixed-integer programming (8)
- branch-and-bound (7)
- Integer Programming (6)
- integer programming (6)
- branching rule (5)
- network design (5)
- primal heuristic (5)
- Constraint Programming (4)
- Ganzzahlige Programmierung (4)
- MIP (4)
- Routing (4)
- branch-and-cut (4)
- domain propagation (4)
- large neighborhood search (4)
- primal heuristics (4)
- routing (4)
- Large Neighborhood Search (3)
- Primal Heuristic (3)
- Resource Allocation (3)
- SAT (3)
- Steiner tree packing (3)
- UMTS (3)
- constraint integer programming (3)
- nonconvex (3)
- Branch-And-Cut (2)
- Branch-and-cut (2)
- Branch-and-price (2)
- Chip-Verifikation (2)
- Column generation (2)
- Constraint Programmierung (2)
- Constraint integer programming (2)
- Gemischt-Ganzzahlige Programmierung (2)
- IP (2)
- Linear programming (2)
- MINLP (2)
- MIQCP (2)
- Mathematical Programming (2)
- Mixed-Integer Nonlinear Programming (2)
- Mixed-Integer Programming (2)
- Mixed-integer linear programming (2)
- Mixed-integer nonlinear programming (2)
- Mixed-integer semidefinite programming (2)
- Nachbarschaftssuche (2)
- Network Performance (2)
- Network Planning (2)
- Network design (2)
- Operation Research (2)
- Optimierungssoftware (2)
- Optimization (2)
- Optimization solver (2)
- ParaSCIP (2)
- Parallelization (2)
- Primalheuristiken (2)
- Scheduling (2)
- Wireless ad hoc networks (2)
- branch and cut (2)
- branch-and-cut algorithm (2)
- chip verification (2)
- conflict analysis (2)
- constraint programming (2)
- cutting planes (2)
- dual degeneracy (2)
- energy efficiency (2)
- exact computation (2)
- mixed integer nonlinear programming (2)
- mixed-integer quadratically constrained programming (2)
- optimization software (2)
- presolving (2)
- scip (2)
- search strategy (2)
- strong branching (2)
- survivable network design (2)
- 2-dim Cutting Stock Problem (1)
- Algebraic Modelling Languages (1)
- Branch and Cut (1)
- Branch-and-cut-and-price (1)
- CP (1)
- Chip Verification (1)
- Chipverifikation (1)
- Combinatorial Optimization (1)
- Constraint Integer Programming (1)
- Cutting Planes (1)
- Distributed Memory (1)
- Drinking water supply (1)
- Eigenschaftsprüfer (1)
- Entry-Exit Model (1)
- Facility Location (1)
- Fallstudie (1)
- Feasibility Pump (1)
- Gas Distribution Networks (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gurobi (1)
- Hardware Configuration (1)
- Heuristics (1)
- Hierarchical Networks (1)
- IP Routing (1)
- IST-20 (1)
- Instances (1)
- Internet routing (1)
- LP solver (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- Lagrangian Relaxation (1)
- Lagrangian relaxation (1)
- Line Planning, Extended Formulation, Public Transport (1)
- Location Planning in Telecommunications (1)
- MINLP solver (1)
- MINLP, global optimization, operative planning, water supply networks (1)
- MIP solver (1)
- MIP-Solver (1)
- MIPLIB (1)
- MIPLIB2003 (1)
- MOMENTUM (1)
- Mathematical Optimization (1)
- Mathematische Programmierung (1)
- Maximum Diversity Problem (1)
- Mengenüberdeckung (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Nonlinear Nonconvex Stochastic Optimization (1)
- Mixed-Intger Programming (1)
- Mixed-integer programming (1)
- Modelling (1)
- Modelling Languages (1)
- Multi-layer-Netzen Ausfallsicherheit (1)
- Neighbourhood Search (1)
- Network Capacity Planning (1)
- Network Models (1)
- Network planning (1)
- Netzwerkaggregation (1)
- Newton barrier method (1)
- Nonconvex Optimization (1)
- OSPF Routing (1)
- Parallel Computing (1)
- Passenger routing (1)
- Periodic Timetabling (1)
- Periodic timetabling (1)
- Primalheuristik (1)
- Problem Instances (1)
- Pseudo-Boolean (1)
- Public transport (1)
- SCIP (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- SNDlib (1)
- Shortest Path Routing (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Steiner Tree Packing in Graphs (1)
- Steiner connectivity (1)
- Steiner tree (1)
- Steiner tree solver (1)
- Supercomputer (1)
- Surviva (1)
- Survivable Network Design (1)
- Survivable Networks (1)
- Teaching (1)
- Telecommunication (1)
- Telecommunication Network Design (1)
- Telekommunikationsnetze (1)
- Topology Planning (1)
- Traffic enineering (1)
- Trassenallokation (1)
- Tropical Geometry (1)
- Ubiquity Generator Framework (1)
- analytic center (1)
- block structure (1)
- branch-and-cut-and-price (1)
- branch-and-price (1)
- branch-cut-and-price framework (1)
- capacitated network design (1)
- case study (1)
- column generation (1)
- computational (1)
- configuration (1)
- continuous time model (1)
- convex relaxation (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- cplex (1)
- cut-based inequalities (1)
- cutset-polyhedra (1)
- data library (1)
- distribution network (1)
- dual proof analysis (1)
- feasibility pump (1)
- fix-and-propagate (1)
- flow-cutset inequalities (1)
- formal chip verification (1)
- formale Chip Verifikation (1)
- gas transport optimization (1)
- gemischt-ganzzahlige Optimierung (1)
- general flow-cutset inequalities (1)
- generic column generation (1)
- global optimization (1)
- grid graphs (1)
- grooming (1)
- hardware configuration (1)
- hop limits (1)
- interior point algorithm (1)
- knapsack with integer capacity (1)
- linear programming (1)
- linear programming bounds (1)
- link and path restoration (1)
- massive parallization (1)
- mathematical model (1)
- micro chip (1)
- minimum cost operative planning (1)
- mixed integer model (1)
- mixed integer quadratically constrained programming (1)
- mixed integer rounding (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer nonlinear programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- mixed-integer semidefinite programming (1)
- modeling (1)
- multi-criteria optimization (1)
- multi-hour (1)
- multi-layer (1)
- multi-layer networks (1)
- multi-period (1)
- multicast network design (1)
- network aggregation (1)
- network detection (1)
- network planning (1)
- no-good learning (1)
- nonlinear programming m (1)
- optimization (1)
- parallel branch-and-bound (1)
- parallel computing (1)
- perfect power control (1)
- performance measure (1)
- periodic event scheduling (1)
- perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study (1)
- power consumption (1)
- preprocessing (1)
- property checking (1)
- radio interface (1)
- railway track allocation (1)
- restoration (1)
- rounding (1)
- set covering (1)
- simplex method (1)
- solution learning (1)
- solver software (1)
- supercomputing (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- survivable multi-layer network design (1)
- telecommunication network design (1)
- telecommunication networks (1)
- telecommunications (1)
- tropical geometry (1)
- variable selection (1)
- zonotopal tilings (1)
Institute
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.
Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The
most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [3]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [4]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods
available in the solver. Finally, we provide better primal bounds for five PESPlib instances.
The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.
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.
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.
In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. In MADASS, we need to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the computational results won the contest.
In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2CSP literature.
Conflict Analysis for MINLP
(2020)
The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.
Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search.
We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.
The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.
Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average.
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.
"Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex." This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.
In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.
The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.
SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice.
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.
Mixed integer programming has become a very powerful tool for modeling and
solving real-world planning and scheduling problems, with the breadth of
applications appearing to be almost unlimited. A critical component in
the solution of these mixed-integer programs is a set of routines commonly
referred to as presolve. Presolve can be viewed as a collection of
preprocessing techniques that reduce the size of and, more importantly,
improve the ``strength'' of the given model formulation, that is, the degree
to which the constraints of the formulation accurately describe the
underlying polyhedron of integer-feasible solutions. As our computational
results will show, presolve is a key factor in the speed with which we can
solve mixed-integer programs, and is often the difference between a model
being intractable and solvable, in some cases easily solvable. In this
paper we describe the presolve functionality in the Gurobi commercial
mixed-integer programming code.
This includes an overview, or taxonomy of the different methods that are
employed, as well as more-detailed descriptions of several of the techniques,
with some of them appearing, to our knowledge, for the first time in the
literature.
This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality.
SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.
The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers.
This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.