Improving the performance of DICOPT in convex MINLP
problems using a feasibility pumpDavid E. Bernala , Stefan Vigerskeb , Francisco Trespalaciosc , andIgnacio E. Grossmanna∗a

Department of Chemical Engineering, Carnegie Mellon University, 5000 Forbes Avenue,
Pittsburgh, PA 15213, USA;b
GAMS Software GmbH, c/o Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany;c
ExxonMobil Research and Engineering, 1545 Route 22 East, Annandale NJ 08801, USA

August 12, 2019

Abstract
The solver DICOPT is based on the outer-approximation algorithm used for solving
mixed-integer nonlinear programming (MINLP) problems. This algorithm is very effective
for solving some types of convex MINLPs. However, it has been observed that DICOPT has
difficulties solving instances in which some of the nonlinear constraints are so restrictive that
nonlinear subproblems generated by the algorithm are infeasible. This problem is addressed inthis paper with a feasibility pump algorithm, which modifies the objective function in order
to efficiently find feasible solutions. It has been implemented as a preprocessing algorithm,
which is used to initialize both the incumbent and the mixed-integer linear relaxation of
the outer-approximation algorithm. Computational comparisons with previous versions of
DICOPT on a set of convex MINLPs demonstrate the effectiveness of the proposed algorithm
in terms of solution quality and solution time.
Keywords: feasibility pump; mixed-integer nonlinear programming; primal heuristics
2010 Mathematics Subject Classification: 90C11, 90C25, 90C30.

1Introduction

The capabilities of algorithms designed to solve mathematical programming problems are continuously improving. This allows solving increasingly larger and more complex problems. Efficientsolutions of mixed-integer linear programs (MIP) and nonlinear programs (NLP) enable the solution of mixed-integer nonlinear programs (MINLP). These problems are of great interest inchemical engineering and many other areas as they combine integer variables (like discrete choices
in superstructures or networks) with nonlinear constraints (for example posynomial equations inresource allocation for scheduling and convex reformulations of horizon time constraints in thedesign of multiproduct batch processes) [5, 15, 16, 19, 21]. The general form of an MINLP is,
min f (x, y),
x,y

s.t.

g(x, y) ≤ 0,

(MINLP)x ∈ X, y ∈ Y ∩ Zny ,where X ⊆ Rnx , Y ⊆ Rny , f : X × Y → R is the objective function and at least one of theconstraints g : X × Y → Rm or the objective function itself is nonlinear. MINLP models are∗ Corresponding author. Email: grossmann@cmu.edu

1generally nonconvex due to the discrete nature of y and possible nonconvexity of f and g. Models inwhich X and Y are convex and f and gi , i = 1, . . . , m, are convex on X × Y , are denoted as convex
MINLP problems. In the following, we will assume that X and Y describe possible variable bounds,
that is, X = [xL , xU ] and Y = [y L , y U ] for xL , xU ∈ (R ∪ {±∞})nx and y L , y U ∈ (Z ∪ {±∞})ny .
DICOPT (Discrete Continuous Optimizer) is an MINLP solver that has been developed in
1988. It combines the outer-approximation method [11] with equality relaxation and augmented
penalty [23]. The algorithm decomposes the MINLP into an NLP subproblem defined by fixing
the discrete variables in the MINLP and a MIP approximation defined by linearizations of thenonlinear functions in the MINLP. The MIP and the NLP are solved alternately, whereby the MIP
approximation provides values for fixing the discrete variables in the NLP, and the convex NLP
subproblem, if feasible, provides feasible solutions to the MINLP and cutting planes to improve
the MIP approximation. If the MINLP is convex, then this MIP approximation is a relaxation of
the MINLP, thus providing a lower bound to its optimal value, and the NLP subproblems can besolved to global optimality yielding an upper bound. By adding additional inequalities to the MIP
approximation, one can further ensure that any fixed values for the discrete variables are evaluatedby an NLP at most once. Therefore, for a convex MINLP, a possible stopping criterion is that thebound defined by the last MIP approximation is within a tolerance of the objective value of thebest solution found.
For some problems, DICOPT has difficulty in finding a feasible solution. The main reason forthis is that by default, and to address nonconvex problems, DICOPT does not include linearizationsof nonlinearities from infeasible NLPs into the MIP. Instead, it only excludes the infeasible fixed
integer variables in the MIP and resolves it. Furthermore, even if linearizations are included for
infeasible NLPs, which are valid for convex MINLPs, DICOPT still has difficulties in finding afeasible solution for some problems, which results in slow progress compared to the case where
feasible MINLP solutions are found early in the search.
In order to quickly find initial feasible solutions for convex MINLPs, an implementation ofa feasibility pump [6, 12] has been incorporated into DICOPT as described in this paper. The
feasibility pump is similar to the outer-approximation algorithm, but its focus is on finding feasible
solutions. As with outer-approximation, the main idea of the feasibility pump is to decompose theoriginal MINLP problem into a MIP and an NLP. The MIP problem yields solutions that satisfy
integrality requirements (y ∈ Zny ) but may violate nonlinear constraints, while the solutions of
the NLP problems satisfy the constraints g(x, y) ≤ 0 but may violate integrality requirements.
Contrary to outer-approximation, both MIP and NLP are defined over relaxations of the feasiblearea of the original MINLP. By alternately projecting onto the MIP and NLP relaxations, a solution
is obtained that is feasible for both relaxations, and thus for the MINLP itself, if certain constraint
qualifications are satisfied [6]. The feasibility pump can also be used as a standalone solver for
convex MINLPs by including a bound (cutoff-value) to the objective function, which is set to theobjective value of the best-known solution, reduced by a desired δ-improvement. Applying thismodified feasibility pump repeatedly until the MIP becomes infeasible, yields a δ-optimal solutionof a convex MINLP [6]. The drawback of this algorithm is that it may require many iterations,since only a δ-improvement of the objective function is enforced at each iteration.
In this work, a feasibility pump is added to DICOPT and is used as an initialization of theouter-approximation method. In the feasibility pump, improvements in the objective function are
enforced at each iteration. After the method finishes, the cuts that define the MIP relaxation of
the feasibility pump and the best-found solution are passed on to the outer-approximation method
to find better solutions, if any, and prove optimality. The described extension of DICOPT has been
available in GAMS1 since version 24.5. We present computational results of the new method on aset of convex MINLP problems, and show that it outperforms the previous version of DICOPT.
This paper is organized as follows. Section 2 provides an overview of the outer-approximationand the feasibility pump algorithms for convex MINLP problems. Section 3 describes the algorithm
proposed in this work, which uses the feasibility pump as initialization for the outer-approximation
algorithm. An illustrative example and computational results are presented in Section 4.
1 http://www.gams.com/latest2

2

BackgroundIn the following, we summarize the outer-approximation algorithm [11], the feasibility pumpalgorithm [6], and a hybrid of both algorithms. These algorithms are intended to solve problems of
the form (MINLP). The following assumptions are made [11, 13]:
(A1) The integer variables are bounded, that is, Y is a bounded set.
(A2) The constraint functions g(x, y) and the objective function f (x, y) are continuously differentiable and convex on X × Y .
(A3) The continuous relaxation of the (MINLP) obtained by removing the integrality requirementy ∈ Zny is bounded.

