1137
eng
reportzib
0
2009-07-09
2009-07-09
--
Extending a CIP framework to solve MIQCPs
This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.
09-23
1438-0064
1186
urn:nbn:de:0297-zib-11371
App. in: Mixed Integer Nonlinear Programming. Jon Lee, Sven Leyffer (eds.) The IMA Volumes in Mathematics and its Applications, 154. Springer 2011, pp. 427-444
Timo Berthold
unknown unknown
Stefan Heinz
Stefan Vigerske
ZIB-Report
09-23
eng
uncontrolled
mixed integer quadratically constrained programming
eng
uncontrolled
constraint integer programming
eng
uncontrolled
convex relaxation
eng
uncontrolled
nonconvex
Mathematik
Mixed integer programming
Quadratic programming
Nonconvex programming, global optimization
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Berthold, Timo
Heinz, Stefan
Vigerske, Stefan
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.pdf
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.pdf
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.ps
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.ps
1150
eng
reportzib
ZIB
0
2009-10-15
2009-10-15
--
Comparing MIQCP solvers to a specialised algorithm for mine production scheduling
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
09-32
1438-0064
1206
urn:nbn:de:0297-zib-11507
10.1007/978-3-642-25707-0
Appeared in: Modeling, Simulation and Optimization of Complex Processes, Proc. of the 4th Int. Conf. on High Performance Scientific Computing, 2009, Hanoi, Vietnam. H. G. Bock et al. (eds.) 2012, pp. 25-39
Andreas Bley
unknown unknown
Ambros Gleixner
Thorsten Koch
Stefan Vigerske
ZIB-Report
09-32
Informatik, Informationswissenschaft, allgemeine Werke
Production models
Scheduling theory, deterministic [See also 68M20]
Mixed integer programming
Nonconvex programming, global optimization
Applications of mathematical programming
Mathematical Optimization
Gleixner, Ambros
Koch, Thorsten
Vigerske, Stefan
MATHEON-B19:MINLP
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1150/ZR_09_32.pdf
https://opus4.kobv.de/opus4-zib/files/1150/ZR_09_32.ps
1199
eng
reportzib
0
2011-03-16
2011-03-16
--
On the computational impact of MIQCP solver components
We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
11-01
urn:nbn:de:0297-zib-11998
Timo Berthold
-empty- (Opus4 user: )
Ambros Gleixner
Timo Berthold
Stefan Heinz
Stefan Vigerske
ZIB-Report
11-01
deu
uncontrolled
MIQCP
deu
uncontrolled
MIP
deu
uncontrolled
mixed-integer quadratically constrained programming
deu
uncontrolled
computational
deu
uncontrolled
nonconvex
MATHEMATICAL SOFTWARE
Mathematical programming methods [See also 90Cxx]
Mixed integer programming
Nonconvex programming, global optimization
Nonlinear programming
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1199/ZR-11-01.pdf
1463
eng
reportzib
0
2012-02-06
2012-02-06
--
Undercover: a primal MINLP heuristic exploring a largest sub-MIP
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.
1438-0064
12-07
urn:nbn:de:0297-zib-14631
10.1007/s10107-013-0635-2
Mathematical Programming
urn:nbn:de:0297-zib-14631
Timo Berthold
Timo Berthold
Ambros Gleixner
ZIB-Report
12-07
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Large Neighborhood Search
eng
uncontrolled
Mixed-Integer Quadratically Constrained Programming
eng
uncontrolled
Nonconvex Optimization
Mixed integer programming
Quadratic programming
Nonconvex programming, global optimization
Nonlinear programming
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07.pdf
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07_rev.pdf
1559
jpn
reportzib
0
2012-07-25
2012-07-25
--
SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法
Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite
この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン
グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint
integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの
構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization
problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化
し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により,
Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開
発計画の概要について述べる.
This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how in concert these can be used to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview over available interfaces, and outline plans for future development.
1438-0064
urn:nbn:de:0297-zib-15598
Appeared in: Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming. Masakazu Muramatsu (ed. ) 2012, pp. 165-192
Timo Berthold
Ambros Gleixner
Ambros Gleixner
Stefan Heinz
Thorsten Koch
Yuji Shinano
ZIB-Report
12-24
mul
uncontrolled
SCIP, MIP, MINLP, CIP, LP, modeling, optimization
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1559/ZR-12-24.pdf
1560
eng
reportzib
0
2012-07-25
2012-07-25
--
Towards globally optimal operation of water supply networks
This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms.
In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem.
1438-0064
urn:nbn:de:0297-zib-15603
10.3934/naco.2012.2.695
Appeared in: Numerical Algebra, Control and Optimization 2 (2012) 695-711
Ambros Gleixner
Ambros Gleixner
Harald Held
Wei Huang
Stefan Vigerske
ZIB-Report
12-25
eng
uncontrolled
MINLP, global optimization, operative planning, water supply networks
Mixed integer programming
Nonconvex programming, global optimization
Applications of mathematical programming
Mathematical Optimization
Gleixner, Ambros
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1560/zibreport.pdf
1565
eng
reportzib
0
2012-07-31
2012-07-31
--
Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite
This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.
1438-0064
urn:nbn:de:0297-zib-15654
Timo Berthold
Ambros Gleixner
Gerald Gamrath
Ambros Gleixner
Stefan Heinz
Thorsten Koch
Yuji Shinano
ZIB-Report
12-27
eng
uncontrolled
LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gamrath, Gerald
Gleixner, Ambros
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1565/ZR-12-27.pdf
1803
eng
reportzib
0
2013-04-16
2013-04-16
--
Undercover Branching
In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred.
Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule.
We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.
1438-0064
urn:nbn:de:0297-zib-18030
10.1007/978-3-642-38527-8_20
Appeared in: Experimental Algorithms. 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings
Timo Berthold
Ambros Gleixner
Ambros Gleixner
ZIB-Report
13-14
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1803/ZR-13-14.pdf
1763
eng
reportzib
0
2013-10-01
2013-10-01
--
Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming
Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.
1438-0064
urn:nbn:de:0297-zib-17631
10.1007/978-3-642-38171-3_26
Appeared in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013
Ambros Gleixner
Ambros Gleixner
Stefan Weltge
ZIB-Report
13-04
eng
uncontrolled
MINLP
eng
uncontrolled
optimization-based bound tightening
eng
uncontrolled
optimality-based bound tightening
eng
uncontrolled
OBBT
eng
uncontrolled
propagation
Nonconvex programming, global optimization
Mathematical Optimization
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1763/ZR-13-04.pdf
1775
eng
reportzib
0
2013-02-14
2013-02-14
--
Analyzing the computational impact of MIQCP solver components
We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
1438-0064
urn:nbn:de:0297-zib-17754
10.3934/naco.2012.2.739
Appeared in: Numerical Algebra, Control and Optimization vol. 2, no. 4 (2012) pp. 739-748
Timo Berthold
Timo Berthold
Ambros Gleixner
Stefan Heinz
Stefan Vigerske
ZIB-Report
13-08
eng
uncontrolled
mixed-integer quadratically constrained programming
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-cut
eng
uncontrolled
nonconvex
eng
uncontrolled
global optimization
Mixed integer programming
Nonconvex programming, global optimization
Nonlinear programming
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1775/ZR-13-08.pdf