90C10 Integer programming
Refine
Year of publication
Document Type
- ZIB-Report (83)
- Doctoral Thesis (4)
- Habilitation (2)
Is part of the Bibliography
- no (89)
Keywords
- integer programming (18)
- Integer Programming (10)
- mixed integer programming (7)
- constraint integer programming (6)
- combinatorial optimization (5)
- cumulative constraint (5)
- branching rule (4)
- constraint programming (4)
- domain propagation (4)
- line planning (4)
- polyhedral combinatorics (4)
- Ganzzahlige Programmierung (3)
- IP (3)
- column generation (3)
- conflict analysis (3)
- mixed-integer programming (3)
- set partitioning (3)
- symmetry breaking (3)
- transfers (3)
- Branch-and-cut (2)
- Branch-and-price (2)
- Column generation (2)
- Constraint integer programming (2)
- Kombinatorische Optimierung (2)
- Linear programming (2)
- MIP (2)
- Mixed Integer Programming (2)
- Mixed-integer linear programming (2)
- Mixed-integer nonlinear programming (2)
- Mixed-integer semidefinite programming (2)
- Operations Research (2)
- Optimierung (2)
- Optimization solver (2)
- Parallelization (2)
- Polyhedral Combinatorics (2)
- Sudoku (2)
- Zählen (2)
- branch-and-bound (2)
- counting (2)
- direct connection (2)
- dual degeneracy (2)
- duty scheduling (2)
- hypergraph (2)
- integrated scheduling (2)
- metric inequalities (2)
- optical networks (2)
- optional activities (2)
- orbitopes (2)
- rapid branching (2)
- scheduling (2)
- search strategy (2)
- set packing (2)
- stable multi-sets (2)
- stable set polytope (2)
- strong branching (2)
- vehicle positioning (2)
- wavelength assignment (2)
- 1/2}-Chvatal-Gomory cuts (1)
- ATSP (1)
- Airline Crew Scheduling (1)
- Asymmetric Travelling Salesman Problem (1)
- Aufzugssteuerung (1)
- Ausubel Milgrom Proxy Auction Mechanism (1)
- Benders' decomposition (1)
- Branch and Generate (1)
- Branch&Cut-Algorithm (1)
- Cellular Radio Telephone Systems (1)
- Chip-Verifikation (1)
- Column Generation (1)
- Combinatorial Auction Problem (1)
- Constraint Programmierung (1)
- Container Terminal (1)
- Control of Stacker Cranes (1)
- Cutting Planes (1)
- Dienstplanung (1)
- Dispatching von Fahrzeugen (1)
- Dual Ascent (1)
- Duty Rostering (1)
- Flugzeugumlaufplanung (1)
- Frequency Assignment Problem (1)
- General Public (1)
- Graphen (1)
- Graphenisomorphie (1)
- Graphs (1)
- Heuristics (1)
- Hilbert basis (1)
- Integer Programs (1)
- Integral pointed cones (1)
- Integrierte Umlauf- und Dienstplanung (1)
- Intermediate Storage Area (1)
- Kürzeste Wege (1)
- LP solver (1)
- Lagrangean Relaxation (1)
- Landside operation (1)
- Linienplanung (1)
- MINLP solver (1)
- MIP solver (1)
- MIPLIB (1)
- Mathematical Programming Testdata Library (1)
- Minimum-Cost Flow Problems (1)
- Modeling (1)
- Modelling language (1)
- Nahverkehr (1)
- Online-Optimierung (1)
- Optimization (1)
- Orbitope (1)
- Passenger routing (1)
- Periodic timetabling (1)
- Problem Instances (1)
- Protein Folding (1)
- Pseudo-Boolean (1)
- Public Transit (1)
- Public transport (1)
- Railway Track Allocation (1)
- Regionalverkehr (1)
- Robust Optimization (1)
- SAT (1)
- STP (1)
- Self-Avoiding Path (1)
- Separation Algorithm (1)
- Set Partitioning (1)
- Shortest Path Routing (1)
- Signaling network (1)
- Spaltenerzeugung (1)
- Steiner Trees (1)
- Steiner tree solver (1)
- Storage space allocation (1)
- Symmetrie-Brechung (1)
- Symmetrie-Erkennung (1)
- Tail Assignment (1)
- Telecommunications (1)
- Ticket prices (1)
- Time Windows (1)
- Umlaufplanung (1)
- Umsteigen (1)
- Vehicle Routing Problem (1)
- Wegeprobleme (1)
- Yard crane scheduling (1)
- Zimpl (1)
- antiwebs (1)
- applications of integer programming (1)
- assignment (1)
- bipartite (1)
- block structure (1)
- branch-and-price (1)
- branch-cut-and-price framework (1)
- bundle method (1)
- chip verification (1)
- combinatorial packing (1)
- computations (1)
- cost allocation game (1)
- crew scheduling (1)
- cutting planes (1)
- dual proof analysis (1)
- duty rostering (1)
- duty templates (1)
- elevator control (1)
- energetic reasoning (1)
- facet (1)
- fix-and-propagate (1)
- ganzzahlige Programme (1)
- generic column generation (1)
- graph ismorphism (1)
- graph theory (1)
- hyperassignment (1)
- hyperassignments (1)
- hypergraphs (1)
- ideal matrices (1)
- inequality (1)
- integral Carathéodory property (1)
- large neighborhood search (1)
- large scale optimization (1)
- lexicographic representatives (1)
- line planning, transfers,Steiner connectivity problem (1)
- linear programming (1)
- linear relaxation (1)
- load-balancing (1)
- matching (1)
- mathematical optimization (1)
- mixed-integer linear and 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)
- mixed-integer-programming (1)
- modeling (1)
- multi-commodity flow problem (1)
- multi-criteria optimization (1)
- network design (1)
- no-good learning (1)
- nonidentical machines (1)
- nonlinear programming (1)
- online optimization (1)
- operations research (1)
- optical network design (1)
- optional resources (1)
- parallel branch-and-bound (1)
- path problems (1)
- perfect graph (1)
- perfect graphs (1)
- polyhedral relaxations (1)
- primal heuristic (1)
- primal heuristics (1)
- public transit (1)
- public transport (1)
- public transportation (1)
- quadratic programming (1)
- railways (1)
- relaxations (1)
- relaxations of perfect graphs (1)
- resource-constrained project Scheduling (1)
- resource-constrained project scheduling (1)
- robuste Optimierung (1)
- rolling-stock-planning (1)
- rounding (1)
- separation algorithm (1)
- separation algorithms (1)
- set covering (1)
- shortest paths (1)
- simplex method (1)
- solution learning (1)
- steel mill slab problem (1)
- symmetry detection (1)
- transportation planning (1)
- variable fixing (1)
- variable selection (1)
- vehicle dispatching (1)
- vehicle rotation planning (1)
- vehicle scheduling (1)
- wavelength conversion (1)
- {0 (1)
- Öffentlicher Verkehr (1)
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.
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.
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.
We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are
inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are
located.
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.