2.1

Outer-approximation algorithm

The outer-approximation algorithm was proposed by Duran and Grossmann in 1986 [11]. In theoriginal version of the algorithm, the starting point was given by some fixed values for the binary
variables y. Viswanathan and Grossmann [23] proposed to solve the continuous relaxation of the
MINLP in the first iteration, which is obtained by relaxing the integrality requirement on y,
min f (x, y),
x,y

s.t.

(rMINLP)g(x, y) ≤ 0,x ∈ X, y ∈ Y.

If (rMINLP) is infeasible, then (MINLP) is also infeasible. Otherwise, let (x̄0 , ȳ 0 ) be a solution to(rMINLP). If ȳ 0 is integral, (x̄0 , ȳ 0 ) is an optimal solution to (MINLP) and the algorithm stops.
If ȳ 0 is not integral, a MIP relaxation of (MINLP) is constructed by linearizing the nonlinear
functions in g(x, y) and f (x, y) by first-order Taylor series approximations at (x̄0 , ȳ 0 ), which, inthe case of convex functions, provide supporting hyperplanes [23]. Given a set of solutions x̄k ,k = 1, . . . , i − 1, the i-th MIP problem generated by the outer-approximation algorithm is asfollows:
min

x,y,α

α,


x − x̄ks.t. f (x̄ , ȳ ) + ∇f (x̄ , ȳ )≤ α,y − ȳ kx − x̄kgl (x̄k , ȳ k ) + ∇gl (x̄k , ȳ k )>≤ 0,y − ȳ k
k

k

k

k >



ky − ȳ k k1 ≥ 1,

k = 0, . . . , i − 1,kl ∈ L , k = 0, . . . , i − 1,

(MIPi )k ∈ C i,x ∈ X, y ∈ Y ∩ Zny , α ∈ R,
where Lk ⊆ {1, . . . , m} is a subset of constraints for which linearizations are included (L0 ={1, . . . , m}, typically), and C i ⊆ {1, . . . , i − 1} is a subset of iterations in which the so-called integer
cut ky − ȳ k k1 is added [2] (discussed below). Note, that due to assumption (A1), the equationky − ȳ k k1 ≥ 1 can be written in an equivalent linear form, see Appendix A. (MIPi ) is called themaster problem. We denote by (α̂i , x̂i , ŷ i ) a solution for (MIPi ), if feasible. Due to assumption(A2), the optimal value of (MIPi ) yields a lower bound to the optimal value of (MINLP), if C i = ∅(for now).
The solution of (MIPi ) is used to define the following NLP subproblem of MINLP, obtained by
fixing the integer variables to ŷ i :min f (x, ŷ i ),xs.t.

g(x, ŷ i ) ≤ 0,x ∈ X.
3(NLPi )

Let ȳ i := ŷ i and let x̄i be a solution to (NLPi ), if feasible. Then (x̄i , ȳ i ) is a feasible point to(MINLP) and provides an upper bound on its optimal value. If (NLPi ) is not feasible, then let(x̄i , s̄i ) be a minimal infeasible solution to (NLPi ), that is, a solution to the NLP
min
x,s

s.t.

m
X

sj ,

j=1

g(x, ŷ i ) ≤ s,

(NLP-feasi )x ∈ X, s ∈ Rm+.
Note that adding linearization of gj (x, y) in (x̄i , ȳ i ) for those j ∈ {1, . . . , m} with gj (x̄i , ȳ i ) > 0 to
(MIPi ) will eliminate (x̄i , ȳ i ) from its feasible set. However, for the case that (NLPi ) is feasible andthe corresponding linearization are added there may exist some other values of x for which (x, ȳ i )is still feasible for (MIPi ). Therefore, one may, additionally or alternatively, add the integer-cut
ky − ŷ i k1 ≥ 1 to (MIPi ) to cut off any point in Rnx × {ŷ i }. Hence, if only those iterations areincluded into C i for which (NLPi ) is infeasible, then the optimal value of (MIPi ) provides a lower
bound to the optimal value of (MINLP).
The outer-approximation algorithm is summarized in Algorithm 1. The NLP and MIP problems
are solved alternately until the gap between the bounds given by (NLPi ) and (MIPi ) is less than
the specified tolerance. It has been proved that this algorithm finds an -optimal solution of aconvex MINLP or proves that none exist in a finite number of iterations if the solution of every(NLPi ) and (NLP-feasi ) satisfies the linear independence constraint qualification [5, 11, 13], thatis, the gradients of the constraints satisfied with equality are linearly independent.

2.2

Outer-approximation in DICOPT

Outer-approximation is the main algorithm behind the solver DICOPT [17, 18, 23], which has beendeveloped in the late 1980s by the research group of I.E. Grossmann at the Engineering Research
Design Center at Carnegie Mellon University. Since then, it has been available in the commercial
algebraic modeling system GAMS. DICOPT solves NLP and MIP problems by means of othersolvers that are available in GAMS and are specialized in these problem types.
Although the outer approximation algorithm has a guaranteed convergence for convex MINLP
problems [11], DICOPT implements the methods of equality relaxation and augmented penalty tomake it a better heuristic for solving nonconvex MINLP problems. The implementation of theouter-approximation algorithm does therefore slightly deviate from Algorithm 1:• For convex MINLP, Z L and Z U yield valid lower and upper bounds on the optimal value of(MINLP) given that (NLPi ) can be solved to global optimality. Therefore, closing the gap
between these bounds is a stopping criterion that ensures finding a global optimal solution ina finite number of iterations. This can be enabled in DICOPT by setting the option stop
to 1. For nonconvex MINLPs, valid lower bounds and solving (NLPi ) to global optimality
are not ensured. Therefore, by default DICOPT stops as soon as the upper bound Z U stops
improving. Although it is a heuristic, this stopping criterion has shown that in many cases ityields optimal or near optimal integer solutions. For the computational experiments in thispaper, we have set option stop to 1.
• If the NLP subproblem (NLPi ) is feasible, linearizations of nonlinear functions are not addedin their original form to (MIPi ). Instead, they are added as soft-constraints, that is, violationof these constraints is allowed but penalized in the objective function (by default, a weight ρof 1000 times the constraint marginal is used) [23]. Also in the context of convex MINLP, thepenalty relaxation of linearizations is applied. Note, that the optimal value of the modified
master problem still provides a valid lower bound on the optimal value of (MINLP) if thecontribution of the penalty term is removed and termination is still ensured due to the finite
number of integer points y to be enumerated. This modification leads to the following MIP

4

