Solving mixed-integer
nonlinear programming
(MINLP) problems
Marcel Hunting
AIMMS Optimization Specialist
Webinar, June 15, 2016
Overview
> Introduction
> MINLP solvers
> Algorithms used by solvers
> Improving model formulation (preprocessing, linearizations)
> Troubleshooting
2
Mixed-Integer Nonlinear Program
minimize f(x,y)
subject to gj(x,y) ≤ 0 j∈J
Ax + By ≤ b
x continuous
y integer
Important special cases:
Convex MINLP: f and gj are convex
MIQP: f is quadratic and gj are linear
MIQCP: gj are quadratic or second-order cone (and f is linear
or quadratic)
MISOCP
3
MINLP solvers (+ linear solvers)
Problem class First choice Second choice
Convex MIQP CPLEX, Gurobi AOA, BARON, Knitro
Convex MIQCP CPLEX, Gurobi AOA, BARON, Knitro
Convex MINLP AOA BARON, Knitro
Non-convex MIQP AOA, BARON, Knitro, CPLEX
Non-convex MINLP* AOA, BARON, Knitro
*: Including Non-convex MIQCP
CPLEX and Gurobi are linear solvers
BARON is a global nonlinear solver
AOA and Knitro are local nonlinear solvers
4
MINLP solvers (+ linear solvers)
Problem class First choice Second choice
Convex MIQP CPLEX, Gurobi AOA, BARON, Knitro
Convex MIQCP CPLEX, Gurobi AOA, BARON, Knitro
Convex MINLP AOA BARON, Knitro
Non-convex MIQP AOA, BARON, Knitro, CPLEX
Non-convex MINLP AOA, BARON, Knitro
Global optimum
CPLEX and Gurobi are linear solvers
BARON is a global nonlinear solver
AOA and Knitro are local nonlinear solvers
4
Algorithms used by Solvers
Solver Algorithm
AOA Outer Approximation, Quesada-Grossmann OA
BARON Spatial Branch-and-Bound
Knitro Branch-and-Bound, Quesada-Grossmann OA, MISQP
CPLEX Branch-and-Cut, McCormick Relaxation Branch-and-Bound
Gurobi Branch-and-Cut
5
Algorithms used by Solvers
Solver Algorithm
AOA Outer Approximation, Quesada-Grossmann OA
BARON Spatial Branch-and-Bound
Knitro Branch-and-Bound, Quesada-Grossmann OA
CPLEX Branch-and-Cut, McCormick Relaxation Branch-and-Bound
Gurobi Branch-and-Cut
5
Spatial Branch-and-Bound
Objective
Region S1 Region S2
Variable
6
Spatial Branch-and-Bound
Objective
Region S1 Region S2
S1 upper
bound
S2 upper
bound
S1 lower
bound
S2 lower Variable
bound
6
Outer Approximation
add integer
elimination
constraints
7
Outer Approximation: Example
max 0.5 x + y
s.t. (x-1)2 + y2 ≤ 3
x ∈ [0,3]
y ∈ {0..2}
8
Outer Approximation: Example
NLP 0
Solve NLP relaxation
8
Outer Approximation: Example
NLP 0
Add linearization to Master MIP
8
Outer Approximation: Example
NLP 0
MIP 1
Solve Master MIP
8
Outer Approximation: Example
NLP 0
NLP 1 MIP 1
Fix y = 1 and solve NLP
8
Outer Approximation: Example
NLP 0
NLP 1 MIP 1
Add linearization to Master MIP
8
Outer Approximation: Example
MIP 2
NLP 0
NLP 1 MIP 1
Solve Master MIP
8
Outer Approximation: Example
MIP 2
NLP 2
NLP 0
NLP 1 MIP 1
Fix y = 2 and solve NLP: infeasible
8
Outer Approximation: Example
MIP 2
NLP 2
NLP 0
NLP 1 MIP 1
Add linearization to Master MIP
8
Outer Approximation: Example
MIP 2
NLP 2
NLP 0
NLP 1 MIP 1
MIP 3
Solve Master MIP
8
Outer Approximation: Example
MIP 2
NLP 2
NLP 0
NLP 1 MIP 1
MIP 3
NLP 3
Fix y = 0 and solve NLP
8
Outer Approximation: Example
MIP 2
NLP 2
NLP 0
NLP 1 MIP 1
MIP 3
NLP 3
Add linearization to Master MIP
8
AIMMS Presolver
> Delete redundant constraints & fixed variables
> Bounds Tightening
• Variable x: range [0,inf) range [10,55]
• Linear / nonlinear constraints
> Improve coefficients (“probing”)
> Linearize quadratic constraints
9
Linearize constraints – Example 1
> Initial constraint:
Y = sum[ j, sqrt( p(j) * sum( i, X(i,j) * q(i) ) ]
Here X(i,j) is a binary variable such that X(i,j) = 0 if i <> j
> Remark: You can use X(i) instead of X(i,j)
> Step 1: Y = sum[ j, sqrt( p(j) * X(j,j) * q(j) ) ]
> Step 2: Y = sum[ j, X(j,j) * sqrt( p(j) * q(j) ) ]
10
Linearize constraints – Example 2
> Initial constraints (0 ≤ X(i) ≤ u):
sum( i, Y(i) ) ≥ 1 X(i) 3 7 5
Y(i) 0 1 0
Z = max( i, X(i) )
Y(i) = if ( X(i) = Z ) then 1 else 0 endif; ∀i
> Reformulation:
sum( i, Y(i) ) ≥ 1
Z ≥ X(i) ∀i
X(i) ≥ Z + (1-Y(i)) * u ∀i
11
Troubleshooting
> Solver returns Infeasible
• Look for errors & warnings (e.g. derivative evaluation errors)
• Check solver log/status file
• BARON: Infeasibility finder (option: Compute IIS)
• Display Infeasibility Analysis using AIMMS Presolver
• Remove nonlinear constraints; is MIP also infeasible?
GMP::Instance::CreateMasterMIP
• Reformulate (parts of) model
12
Troubleshooting AOA
> AOA returns Infeasible
• First MIP is infeasible: the linear problem obtained by removing all
nonlinear constraints is infeasible
• First MIP is unbounded: add finite upper and lower bounds for variables
• All NLP are infeasible: use multistart, switch NLP solver or increase
iteration limit
> AOA takes a long time
• Decrease iteration limit
• Increase value of option ‘MIP Relative Optimality Tolerance’
> AOA returns poor solution
• Use multistart, or call AOA for second time (better starting point)
13
(Dis)Advantages solvers
AOA BARON Knitro
+ Open algorithm + Global solver + Three algorithms
+ Combine with multistart + Find k best solutions + Tuning tool
+ We know it very well + Branching priorities + Branching priorities
− Algorithm not solver + Infeasibility finder + Several NLP algorithms
− No goniometric func. − Derivative errors
− Not in Free Academic − Not in Free Academic
License License
option: honor bounds
14
References
> AIMMS Language Reference
• The AIMMS OA algorithm for MINLP: Chapter 18
• AIMMS Presolver & Multistart: Chapter 17
> AIMMS Optimization Modeling
• Integer Linear Programming Tricks: Chapter 7
> White papers on website
• The AIMMS Outer Approximation Algorithm for MINLP (using GMP)
• Solving convex MINLP problems with AIMMS
15
References
> Webinars
• [Link]
• AIMMS Presolver
• Multistart
• Introduction to GMP
> Example: Water Distribution
• [Link]
• Generic Branch-and-Bound algorithm (GMP)
16