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
In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5.
We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data.