Algorithm 1 Outer-approximation algorithm.
1: Set Z U = ∞, Z L = −∞, i = 0. Initialization
2: Define gap tolerance  ≥ 0
3: Solve (rMINLP). Solve initial relaxation
4: if (rMINLP) is infeasible then5:
Set Z L = ∞. (MINLP) is infeasible
6: else7:
Let (x̄0 , ȳ 0 ) be an optimal solution of (rMINLP)
8:
Set Z L = f (x̄0 , ȳ 0 )9:
Set L0 = {1, . . . , m}, C 0 = ∅10:
if ȳ 0 ∈ Zny then11:
Set Z U = f (x̄0 , ȳ 0 ) and ŷ 0 = ȳ 0
12: while Z U − Z L >  do
13:
Set i = i + 1
14:
Solve (MIPi ). Solve master problem
15:
if (MIPi ) is infeasible then16:
Set Z L = ∞. (MINLP) is infeasible
17:
else
18:
if (MIPi ) is unbounded then19:
Let (α̂i , x̂i , ŷ i ) be a feasible solution of (MIPi )
20:
else
21:
Let (α̂i , x̂i , ŷ i ) be an optimal solution of (MIPi )22:
Set Z L = α̂i23:Set ȳ i = ŷ i and solve (NLPi ). Solve nonlinear subproblem
24:
if (NLPi ) is infeasible then25:
Solve (NLP-feasi )26:
Let (x̄i , s̄i ) be an optimal solution of (NLP-feasi )27:
Set C i+1 = C i ∪ {i}
28:
else
29:
Let x̄i be an optimal solution of (NLPi )30:
Set C i+1 = C i
31:
if Z U < f (x̄i , ŷ i ) then32:
Set Z U = f (x̄i , ŷ i ), x∗ = x̄i and y ∗ = ŷ i
33:
Set Li = {j ∈ {1, . . . , m} : gj (x̄i , ŷ i ) ≥ 0 and gj is nonlinear}
34: (x∗ , y ∗ ) is an optimal solution of (MINLP), if Z U < ∞, otherwise (MINLP) is infeasible

master problem:X
min α +
ρl sl ,
x,y,α,sl∈Lk
x − x̄ks.t. f (x̄ , ȳ ) + ∇f (x̄ , ȳ )≤ α,y − ȳ kx − x̄k≤ sl ,
gl (x̄k , ȳ k ) + ∇gl (x̄k , ȳ k )>y − ȳ k
k

k

k

k >



k = 0, . . . , i − 1,(rMIPi )kl ∈ L , k = 0, . . . , i − 1,ky − ȳ k k1 ≥ 1,

k ∈ C i,Pi−1

x ∈ X, y ∈ Y ∩ Zny , α ∈ R, s ∈ R+ k=0

|Lk |

.

• If the NLP subproblem (NLPi ) is infeasible, DICOPT by default adds only an integer cut
to eliminate the current fixing y = ŷ i from (rMIPi ), but does not add the corresponding
linearizations of nonlinear functions, i.e., Li = ∅ if (NLPi ) is infeasible in Line 33 of5

Algorithm 1. This option is sufficient to avoid visiting the same solution point again while
avoiding adding linearizations which are not supporting hyperplanes for nonconvex MINLPs.
However, it also exhibits slower progress as less information is made available to the masterproblem. Thus, when solving a convex MINLP, these valid linearizations should be added.
This can be enabled in DICOPT by setting the option infeasder to 1. We do so in our
computational experiments.
• Finally, DICOPT relaxes nonlinear equality constraints to inequalities and adds corresponding
linearizations to (rMIPi ). The dual multipliers in the solution of (NLPi ) are used to decidein which direction to relax the inequalities [23]. For a convex MINLP, such constraints do
not appear.

2.3

Feasibility pump

The feasibility pump algorithm is a primal heuristic developed by Fischetti, Glover, and Lodi toquickly find feasible solutions for MIPs where all integer variables are binaries [12]. Extensions
and variations of the algorithm have been proposed, including an extension to general integer
variables [3]. Nowadays, many state-of-the-art commercial and non-commercial MIP solvers feature
implementations of the feasibility pump [3]. The first extension of the feasibility pump algorithm toconvex MINLP problems was introduced by Bonami, Cornuéjols, Lodi, and Margot [6]. Contrary
to the original feasibility pump for MIP [12], the feasibility pump for convex MINLP is guaranteed
to converge to a feasible solution, if any. Subsequently, several authors have proposed extensions
to nonconvex MINLPs [4, 9, 14], where the handling of the nonconvex nonlinear constraints poses
an additional challenge. The MINLP solvers BONMIN and Couenne have implemented feasibility
pump algorithms as primal heuristics [4, 6].
The main idea of this algorithm is to decompose the original mixed-integer problem into
two parts: integer feasibility and constraint feasibility. For convex MINLPs, a MIP is solved toobtain a solution, which satisfies the integrality constraints on y, but may violate some of thenonlinear constraints; next, by solving an NLP, a solution is computed that satisfies the constraints(g(x, y) ≤ 0) but might again violate the integrality constraints on y. By minimizing iteratively the
distance between these two types of solutions, a solution that is both constraint- and integer-feasible
can be expected. The first iteration of the algorithm proposed in [6] is the same as in Algorithm 1,
where the continuous relaxation (rMINLP) of the original MINLP problem is solved. Following this,the next iteration builds a MIP master problem with the outer-approximation linearization of thenonlinear constraints and a modified objective function called the Feasibility Outer-Approximation:
min ky − ȳ i−1 k1 ,
x,y

s.t.

k

k

k

k >



gl (x̄ , ȳ ) + ∇gl (x̄ , ȳ )x − x̄ky − ȳ k≤ 0,l ∈ Lk , k = 0, . . . , i − 1,

(FOAi )x ∈ X, y ∈ Y ∩ Zny ,where Lk ⊆ {1, . . . , m} is chosen as in Algorithm 1. The solution to this problem is denoted as(x̂i , ŷ i ). In (FOAi ), the original objective function has been replaced by the L1 -distance of y toȳ i−1 . In the first iteration, ȳ 0 corresponds to the solution of the continuous relaxation (rMINLP)
of (MINLP). However, in the following iterations, ȳ i−1 is given by the solution of the following
nonlinear program for the feasibility pump:
min ky − ŷ i−1 k22 ,
x,y

s.t.

g(x, y) ≤ 0,

(FP-NLPi )x ∈ X, y ∈ Y.
The solution of this problem is denoted as (x̄i , ȳ i ). If ȳ i ∈ Zny , a feasible solution for (MINLP)
has been found.
6

Bonami et al. [6] have shown on an example that this basic algorithm can cycle ((x̄i−1 , ȳ i−1 ) =(x̄ , ȳ i )) if the linear independence constraint qualification is not satisfied. A possibility to avoid
this cycling is to add the cut(ȳ i − ŷ i−1 )> (y − ȳ i ) ≥ 0(1)i

