Minotaur: a mixed-integer nonlinear optimization toolkit
- PDF / 2,309,727 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 241 Views
Minotaur: a mixed-integer nonlinear optimization toolkit Ashutosh Mahajan1 · Sven Leyffer2 · Jeff Linderoth3 · James Luedtke3 · Todd Munson2 Received: 16 October 2017 / Accepted: 19 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We present a flexible framework for general mixed-integer nonlinear programming (MINLP), called Minotaur, that enables both algorithm exploration and structure exploitation without compromising computational efficiency. This paper documents the concepts and classes in our framework and shows that our implementations of standard MINLP techniques are efficient compared with other state-of-the-art solvers. We then describe structure-exploiting extensions that we implement in our framework and demonstrate their impact on solution times. Without a flexible framework that enables structure exploitation, finding global solutions to difficult nonconvex MINLP problems will remain out of reach for many applications. Keywords Mixed-integer nonlinear programming · Global optimization · Software Mathematics Subject Classification 65K05 · 90C11 · 90C30 · 90C26
B
Ashutosh Mahajan [email protected] Sven Leyffer [email protected] Jeff Linderoth [email protected] James Luedtke [email protected] Todd Munson [email protected]
1
Industrial Engineering and Operations Research, IIT Bombay, Mumbai 400076, India
2
Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL 60439, USA
3
Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, WI 53706, USA
123
A. Mahajan et al.
1 Introduction, background, and motivation Over the past two decades, mixed-integer nonlinear programming (MINLP) has emerged as a powerful modeling paradigm that arises in a broad range of scientific, engineering, and financial applications; see, e.g., [7,28,41,57,66,71]. MINLP combines the combinatorial complexity of discrete decision variables with the challenges of nonlinear expressions, resulting in a class of difficult nonconvex optimization problems. The nonconvexities can arise from both the integrality restrictions and nonlinear expressions. MINLP problems can be generically expressed as ⎧ f (x), ⎨ minimize x ⎩ subject to c(x) ≤ 0, x ∈ X , xi ∈ Z, ∀i ∈ I,
(1.1)
where f : IRn → IR and c : IRn → IRm are given functions, X ⊂ IRn is a bounded polyhedral set, and I ⊆ {1, . . . , n} is the index set of the integer variables. Equality and range constraints can be readily included in (1.1). MINLP problems are at least NP-hard combinatorial optimization problems because they include mixed-integer linear programming (MILP) as a special case [50]. In addition, general nonconvex MINLP problems can be undecidable [49]. In the remainder of this paper, we consider only MINLP problems (1.1) that are decidable by assuming that either X is compact or the problem functions, f and c, are convex. In reality, the distinction between hard and easy problems in MINLP is far more subtle, and instances of NP-
Data Loading...