to (FOAi ). Since (FP-NLPi ) projects the solution ŷ i−1 onto the convex set {y ∈ Y : ∃x ∈ X :g(x, y) ≤ 0}, the cut (1) outer-approximates the feasible region of (MINLP) and is violated byŷ i−1 (unless ȳ i = ŷ i−1 , in which case (x̄i , ȳ i ) is a feasible solution for (MINLP)). Thus, adding it
to (FOAi ) avoids revisiting ŷ i−1 . This algorithm is denoted as enhanced Feasibility Pump in [6]and has been shown to find a feasible solution to (MINLP) or prove that none exist in a finite
number of iterations, if assumptions (A1) and (A2) are satisfied.
To find further (and better) feasible solutions, the feasibility pump can be applied iteratively,
thereby excluding solutions for which the (linearized) objective function has a worse value thanthe best known value. This is achieved by the following modification to (FOAi ):min ky − ȳ i−1 k1 ,x,y

x − x̄ks.t. f (x̄ , ȳ ) + ∇f (x̄ , ȳ )≤ α,y − ȳ kx − x̄kgl (x̄k , ȳ k ) + ∇gl (x̄k , ȳ k )>≤ 0,y − ȳ k
k

k

k

k >



k = 0, . . . , i − 1,l ∈ Lk , k = 0, . . . , i − 1,α ≤ Z U − δ,x ∈ X, y ∈ Y ∩ Zny , α ∈ R.
The variable α is initially unbounded (Z U = ∞). When a new incumbent is found, Z U is updated
to the value of the original objective function in the incumbent. The small positive constantδ ensures that the incumbent becomes infeasible in (FP-OAi ) and enforces the search for an
improved solution. If (MINLP) is feasible, (A2) and (A3) are satisfied, and the linear independence
constraint qualificiation holds for (FP-NLPi ) at (x̄i , ȳ i ), then this iterative algorithm finds a
δ-optimal solution [6].

3Proposed Algorithm

While the main focus of the outer-approximation algorithm is to find an optimal solution andproving its optimality, the feasibility pump algorithm mostly disregards the original objectivefunction and focuses primarily on simultaneously minimizing violation of integrality and nonlinear
constraints. Therefore, the outer-approximation algorithm may take longer to find feasible solutions
on problems where feasible solutions are difficult to find, while the (iterative) feasibility pumpalgorithm may take longer to find a (proven) optimal solution on problems with many feasible
points. To alleviate and explore the differences between these algorithms, hybrid algorithms havebeen designed, the first one being in [6]. In [6], the feasibility pump algorithm is called when the
NLP subproblem (NLPi ) is found to be infeasible.
For DICOPT, we implemented a variation of this hybrid algorithm. Instead of starting thefeasibility pump for one or several times within the outer-approximation algorithm, we run theiterative feasibility pump once before the main outer-approximation loop starts. Furthermore, weslightly modified the feasibility pump algorithm in the following way.
A drawback of neglecting the original objective function in the feasibility pump algorithm asstated in Section 2.3 is that although it may be successful in finding feasible solutions, the qualityof solutions in terms of the objective function value can be poor [1]. Therefore, as in [6], after
finding a feasible solution by means of solving (FP-NLPi ), we try to improve it further by solving
the NLP subproblem obtained from fixing all integer variables in (MINLP) to the values in thesolution of (FP-NLPi ) (that is, we solve (NLPi ) with ŷ i replaced by ȳ i ).
Another problem arises from the possibility of repeating the same values in the integer variables(ŷ i−1 = ŷ i ), either due to cycling or when several feasible solutions with the same values in the7integer variables exist. The former is avoided by adding the cut (1), if ȳ i 6= ŷ i−1 , as proposedby [6]. If, however, ȳ i = ŷ i−1 , then a feasible solution for (MINLP) has been found and we can
add the integer cut ky − ŷ i k ≥ 1. With δ > 0, this would not be necessary to ensure progress inthe search for an improving solution. However, we observe that in certain instances adding this cut
accelerates the search. Since the linearization of integer cuts may require additional variables if
general integer variables are present (see Appendix A), integer cuts are by default only added formixed-binary problems (Y = [0, 1]ny ). To summarize, the MIP projection problem that we solve isthe following:
min ky − ȳ i−1 k1 ,
x,y

s.t.


x − x̄k≤ α,y − ȳ kx − x̄kgl (x̄k , ȳ k ) + ∇gl (x̄k , ȳ k )>≤ 0,y − ȳ kf (x̄k , ȳ k ) + ∇f (x̄k , ȳ k )>ky − ȳ k k1 ≥ 1,l ∈ Lk , k = 0, . . . , i − 1,

(FP-OAi )k ∈ C i,(ȳ k − ŷ k )> (y k − ȳ k ) ≥ 0,
U

k = 0, . . . , i − 1,

k = 1, . . . , i − 1,U

α ≤ Z − δ max(|Z |, 1),x ∈ X, y ∈ Y ∩ Zny , α ∈ R.
Finally, similar to (FP-OAi ), we add the constraint f (x, y) ≤ Z U −δ max(|Z U |, 1) to (FP-NLPi )in order to avoid non-improving solutions.
When the feasibility pump terminates, the outer-approximation algorithm is initialized not onlyby the best solution that the feasibility pump may have found, but also with the linearizations,
integer cuts, and cuts (1) that have been added to (FP-OAi ). However, regarding the cuts (1),only those generated before the last incumbent solution has been found can be used to initialize
the outer-approximation algorithm, since subsequent cuts were generated with respect to theadditional constraint f (x, y) ≤ Z U − δ max(|Z U |, 1), which may cut off an optimal solution (x∗ , y ∗ )if Z U − δ max(|Z U |, 1) < f (x∗ , y ∗ ) < Z U .
A general outline of the proposed algorithm is given in Algorithm 2. Up until Line 27 of
Algorithm 2, the algorithm is similar to the Iterated Feasibility Pump (IFP) for MINLP proposedin [6]. The main differences with the IFP are the optional inclusion of the integer cuts and thesolution of problem (NLPi ) in Line 19. Therefore, we can argue that executing lines 1–27 of
Algorithm 2 with imax = ∞ finds a δ-optimal (δ > 0) solution to (MINLP), or proves that none
exist if assumptions (A2) and (A3) are satisfied (see Theorem 2 in [6]). To find an optimal solution(δ = 0), if any exists, integer cuts need to be generated also if general integer variables are present.
To be able to add these in linear form, also Assumption (A1) needs to be satisfied.
Contrary to the Enhanced Outer Approximation method presented by Bonami et al. [6], whichruns the feasibility pump both as starting procedure and when the NLP subproblem (NLPi ) is
infeasible, we are employing the feasibility pump only once and before the outer-approximation
algorithm implemented in DICOPT. This is motivated by the fact that the MIP (FP-OAi ), which
is built by the feasibility pump, provides a valid relaxation for the convex MINLP. Therefore,
the feasibility pump does not only provide an initial feasible solution if successful, but also an
initialization of the MIP relaxation (rMIPi ) in any case.
Algorithm 2 has been implemented as part of the solver DICOPT and is available in GAMS
since version 25.1 (an earlier version without cuts (1) is available since GAMS 24.5). To enable
and adjust the algorithm, a number of options were added, which are summarized in Table 1. As
DICOPT is often used for nonconvex MINLPs, as commented in Section 2.2, the default values for
options convex and feaspump are 0.

8

Algorithm 2 Proposed algorithm.
1: Set Z U = ∞, i = 0. Initialization
2: Define cutoff decrease δ ≥ 0
3: Solve (rMINLP). Solve initial relaxation
4: if (rMINLP) is infeasible then5:
Stop
. (MINLP) is infeasible
6: Let (x̄0 , ȳ 0 ) be an optimal solution of (rMINLP)
7: Set L0 = {1, . . . , m}, C 0 = ∅8: Set Z L = f (x̄0 , ȳ 0 )9: if ȳ 0 ∈ Zny then10:
Set Z U = f (x̄0 , ȳ 0 ). Optimal solution found
11:Stop
12: Set i = 1
13: Solve (FP-OAi ). Solve feasibility OA problem
14: while (FP-OAi ) is feasible and i ≤ imax do
15:
Let (x̂i , ŷ i ) be an optimal (or feasible if unbounded) solution of (FP-OAi )16:
Solve (FP-NLPi ). Solve nonlinear feasibility problem
17:
Let (x̄i , ȳ i ) be an optimal solution of (FP-NLPi )18:
if kȳ i − ŷ i k = 0 then19:
Solve (NLPi ). Solve nonlinear subproblem
20:
Let x̄i be an optimal solution of (NLPi )21:
Set Z U = min(Z U , f (x̄i , ȳ i )). New incumbent solution
22:
Set C i+1 = C i ∪ {i} (if y ∈ {0, 1}ny in (MINLP))
23:
else
24:
Set C i+1 = C i
25:
Set Li = {j ∈ {1, . . . , m} : gj (x̄i , ȳ i ) ≥ 0 and gj is nonlinear}26:
Set i = i + 1
27:
Solve (FP-OAi ). Solve feasibility OA problem
28: Solve (MINLP) using DICOPT’s modification of Alg. 1, initialized with incumbent solution(x̄i , ȳ i ), if Z U < ∞, and linearizations given by L0 , · · · , Li , integer cuts given by C i , and cuts
(1) in the relaxation (rMIPi ).

4

Computational results

In the following, we evaluate the benefits of adding the feasibility pump to DICOPT on a setof convex MINLPs selected from MINLPLib (version c0f77612, as of 13.3.2018)2 [22]. First,
we selected all instances that are marked as convex, are not proven to be infeasible, have atleast one binary or general integer variable, no semi-continuous or semi-integer variables, and no
special-ordered-sets. This gives a set of 359 instances. Second, we run DICOPT with the convex
option enabled, and the feasibility pump disabled, and removed all instances for which DICOPT
terminated in less than one second. In this remaining set, a strong dominance of some subsets of
instances that were clearly derived from the same model (strong similarity in name) was observed.
Therefore, we reduced these subsets to the four largest instances. This leaves a final set of 80
instances, which have their origin in a wide variety of applications, ranging from process synthesis
flowsheets, facilities layout problems, batch design with storage, water treatment models, andinvestment portfolios. Table 1 in the Supplemental material provides this list of instances.
For all the experiments, we used a time limit of 1800 seconds and set the GAMS gap tolerance
optcr (relative distance of Z L and Z U ) to 10−5 . GAMS 25.1.1 was run on a cluster of Dell
PowerEdge M620 blades with 64 GB RAM, Intel Xeon E5-2680 CPUs running at 2.70 GHz, andLinux 4.4.0 (64bit). With this GAMS version, DICOPT uses CPLEX 12.8.0.0 for solving the MIPs,
2 http://www.minlplib.org

9

Optionconvexfeaspump
fp iterlimit
fp timelimit
fp sollimit
fp stalllimit

fp cutoffdecr
fp acttol
fp projzerotol
fp mipgap
fp transfercuts
fp integercuts
fp projcuts

Table 1: Feasibility pump options in DICOPT
Description
If enabled, then the default values for the following options
are changed to be more appropriate for convex MINLPs, seealso Section 2.2: option stop is set to 1, option infeasderis set to 1, and option feaspump is set to 1
Whether to run the feasibility pump
Major iteration limit (imax ) in the feasibility pumpTime limit in the feasibility pump
Limit on number of (improving) solutions found by thefeasibility pump
Limit on the number of consecutive iterations where no
improving solution is found. Only applies after a firstsolution has been found.
Relative decrease of cutoff value for objective variable (δ)
Tolerance on when a constraint is found active
Tolerance on when to consider the difference kȳ i − ŷ i k as
zero
Optimality tolerance (relative gap) when solving (FP-OAi )Whether to transfer cuts from the feasibility pump MIP tothe DICOPT MIP
Whether to add integer cuts to (FP-OAi ) when finding a
new feasible solution
Whether to add cuts (1) to (FP-OAi ) after solving(FP-NLPi )Default
0

0
20
∞
∞
5

0.1
10−6
10−4
0.01
1
1
1

and CONOPT 3.17I for solving the NLPs. We used PAVER 2 [7] to help in the evaluation.

4.1

Illustrative example

Before evaluating the performance of the new feasibility pump on the complete test set, we discuss
its behavior for a single instance. This instance corresponds to the block layout design problem
with unequal areas. The original problem was proposed by Meller et al. [20] and was reformulated
by Castillo et al. [8] as a convex MINLP. This type of problems may be applied in piping design
problems and in process plants layouts. The complete formulation of this model is reported
in [8]. The test case selected was the block layout design problem of 7 departments and withan aspect ratio (the maximum permissible ratio between its longest and shortest dimensions) of
5. The problem involves 211 constraints, of which 14 are nonlinear, specifically signomial, and
114 variables, of which 42 are binary. This instance can be found in MINLPLib under the nameo7 23 . The authors of the model used several MINLP solvers to find the optimal solution to thisproblem, among them DICOPT. DICOPT performed very poorly because the linearizations in theinitial outer-approximation (rMIPi ) were not helpful and many nonlinear subproblems (NLPi ) are
infeasible [8].
The given instance was tested using different options for DICOPT. The stopping criterion for all
the different options was closing the gap between the objective values of the MIP master problem
and the incumbent solution. The default setting for option infeasder requires that if the nonlinear
subproblem (NLPi ) is infeasible, only a corresponding integer cut is added to (rMIPi ). Thisapproach, although rigorous for convex and non-convex MINLPs, is not very efficient, particularly
for this type of problems where “a significant amount of integer cuts may be required before
a feasible solution is obtained” [8]. For convex MINLPs another rigorous approach is to add
3 http://www.minlplib.org/o7_2.html

10Table 2: Results of the solution of the illustrative example o7 2 for each setting of DICOPT.
DICOPT
w/o FP
w/o FPw/ FP
w/ FP
options
w/o infeasder w/ infeasder w/o infeasder w/ infeasdermajor iterations
feasible solutions foundFP iterations
FP time [s]infeasible NLPtime to optimal sol. [s]solution time [s]final objective value*Time limit reached.

113
0
0
0
112
–
> 1800*
–

7
1
0
0
5
676.6
915.5
116.95

2
5
12
199.4
0
417.3
620.9
116.95

2
5
12
200.1
0
418.4
621.2
116.95linearization cuts if the nonlinear subproblem is infeasible, using the solution of (NLP-feasi ) as areference point. This can be enabled by using the option infeasder, see Section 2.2. Note thatthe setting of the infeasder option does not influence the handling of infeasible NLPs within thefeasibility pump. A comparison of DICOPT on instance o7 2 with the feasibility pump and theinfeasder option enabled and disabled is given in Table 2.
We notice that DICOPT without feasibility pump and with infeasder disabled cannot find afeasible solution within 30 minutes. During this time the solver performed 113 major iterations.
That is, at each iteration, it solved a MIP master problem (rMIPi ) and an NLP subproblem (NLPi ).
All NLP subproblems were infeasible. Enabling the infeasder option, the problem could be solvedin 912 seconds. During this time, 5 out of the 6 solved NLP subproblems were infeasible. The
only feasible solution, found in the 7th iteration, was also an optimal solution to the problem. It
required another solution of the MIP to prove its optimality.
The use of the feasibility pump allowed the solver to find 4 feasible solutions in the first ≈ 200
seconds. After that, a single major iteration was required to find an optimal solution, which
required 217 seconds in both cases with and without the infeasder option. In that same major
iteration, optimality of the solution was proven. The results when using the feasibility pump withand without the infeasder option are the same (except for variations in time measurement) sincenone of the NLP subproblems (NLPi ) in the outer-approximation algorithm were infeasible.
These results highlight that first, enabling the infeasder option can be essential to solving aproblem or just finding a feasible solution. Second, the feasibility pump can further improve theperformance by finding feasible solutions early. That is, we obtained a 38% reduction in the timeneeded to find an optimal solution to the problem and a 32% reduction in the complete solution
time by enabling the feasibility pump. It is also interesting to note that when this problem issolved with AlphaECP it required 897 seconds, with BONMIN 756 seconds, and with SCIP 768
seconds. When running only the iterative feasibility pump algorithm of BONMIN [6], no feasible
solution is obtained before hitting the time limit of 30 minutes.

4.2

Feasibility pump alone

In the following, we consider the full test set of 80 instances. First, we run only our (iterative)
feasibility pump implementation with various settings, that is, without continuing with the outerapproximation algorithm of DICOPT. In setting “default”, the feasibility pump is run in its default
settings, see Table 1, that is, a stall limit of 5 and a cutoff decrease of δ = 0.1, except that theiteration limit has been disabled (imax = ∞). A stall limit of k iterations stops the feasibility
pump if, after a first solution has been found, no improving solution is found within the next kiterations. In setting “stall10”, we increased the stall limit to 10. In setting “no cuts (1)”, we
disabled the addition of cuts (1) to (FP-OAi ) after having solved the NLP projection problem(FP-NLPi ). Setting “no integer cuts” completely disables the addition of integer cuts when a new

11

Table 3: Results of running feasibility pump alone with different settings. For each setting, we show
the number of instances in which the feasibility pump reaches the time limit, found a δ-optimal
solution (without necessarily proving optimality), found a solution with primal gap ≤ 10%, found
any feasible solution, and the time used, respectively.
settingtimeout optimal good sol. feasible mean time [s]default
stall10no cuts (1)no integer cuts

4
4
5
4

12
14
13
13

57
64
55
60

77
77
76
77

9.1
11.4
9.6
9.8

findopt
findopt w/o integer cuts
findopt w/ all integer cuts

25
42
29

67
44
69

74
52
74

77
77
77

119.0
238.1
197.1

feasible solution has been found (C i+1 = ∅ in Line 22 of Algorithm 2). Finally, we evaluated threesettings that target to find δ-optimal solutions of the MINLP. For this, setting “findopt” disables
the stall limit and sets the cutoff decrease δ to 10−5 . Setting “findopt w/o integer cuts” additionallydisables the addition of integer cuts when a new solution is found, while setting “findopt w/ allinteger cuts” enables the addition of integer cuts also for problems with general integer variables.
Table 3 summarizes the results for all settings and detailed results are given in Tables B2 andB3 in the Supplemental material. The mean time in Table 3 reports the shiftedQ
geometric mean of180
the runtimes (t1 , . . . , t80 ) of the feasibility pump on all instances, computed as i=1 (ti + 1) 80 − 1.
Figure 1 plots the primal gap of all runs for settings “default”, “stall10”, and “findopt”. As primal
gap, we compute the relative distance between the objective function value of the best solution
found by the algorithm and the objective function value of the best known solution reported in
MINLPLib. We can observe that the feasibility pump in default settings finds an optimal solution
for 12 instances, good solutions (< 10% primal gap) for another 45 instances, and some feasible
solutions (≥ 10% primal gap) for another 20 instances. Increasing the stall limit helps on seven of
the instances where previously only bad solutions were found. On instances where good solutions
were already found in default settings, increasing the stall limit has an effect on one instance only,
likely since the cutoff decrease δ cuts off solutions that are only slightly better or optimal. However,increasing the stall limit also increases the mean running time by 25%. By using the “findopt”
setting, however, the feasibility pump is able to find optimal solutions for many instances wherepreviously a small gap was remaining.
For the runs with stall limit (“default” and “stall10”), the feasibility pump usually terminates
either when the MIP approximation (FP-OAi ) becomes infeasible or the stall limit is reached. In
the “findopt” setting, however, 25 instances terminated when the time limit of 1800 seconds wasreached. Thus, the feasibility pump is not suited to prove optimality of the found solutions. Thisjustifies the choice of the stall limit as a stopping criterion.
Disabling cuts (1) has a small negative impact on performance. Without this cut, the feasibility
pump fails to find a solution for instance tls7 within the allowed time, which then also leads to anincrease in the mean time. As noted by [6], cut (1) was not necessary in practice, though adding
it is unlikely to have a negative effect. Also disabling the integer cuts has little impact on theperformance. The number of instances with optimal and good solution increases slightly, but themean running time also increases slightly. However, disabling integer cuts in the ”findopt” setting
has a severe impact on the performance, since, without these cuts, only the cutoff decrease δ, which
is only 10−5 in this setting, is responsible to force the feasibility pump to look for better feasible
solutions. On instances with general integer variables, integer cuts are already disabled by default,
which is the reason why there is one instance (second instance in Figure 1) where the ”findopt”
setting produces a worse solution than ”default”. Hence, enabling integer cuts also for instanceswith general integer variables improves solution quality, at the cost of a considerably increased
running time.

12

0.7

default
stall10findopt

0.6

Primal gap

0.5

0.4

0.3

0.2

0.1

0
0

10

20

30

40

50

60

70

80

Instance

Figure 1: Primal gap of solutions found by feasibility pump (with different settings) for all instancesin test set, sorted by primal gap of “default” setting.

4.3

DICOPT with feasibility pump

We used DICOPT with the following settings: In the “DICOPT w/ FP” setting, the option convex
was enabled, which also enables the feasibility pump. In the “DICOPT w/o FP” setting, the option
convex was also enabled, but the feasibility pump disabled. In the “DICOPT w/ FP w/o OA
init” setting, option convex was again enabled, but the transfer of cuts from the feasibility pumpMIP (FP-OAi ) to the outer-approximation MIP (rMIPi ) has been disabled. Additionally, with“FP only” we consider the results from running only the feasibility pump without stall limit andcutoff decrease δ = 10−5 (“findopt” setting in Section 4.2).
Table 4 summarizes for each setting the number of instances for which the time limit wasreached, a δ-optimal solution was found, optimality was proven, a good solution was found (primal
gap ≤ 10%), and mean running time. Detailed results are given in Tables B3 and B4 in the
Supplemental material. Performance profiles are shown in Figures 2 and 3. The numbers showthat adding the feasibility pump to DICOPT leads to finding optimal solutions to three moreinstances than before and slightly reducing the mean running time, but does not affect the numberof instances for which optimality is proven. Running the feasibility pump alone increases thenumber of instances where optimal or good solutions are found and even decreases the meanrunning time, but decreases the number of instances where optimality is proven. That is, the best
performance in terms of finding proven optimal solutions can only be expected when combining
the feasibility pump as primal heuristic and outer-approximation to prove optimality. We also
note that the outer-approximation algorithm in DICOPT is targeted for general MINLPs, which
results in applying linearizations of nonlinear functions, also if convex, as soft-constraints only,
cf. Section 2.2. That is, tuning the implementation of the outer-approximation in DICOPT towork better in case of a convex MINLP might lead to achieving the best performance of DICOPT(with feasibility pump) also with regard to running time or finding good solutions.
One of the original motivations to add the feasibility pump to DICOPT was to use cuts from the
MIP projection problem (FP-OAi ) to warm-start the outer-approximation MIP (rMIPi ). As seenfrom Table 4, even though the solution quality does not decrease when disabling the initializationof (rMIPi ), one can observe that the additional time that is spent for running the feasibility pumppays off only if also the cuts from (FP-OAi ) are transferred to (rMIPi ).

13

setting

Table 4: Results of running DICOPT with different settings.
timeout optimal optimal w/ proof good sol.

DICOPT w/ FP
DICOPT w/o FP
FP only
DICOPT w/ FP w/o OA init

5

31
31
25
31

58
55
67
59

48
48
30
49

67
62
74
68

mean time
137.9
140.8
119.0
170.5

Conclusions and perspectives

This paper has addressed the solution of convex MINLPs using the commercial solver DICOPT.
Based on the work of Bonami, Cornuéjols, Lodi, and Margot [6], a modified iterative feasibility
pump algorithm as a preprocessing for DICOPT has been proposed and implemented. As seen in
the illustrative example, DICOPT in default settings has shown to perform poorly when many of
the nonlinear subproblems are infeasible. Solving the illustrative example using DICOPT withthe feasibility pump, better performance in solution time and solution quality could be achieved.
As seen in the results from Section 4.2, the feasibility pump is not efficient in proving optimality,
which validates the use of a stall limit as the criterion when to switch from the feasibility pump to
the outer-approximation algorithm.
If the feasibility pump is used as primal heuristic only, the quality of the found solutions is
improved, but the running time of DICOPT is increased considerably. Only when additionally thecuts from the MIP projection problem of the feasibility pump are used to initialize the MIP of theouter-approximation algorithm, improvements can be achieved with respect to DICOPT without
feasibility pump in terms of both solution quality and running time.
Further work to improve the feasibility pump implementation in DICOPT is motivated by
the following observations. Achterberg and Bethold [1] proposed a modification to the originalalgorithm that includes some information about the original objective function in the objectivefunction of the feasibility pump problems to mitigate the issue of finding poor feasible solutionsin terms of the original objective. Further, currently, the feasibility pump is only run at the
beginning of DICOPT before the main loop of the outer-approximation algorithm. Executing it
only once has been sufficient to find good feasible solutions for many instances in our test set.
However, for some instances, it may be worth investigating a more extensive integration of thefeasibility pump into DICOPT, e.g., allowing it to be used also when infeasible NLP subproblems
are encountered in a similar manner as proposed by Bonami et al. [5]. Finally, the feasibility
pump implementation should be generalized to nonconvex MINLP problems. Several authors haveproposed such extensions [4, 9]. DICOPT itself already has heuristics to deal with nonconvex
MINLPs, see Section 2.2, which could be carried over to the feasibility pump implementation.

Funding
The first and fourth authors would like to acknowledge financial support from the Center for
Advanced Process Decision-making (CAPD). The second author was supported by the ResearchCampus MODAL Mathematical Optimization and Data Analysis Laboratories funded by theGerman Federal Ministry of Education and Research (BMBF Grant 05M14ZAM).

References[1] Tobias Achterberg and Timo Berthold. Improving the feasibility pump. Discrete Optimization,
4(1):77–86, 2007. doi:10.1016/j.disopt.2006.10.004.
[2] Egon Balas and Robert Jeroslow. Canonical cuts on the unit hypercube. SIAM Journal on
Applied Mathematics, 23(1):61–69, 1972. ISSN 0036-1399. doi:10.1137/0123007.
14

[3] Livio Bertacco, Matteo Fischetti, and Andrea Lodi.
A feasibility pump heuristic for general mixed-integer problems.
Discrete Optimization, 4(1):63–76, 2007.
doi:10.1016/j.disopt.2006.10.001.
[4] Timo Berthold. Heuristic algorithms in global MINLP solvers. PhD thesis, TU Berlin, 2014.
[5] Pierre Bonami, Lorenz T. Biegler, Andrew R. Conn, Gérard Cornuéjols, Ignacio E. Grossmann,
Carl D. Laird, Jon Lee, Andrea Lodi, François Margot, Nicolas Sawaya, and Andreas Wächter.
An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization,
5(2):186–204, 2008. doi:10.1016/j.disopt.2006.10.011.
[6] Pierre Bonami, Gérard Cornuéjols, Andrea Lodi, and François Margot. A Feasibility Pump
for mixed integer nonlinear programs. Mathematical Programming, 119(2):331–352, 2009.
doi:10.1007/s10107-008-0212-2.
[7] Michael R. Bussieck, Steven P. Dirkse, and Stefan Vigerske. PAVER 2.0: an open source
environment for automated performance analysis of benchmarking data. Journal of Global
Optimization, 59(2-3):259–275, jul 2014. doi:10.1007/s10898-013-0131-5.
[8] Ignacio Castillo, Joakim Westerlund, Stefan Emet, and Tapio Westerlund. Optimization of block layout design problems with unequal areas: A comparison of MILP and
MINLP optimization methods. Computers & Chemical Engineering, 30(1):54–69, 2005.
doi:10.1016/j.compchemeng.2005.07.012.
[9] Claudia D’Ambrosio, Antonio Frangioni, Leo Liberti, and Andrea Lodi. A storm of feasibility pumps for nonconvex MINLP. Mathematical Programming, 136(2):375–402, 2012.
doi:10.1007/s10107-012-0608-x.
[10] Elizabeth D. Dolan and Jorge J. Moré. Benchmarking optimization software with performance
profiles. Mathematical Programming, 91(2):201–213, 2002. doi:10.1007/s101070100263.
[11] Marco A. Duran and Ignacio E. Grossmann. An outer-approximation algorithm for aclass of mixed-integer nonlinear programs. Mathematical Programming, 36(3):307–339, 1986.
doi:10.1007/BF02592064.
[12] Matteo Fischetti, Fred Glover, and Andrea Lodi. The feasibility pump. Mathematical
Programming, 104(1):91–104, 2005. doi:10.1007/s10107-004-0570-3.
[13] Roger Fletcher and Sven Leyffer. Solving mixed integer nonlinear programs by outer approximation. Mathematical Programming, 66(1-3):327–349, 1994. doi:10.1007/BF01581153.
[14] Björn Geißler, Antonio Morsi, Lars Schewe, and Martin Schmidt. Penalty alternating direction
methods for mixed-integer optimization: A new view on feasibility pumps. SIAM Journal on
Optimization, 27(3):1611–1636, 2017. doi:10.1137/16M1069687.
[15] Ignacio E. Grossmann and Zdravko Kravanja. Mixed-Integer Nonlinear Programming: A surveyof algorithms and applications. In Lorenz T. Biegler, Thomas F. Coleman, Andrew R. Conn,and Fadil N. Santosa, editors, Large-Scale Optimization with Applications: Part II: Optimal
Design and Control, pages 73–100. Springer New York, 1997. doi:10.1007/978-1-4612-1960-6 5.
[16] Ignacio E. Grossmann and Jon Lee. Cyberinfrastructure for mixed-integer nonlinear programming. SIAG/OPT Views-and-News, 22(1):8–12, 2011. URL http://www.minlp.org.
[17] Ignacio E Grossmann, Jagadisan Viswanathan, Aldo Vecchietti, Ramesh Raman, and Erwin
Kalvelagen. GAMS/DICOPT: A Discrete Continuous Optimization Package, 2002.
[18] G. R. Kocis and I. E. Grossmann. Computational experience with DICOPT solving MINLP
problems in process systems engineering. Computers & Chemical Engineering, 13(3):307–315,
1989. doi:10.1016/0098-1354(89)85008-2.
15[19] Jon Lee and Sven Leyffer, editors. Mixed Integer Nonlinear Programming, volume 154 of The
IMA Volumes in Mathematics and its Applications. Springer, 2012. doi:10.1007/978-1-46141927-3.
[20] Russell D Meller and Kai-Yin Gau. The facility layout problem: Recent and emerging trends
and perspectives. Journal of Manufacturing Systems, 15(5):351–366, 1996. doi:10.1016/02786125(96)84198-7.
[21] Francisco Trespalacios and Ignacio E. Grossmann. Review of mixed-integer nonlinear andgeneralized disjunctive programming methods. Chemie Ingenieur Technik, 86(7):991–1012,
2014. doi:10.1002/cite.201400037.
[22] Stefan Vigerske. MINLPLib 2. In L. G. Casado, I. Garcı́a, and E. M. T. Hendrix, editors,
Proceedings of the XII global optimization workshop MAGO 2014, pages 137–140, 2014.
[23] J. Viswanathan and I. E. Grossmann. A combined penalty function and outer-approximation
method for MINLP optimization. Computers & Chemical Engineering, 14(7):769–782, 1990.
doi:10.1016/0098-1354(90)87085-4.

A

Linearization of integer cut

For a point ȳ ∈ Y , consider the integer cut
ky − ȳk1 ≥ 1.

(2)

Recall that Y = [y L , y U ] with y L , y U ∈ Zny (due to (A1)). A linear formulation of (2) is easilyfound if ȳj ∈ {yjL , yjU } for every j ∈ J := {1, . . . , ny }, since the absolute difference |yj − ȳj | isreduced to yj − yjL , if ȳj = yjL , and yjU − yj otherwise. Thus, for the specific case of binary variables
only, i.e., yjL = 0, yjU = 1, j ∈ J, (2) simplifies to
X

yj −

j∈J L

X

(1 − yj ) ≥ 1.

j∈J U

In the general case, we partition the set J into
J L = {j ∈ J : ȳj = yjL },J U = {j ∈ J : ȳj = yjU },J M = J \ (J L ∪ J U ).
Using this set partition, the absolute difference of the variables to a given solution can be expressed
as a sum of three terms. Thus, the integer cut (2) can be written asXXX(yj − yjL ) +(yjU − yj ) +|yj − ȳj | ≥ 1.
j∈J L

j∈J U

j∈J M

For every j ∈ J M , we introduce a binary variable vj , which determines whether the variable
yj is greater than or less than ȳj , and a positive continuous variable wj to represent the value|yj − ȳj |. This can be expressed using the following disjunctions: 
vj = 0vj = 1∨
 , j ∈ JM.
yj ≤ ȳjyj ≥ ȳjwj = ȳj − yj
wj = yj − ȳj16This disjunction can be reformulated into mixed-integer linear form, which yields the following
reformulation of (2):X
X
X
(yj − yjL ) +(yjU − yj ) +wj ≥ 1,
j∈J L

j∈J U

j∈J M

− wj ≤ yj − ȳj ≤ wj ,j ∈ JM,wj ≤ yj − ȳj + Mj1 (1 − vj ),j ∈ JM,wj ≤ ȳj − yj + Mj2 vj ,j ∈ JM,wj ≥ 0,j ∈ JM,vj ∈ {0, 1},j ∈ JM.

To avoid weak relaxations, the big-M constants Mj1 and Mj2 should be chosen as small as possible
and such thatyj − ȳj + Mj1 ≥ wj = ȳj − yj∀yj ∈ [yjL , ȳj ](case vj = 0 → yj ≤ ȳj ),ȳj − yj + Mj2 ≥ wj = yj − ȳj∀yj ∈ [ȳj , yjU ](case vj = 1 → yj ≥ ȳj ).

Thus, Mj1 = 2(ȳj − yjL ) and Mj2 = 2(yjU − ȳj ).

B

Performance Profiles

Figure 2 shows performance profiles [10] comparing DICOPT with and without feasibility pumpand the feasibility pump alone. Figure 3 shows a performance profile that illustrates the effect of
disabling the initialization of (rMIPi ) with the cuts from (FP-OAi ).

Number of instances

proven optimal

optimal solution found

80

80

60

60

40

40

20

0
100

DICOPT w/ FP
DICOPT w/o FP
FP only
101

102

20

0
100

Time at most this factor to fastest

DICOPT w/ FP
DICOPT w/o FP
FP only
101

102

Time at most this factor to fastest

Figure 2: Performance profile showing the number of instances solved to proven optimality (left)
and where an optimal solution has been found (right), respectively, with respect to solution timefor various DICOPT settings.

17

Number of instances

80

60

40

20
DICOPT w/ FP
DICOPT w/ FP w/o OA init
0
100

100.2

100.4

100.6

100.8

101

101.2

Time at most this factor to fastest

Figure 3: Performance profile showing the number of instances solved to proven optimality withrespect to solving time, with and without the initialization of (rMIPi ) with the cuts from thefeasibility pump.

18