Global Optimization of Mixed-Integer Nonlinear Programs

Stefan Vigerske
Kyushu University · January 20, 2023

Outline
Introduction
Fundamental Methods
Mixed-Integer Linear Programming
Convex MINLP
Nonconvex MINLP
ExampleFurther Techniques
Dual Side (Tighter Relaxations)Primal Side (Find Feasible Solutions)
Solver Software
Solvers for Mixed-Integer Quadratic Programs
Solvers for Convex MINLP
Solvers for General MINLPIntroduction

Mixed-Integer Nonlinear Programs (MINLPs)

We consider

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z∀k ∈ [m]∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]The functions gk ∈ C 1 ([ℓ, u], R) can be
0
200

10

100

200

5

−1

convex

0

or

−1

300
200

0

−200

1
1

nonconvex

Examples of Mixed-Integer Nonlinearities• Water treatment unit - variable fraction p ∈ [0, 1] of variable quantity q: qp, andvalve on/off state z ∈ {0, 1}• AC power flow - nonlinear function of voltage magnitudes and angles and binary
decisions on switching status of power lines
pij = gij vi2 − gij vi vj cos(θij ) + bij vi vj sin(θij )• Circle packing - non-overlap constraints∥x − y ∥2 ≥ rx + ry
• etc.

Solving a Mixed-Integer Nonlinear Optimization Problem

Two major tasks:
1. Finding and improving feasible solutions (primal side)• Ensure feasibility, sacrifice optimality• Important for practical applications

2. Proving optimality (dual side)• Ensure optimality, sacrifice feasibility• Necessary in order to actually solve the problem

Connected by:
3. Strategy• Ensure convergence• Divide: branching, decompositions, ...
• Put together all components

Adding Nonlinearity to a MIP Brings New Challenges• More numerical issues• NLP solvers are less efficient and reliable than LP solvers
1. Finding feasible solutions• Feasible solutions must also satisfy nonlinear constraints• If nonconvex: fixing integer variables and solving the NLP can produce local optima

2. Proving optimality• NLP or LP relaxations?
• If nonconvex: continuous relaxation no longer provides a lower bound• "Convenient" descriptions of the feasible set are important

3. Strategy• Need to account for all of the above• Warmstart for NLP is much less efficient than for LP→

Solving MINLPs

Convex MINLP:• Main difficulty: Integrality restrictions on variables• Main challenge: Integrating techniques for MIP (branch-and-bound) and NLP(SQP, interior point, Kelley’s cutting plane, . . . )Solving MINLPs

Convex MINLP:• Main difficulty: Integrality restrictions on variables• Main challenge: Integrating techniques for MIP (branch-and-bound) and NLP(SQP, interior point, Kelley’s cutting plane, . . . )General MINLP = Convex MINLP plus Global Optimization:• Main difficulty: Nonconvex nonlinearities• Main challenges:• Convexification of nonconvex nonlinearities• Reduction of convexification gap (spatial branch-and-bound)• Numerical robustness• Diversity of problem class: MINLP is “The mother of all determinstic optimization
problems” (Jon Lee, 2008)

Fundamental Methods

Fundamental Methods
Mixed-Integer Linear Programming

MIP Branch & Cut

For mixed-integer linear programs (MIP), that is,
min c T x,
s.t. Ax ≤ b,xi ∈ Z,i ∈ I,

the dominant method of Branch & Cut combines
3

2

&

1

1

2

3

cutting planes[Gomory, 1958]

4

branch-and-bound[Land and Doig, 1960]

Fundamental Methods
Convex MINLPRelaxations

Key task: describe the feasible set in a convenient way.
Requirement: the relaxed problem should be efficiently solvable to global optimality.
It is preferable to have relaxations that are:• Convex: NLP solutions are globally optimal, infeasibility detection is reliable• Linear: solving is more efficient, good for warmstarting
and to avoid:• Very large numbers of constraints and variables• Bad numerics

Relaxations for Convex MINLPs• Relax integrality → NLP relaxation→• Replace nonlinear set with linear outer approximation → MIP relaxation• Linear outer approximation + relax integrality → LP relaxation

NLP-based Branch & Bound (NLP-BB)⇒
MIP branch-and-bound[Land and Doig, 1960]

MINLP branch-and-bound[Leyffer, 1993]

Bounding: Solve convex NLP relaxation obtained by dropping integrality requirements.
Branching: Subdivide problem along variables xi , i ∈ I, that take fractional value in
NLP solution.

NLP-based Branch & Bound (NLP-BB)⇒
MIP branch-and-bound[Land and Doig, 1960]

MINLP branch-and-bound[Leyffer, 1993]

Bounding: Solve convex NLP relaxation obtained by dropping integrality requirements.
Branching: Subdivide problem along variables xi , i ∈ I, that take fractional value in
NLP solution.
• However: Robustness and Warmstarting-capability of NLP solvers not as good as
for LP solvers (simplex alg.)⇒ Mahajan, Leyffer, and Kirches [2012]: approximate NLP solves by QPs (hot-startpossible)Reduce Convex MINLP to MIP

Assume all functions gk (·) of MINLP are convex on [ℓ, u].
Duran and Grossmann [1986]: MINLP and thefollowing MIP have the same optimal solutions

Example:min x + ys.t. (x, y ) ∈ ellipsoid

min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,k ∈ [m],xi ∈ Z,x̂ ∈ R,i ∈ I,x ∈ [ℓ, u],where x̂ ∈ R are the solutions of the NLP
subproblems obtained from MINLP by applying any
possible fixing for xI , i.e.,
min c T x s.t. g (x) ≤ 0, x ∈ [ℓ, u], xI fixed.

x ∈ {0, 1, 2, 3}y ∈ [0, 3]

Reduce Convex MINLP to MIP

Assume all functions gk (·) of MINLP are convex on [ℓ, u].
Duran and Grossmann [1986]: MINLP and thefollowing MIP have the same optimal solutions

Example:min x + ys.t. (x, y ) ∈ ellipsoid

min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,k ∈ [m],xi ∈ Z,x̂ ∈ R,i ∈ I,x ∈ [ℓ, u],where x̂ ∈ R are the solutions of the NLP
subproblems obtained from MINLP by applying any
possible fixing for xI , i.e.,
min c T x s.t. g (x) ≤ 0, x ∈ [ℓ, u], xI fixed.

x ∈ {0, 1, 2, 3}y ∈ [0, 3]

Reduce Convex MINLP to MIP

Assume all functions gk (·) of MINLP are convex on [ℓ, u].
Duran and Grossmann [1986]: MINLP and thefollowing MIP have the same optimal solutions

Example:min x + ys.t. (x, y ) ∈ ellipsoid

min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,k ∈ [m],xi ∈ Z,x̂ ∈ R,i ∈ I,x ∈ [ℓ, u],where x̂ ∈ R are the solutions of the NLP
subproblems obtained from MINLP by applying any
possible fixing for xI , i.e.,
min c T x s.t. g (x) ≤ 0, x ∈ [ℓ, u], xI fixed.

x ∈ {0, 1, 2, 3}y ∈ [0, 3]

Reduce Convex MINLP to MIP

Assume all functions gk (·) of MINLP are convex on [ℓ, u].
Duran and Grossmann [1986]: MINLP and thefollowing MIP have the same optimal solutions

Example:min x + ys.t. (x, y ) ∈ ellipsoid

min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,k ∈ [m],xi ∈ Z,x̂ ∈ R,i ∈ I,x ∈ [ℓ, u],where x̂ ∈ R are the solutions of the NLP
subproblems obtained from MINLP by applying any
possible fixing for xI , i.e.,
min c T x s.t. g (x) ≤ 0, x ∈ [ℓ, u], xI fixed.

x ∈ {0, 1, 2, 3}y ∈ [0, 3]

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

x̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

MIPx̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

NLP

MIP

x̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

NLP

MIP

x̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

x̂ ∈ R,∀i ∈ I,∀i ∈ [n]NLP

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

x̂ ∈ R,∀i ∈ I,

NLP
MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

x̂ ∈ R,∀i ∈ I,

NLP
MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z≡∀k ∈ [m]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Outer Approximation(OA) algorithm[Duran and Grossmann, 1986]:• Start with R := ∅.
• Dynamically increase R by alternatively solving
MIP relaxations and NLP subproblems until
MIP solution is feasible for MINLP.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

MIPx̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

MIPx̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

MIPx̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

MIPx̂ ∈ R,∀i ∈ I,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]min c T x,
s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Cutting Plane Method (ECP)[Kelley, 1960, Westerlund and Petterson, 1995]:• Iteratively solve MIP relaxation only.
• Linearize gk (·) in MIP relaxation.
• No need to solve NLP, but weaker MIP
relaxation.

x̂ ∈ R,∀i ∈ I,

MIPOuter Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,∀i ∈ I,xi ∈ [ℓi , ui ],Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP thanECP.

x̂ ∈ R,∀i ∈ [n]Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:
Interior P.

• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

MIP

Outer Approximation Method (OA), ECP, EHP
Convex MINLP

MIP

min c T x
s.t. gk (x) ≤ 0
xi ∈ Zxi ∈ [ℓi , ui ]≡min c T x,

∀k ∈ [m]∀i ∈ I ⊆ [n]∀i ∈ [n]s.t. gk (x̂) + ∇gk (x̂)T (x − x̂) ≤ 0,∀k ∈ [m],xi ∈ Z,x̂ ∈ R,∀i ∈ I,xi ∈ [ℓi , ui ],∀i ∈ [n]Extended Hyperplane Method (EHP)[Veinott, 1967, Kronqvist, Lundell, and Westerlund, 2016,
Lundell, Kronqvist, and Westerlund, 2022, Serrano, Schwarz,
and Gleixner, 2020]:• Iteratively solve MIP relaxation only.
• Move MIP solution onto NLP-feasible set{x ∈ [ℓ, u] : gk (x) ≤ 0} via linesearch.
• Linearize gk (·) in improved reference point.
• No need to solve NLP, but stronger MIP than
ECP.

Interior P.

MIP

LP/NLP- or LP-based Branch & BoundOA/ECP/EHP: Solving a sequence of MIP relaxations can be expensive and wasteful(no warmstarts)

LP/NLP- or LP-based Branch & BoundOA/ECP/EHP: Solving a sequence of MIP relaxations can be expensive and wasteful(no warmstarts)
LP/NLP-based Branch & Bound [Quesada and Grossmann, 1992]:• Integrate NLP-solves into MIP Branch & Bound.
• When LP relaxation is integer feasible, solve NLP subproblem (as in OA).
• Add linearization in NLP solution to LP relaxation and resolve LP.

LP/NLP- or LP-based Branch & BoundOA/ECP/EHP: Solving a sequence of MIP relaxations can be expensive and wasteful(no warmstarts)
LP/NLP-based Branch & Bound [Quesada and Grossmann, 1992]:• Integrate NLP-solves into MIP Branch & Bound.
• When LP relaxation is integer feasible, solve NLP subproblem (as in OA).
• Add linearization in NLP solution to LP relaxation and resolve LP.
LP-based Branch & Bound:• Integrate Kelley’ Cutting Plane method into MIP Branch & Bound.
• Add linearization in LP solution to LP relaxation (as in ECP).
• Optional: Move LP solution onto NLP-feasible set {x ∈ [ℓ, u] : gk (x) ≤ 0} via
linesearch (as in EHP) [Lundell, Kronqvist, and Westerlund, 2022].

Fundamental Methods
Nonconvex MINLP

Nonconvex MINLP
Now: Let gk (·) be nonconvex for some k ∈ [m].
Outer-Approximation:• Linearizations
gk (x̂) + ∇gk (x̂)(x − x̂) ≤ 0
may not be valid.

1.0

0.5

0.0

NLP-based Branch & Bound:• Solving nonconvex NLP relaxation to global
optimality can be as hard as original problem.

-0.5

-1.0
-1.0

-0.5

0.0

0.5

1.0

Nonconvex MINLP
Now: Let gk (·) be nonconvex for some k ∈ [m].
Outer-Approximation:• Linearizations
gk (x̂) + ∇gk (x̂)(x − x̂) ≤ 0
may not be valid.
• Heuristics: add cuts as “soft-constraints”
minα≥0 α s.t. gk (x̂) + ∇gk (x̂)(x − x̂) ≤ α

1.0

0.5

0.0

NLP-based Branch & Bound:-0.5• Solving nonconvex NLP relaxation to global
optimality can be as hard as original problem.
• Heuristic: Solve NLPs locally from multiple
starting points.

-1.0
-1.0

-0.5

0.0

0.5

1.0

Nonconvex MINLP
Now: Let gk (·) be nonconvex for some k ∈ [m].
Outer-Approximation:• Linearizations
gk (x̂) + ∇gk (x̂)(x − x̂) ≤ 0
may not be valid.
• Heuristics: add cuts as “soft-constraints”
minα≥0 α s.t. gk (x̂) + ∇gk (x̂)(x − x̂) ≤ α

1.0

0.5

0.0

NLP-based Branch & Bound:-0.5• Solving nonconvex NLP relaxation to global
optimality can be as hard as original problem.

-1.0
-1.0

-0.5

0.0

• Heuristic: Solve NLPs locally from multiple
starting points.
Exact approach: Spatial Branch & Bound:• Relax nonconvexity to obtain a tractable relaxation (LP or convex NLP).
• Branch on “nonconvexities” to enforce original constraints.

0.5

1.0

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.
Relax I: Convexify the feasible sets that are defined by each constraint individually, i.e.,\conv{x ∈ [ℓ, u] : gk (x) ≤ 0}k∈[m]

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.
Relax I: Convexify the feasible sets that are defined by each constraint individually, i.e.,\conv{x ∈ [ℓ, u] : gk (x) ≤ 0}k∈[m]

• In practice, conv{x ∈ [ℓ, u] : gk (x) ≤ 0} is impossible to construct explicitly ingeneral – but possible for certain cases.

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.
Relax I: Convexify the feasible sets that are defined by each constraint individually, i.e.,\conv{x ∈ [ℓ, u] : gk (x) ≤ 0}k∈[m]

• In practice, conv{x ∈ [ℓ, u] : gk (x) ≤ 0} is impossible to construct explicitly ingeneral – but possible for certain cases.
10

Relax II: Convexify each nonconvex function gk (·)
individually, i.e.,

5

gHxL

-6

-4

2

-2
-5

{x ∈ [ℓ, u] : “ conv(gk )′′ (x) ≤ 0}ge HxL-10

4

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.
Relax I: Convexify the feasible sets that are defined by each constraint individually, i.e.,\conv{x ∈ [ℓ, u] : gk (x) ≤ 0}k∈[m]

• In practice, conv{x ∈ [ℓ, u] : gk (x) ≤ 0} is impossible to construct explicitly ingeneral – but possible for certain cases.
10

Relax II: Convexify each nonconvex function gk (·)
individually, i.e.,

5

gHxL

-6

-4

2

-2
-5

{x ∈ [ℓ, u] : “ conv(gk )′′ (x) ≤ 0}
• In practice, convex envelope is not known explicitly in generalge HxL-10

4

Convex Relaxation
Given: X = {x ∈ [ℓ, u] : gk (x) ≤ 0, k ∈ [m]} (continuous relaxation of MINLP)
Seek: conv(X ) – convex hull of X
• In practice, conv(X ) is impossible to construct explicitly.
Relax I: Convexify the feasible sets that are defined by each constraint individually, i.e.,\conv{x ∈ [ℓ, u] : gk (x) ≤ 0}k∈[m]

• In practice, conv{x ∈ [ℓ, u] : gk (x) ≤ 0} is impossible to construct explicitly ingeneral – but possible for certain cases.
10

Relax II: Convexify each nonconvex function gk (·)
individually, i.e.,

5

gHxL

-6

-4

2

-2
-5

{x ∈ [ℓ, u] : “ conv(gk )′′ (x) ≤ 0}
• In practice, convex envelope is not known explicitly in general– except for many “simple functions”

ge HxL-10

4

Convex Envelopes for “simple” functions
concave functions

xk

1.0

(k ∈ 2Z + 1)

x ·y

1.0

0.5
0.5
0.5

1.0

1.5

2.0

2.5

3.0

-0.5
-1.0

-1.0

0.5

-0.5

1.0

-1.5
-0.5
-2.0
-1.0

x2 · y2√− x · y2x/y(0 < y < ∞)Application to Factorable Functions

Factorable Functions [McCormick, 1976]
g (x) is factorable if it can be expressed as a combination of functions from a finite setof operators, e.g., {+, ×, ÷, ∧, sin, cos, exp, log, | · |}, whose arguments are variables,
constants, or other factorable functions.
• Typically represented as expression trees or graphs (DAG).
Rx• Excludes integrals x 7→ x0 h(ζ)dζ and black-box functions.
Example:+x1 log(x2 ) + x23
×
x1

∧
log

x2

3

McCormick Underestimator for Factorable Functions
McCormick [1976] has shown a possibility to compose known envelopes.
For example, consider f (g (x)) with x ∈ [ℓx , ux ], f (·)
univariate.
1. Let g (x) ∈ [ℓg , ug ] for x ∈ [ℓx , ux ].
2. Let f˘(·) ≤ f (·) be convex envelope of f (·) on[ℓg , ug ].

f (z) =

p|z|, f˘(z), z min = 0:f(z) and its convex envelope

1

0.8

0.6

0.4

0.2

0
-1

3. Let ğ (·) ≤ g (·) ≤ g“ (·) be convex and concave
envelopes of g (·) on [ℓx , ux ].
4. Let z min ∈ argminz∈[ℓ ,u ] f˘(z).
g

g

-0.5

0

0.5

1

g (x) = x 3 , x ∈ [−1, 1]:g(x) and convex and concave envelope

1

0.5

0

-0.5

-1

-1

-0.5

0

0.5

1

McCormick Underestimator for Factorable Functions
McCormick [1976] has shown a possibility to compose known envelopes.
For example, consider f (g (x)) with x ∈ [ℓx , ux ], f (·)
univariate.
1. Let g (x) ∈ [ℓg , ug ] for x ∈ [ℓx , ux ].
2. Let f˘(·) ≤ f (·) be convex envelope of f (·) on[ℓg , ug ].

f (z) =

p|z|, f˘(z), z min = 0:f(z) and its convex envelope

1

0.8

0.6

0.4

0.2

0
-1

3. Let ğ (·) ≤ g (·) ≤ g“ (·) be convex and concave
envelopes of g (·) on [ℓx , ux ].
4. Let z min ∈ argminf˘(z).
z∈[ℓg ,ug ]5. An obvious convex underestimator of f (g (x))
is given by
x 7→ f˘(z min ).

-0.5

0

0.5

1

g (x) = x 3 , x ∈ [−1, 1]:g(x) and convex and concave envelope

1

0.5

0

-0.5

-1

-1

-0.5

0

0.5

1

f (g (x)), McCormick(f ◦ g ) :f(g(x)) and obvious convex underestimator

1

0.8

0.6

0.4

0.2

0
-1

-0.5

0

0.5

1

McCormick Underestimator for Factorable Functions
McCormick [1976] has shown a possibility to compose known envelopes.
For example, consider f (g (x)) with x ∈ [ℓx , ux ], f (·)
univariate.
1. Let g (x) ∈ [ℓg , ug ] for x ∈ [ℓx , ux ].
2. Let f˘(·) ≤ f (·) be convex envelope of f (·) on[ℓg , ug ].

f (z) =

p|z|, f˘(z), z min = 0:f(z) and its convex envelope

1

0.8

0.6

0.4

0.2

0
-1

3. Let ğ (·) ≤ g (·) ≤ g“ (·) be convex and concave
envelopes of g (·) on [ℓx , ux ].
4. Let z min ∈ argminz∈[ℓ ,u ] f˘(z).
gg

5. An obvious convex underestimator of f (g (x))
is given by
x 7→ f˘(z min ).

-0.5

0

0.5

1

g (x) = x 3 , x ∈ [−1, 1]:g(x) and convex and concave envelope

1

0.5

0

-0.5

-1

-1

-0.5

0

0.5

1

f (g (x)), McCormick(f ◦ g ) :f(g(x)) and McCormick convex underestimator

6. The McCormick underestimator is
x 7→ f˘ project z min onto [ğ (x), g“ (x)]

1

0.8

0.6

0.4

0.2

(tighter for z min ̸∈ [ğ (x), g“ (x)]).

0
-1

-0.5

0

0.5

1

McCormick Underestimators

McCormick [1976]: A convex underestimator of f (g (·)) on [ℓx , ux ] is

min
˘

< ğ (x),f (ğ (x)), if z
minwhere z min = argmin f (z).
x 7→ f˘(“
g (x)), if z
> g“ (x),z∈[ℓg ,ug ] ˘ minf (z ), else.
• additional formulas for f (x) · g (x)• in general nonsmooth (nondifferentiable)• implementations for evaluation andcomputation of subgradients exist, e.g., MC++
[Mitsos, Chachuat, and Barton, 2009]

Source: https://psorlab.github.io/EAGO.jl/
stable/McCormick/Usage.html

McCormick Underestimators
McCormick [1976]: A convex underestimator of f (g (·)) on [ℓx , ux ] is

min
˘

< ğ (x),f (ğ (x)), if zmin˘where z min = argmin f (z).
x 7→ f (“g (x)), if z
> g“ (x),z∈[ℓg ,ug ] ˘ minf (z ), else.

• additional formulas for f (x) · g (x)• in general nonsmooth (nondifferentiable)• implementations for evaluation andcomputation of subgradients exist, e.g., MC++
[Mitsos, Chachuat, and Barton, 2009]• differentiable relaxation by Khan, Watson, andBarton [2017]⇒ usable for convex NLP relaxations(→ solvers EAGO and MAiNGO)
Source: https://psorlab.github.io/EAGO.jl/
stable/McCormick/Usage.html

Reformulation of Factorable MINLP

However, most global solvers reformulate factorable MINLPs by introducing new
variables and equations [Smith and Pantelides, 1996, 1997]:
y1 + y2 ≤ 0
x1 y3 = y1
x1 log(x2 ) + x23 ≤ 0
x1 ∈ [1, 2], x2 ∈ [1, e]⇒

x23 = y2log(x2 ) = y3
x1 ∈ [1, 2], x2 ∈ [1, e]y1 ∈ [0, 2], y2 ∈ [1, e 3 ], y3 ∈ [0, 1]• Bounds for new variables inherited from functions and their arguments, e.g.,y3 ∈ log([1, e]) = [0, 1].
• Reformulation may not be unique, e.g., xyz = (xy )z = x(yz).

Factorable Reformulation in Practice
The type of algebraic expressions that is understood and not broken up further isimplementation specific, e.g., for ANTIGONE [Misener and Floudas, 2014]:

Thus, not all functions are supported by any deterministic solver, e.g.,• ANTIGONE and BARON do not support trigonometric functions.
• SCIP does not support max or min (at the moment).
• No deterministic global solver supports external functions that are given byroutines for point-wise evaluation of function and derivatives.

Spatial Branching
Recall Spatial Branch & Bound:✓ Relax nonconvexity to obtain a tractable relaxation.
• Branch on “nonconvexities” to enforce original constraints.

Spatial Branching
Recall Spatial Branch & Bound:✓ Relax nonconvexity to obtain a tractable relaxation.
• Branch on “nonconvexities” to enforce original constraints.
The variable bounds determine the convex relaxation, e.g.,x 2 ≤ ℓ2 +u 2 − ℓ2(x − ℓ)
u−ℓ

1.0

0.8

0.6

0.4

0.2

-1.0

-0.5

0.5

1.0

∀x ∈ [ℓ, u].

Spatial Branching
Recall Spatial Branch & Bound:✓ Relax nonconvexity to obtain a tractable relaxation.
• Branch on “nonconvexities” to enforce original constraints.
The variable bounds determine the convex relaxation, e.g.,x 2 ≤ ℓ2 +u 2 − ℓ2(x − ℓ)u−ℓ∀x ∈ [ℓ, u].

Thus, branching on a nonlinear variable in a nonconvex term allows for tighter
relaxations:

-1.0

-0.5

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0.5

1.0

-1.0

-0.5

0.5

1.0

Spatial Branch and Bound• Solve a relaxation → lower bound• Run heuristics to look for feasible
solutions → upper bound• Branch on a suitable variable• Discard parts of the tree that are
infeasible or where lower bound >best known upper bound• Repeat until gap is below given
tolerance

Tighter variable bounds → improved relaxations → improved bounds on optimal value.

Spatial Branch and Bound• Solve a relaxation → lower bound• Run heuristics to look for feasible
solutions → upper bound• Branch on a suitable variable• Discard parts of the tree that are
infeasible or where lower bound >best known upper bound• Repeat until gap is below given
tolerance

Tighter variable bounds → improved relaxations → improved bounds on optimal value.

Spatial Branch and Bound• Solve a relaxation → lower bound• Run heuristics to look for feasible
solutions → upper bound• Branch on a suitable variable• Discard parts of the tree that are
infeasible or where lower bound >best known upper bound• Repeat until gap is below given
tolerance

Tighter variable bounds → improved relaxations → improved bounds on optimal value.

Spatial Branch and Bound• Solve a relaxation → lower bound• Run heuristics to look for feasible
solutions → upper bound• Branch on a suitable variable• Discard parts of the tree that are
infeasible or where lower bound >best known upper bound• Repeat until gap is below given
tolerance

Tighter variable bounds → improved relaxations → improved bounds on optimal value.

Spatial Branch and Bound• Solve a relaxation → lower bound• Run heuristics to look for feasible
solutions → upper bound• Branch on a suitable variable• Discard parts of the tree that are
infeasible or where lower bound >best known upper bound• Repeat until gap is below given
tolerance

Tighter variable bounds → improved relaxations → improved bounds on optimal value.

Example

Example

Considerminimize − 2x + 3ysuch that x 2 − xy + y 2 ≥ 2x −y ≤1x ∈ [0, 2],y ∈ [−2, 2]
Optimal solution:• from the picture, both inequalities are active ⇒ y = x − 1⇒ 2 = x 2 − x(x − 1) + (x − 1)2 = x 2 − x + 1 ⇒ (x − 12 )2 = 45√

• x ≥ 0 ⇒ x = 1+2 5 , y =√√5−1, objective = 5−5≈ −1.382
2

Example: Solvers

Solve with GAMS (AMPL works too):solverVariables x, y, z;
Equations e1, e2, e3;e1.. -2*x + 3*y =E= z;
e2.. sqr(x)+sqr(y)-x*y =G= 2;e3.. x - y =L= 1;
x.lo = 0;y.lo = -1;

x.up =
y.up =

2;2;

Model m /all/;
Solve m min z using qcp;

ANTIGONEBARONCONOPT
Gurobi
Ipopt
KnitroLindo API
Minos
SCIP
SNOPT
Octeract

optimumtime

B&B tree-1.381966-1.381966
infeasible-1.381966-1.381966-1.381966-1.381968
infeasible-1.381966
infeasible-1.381966

0.00s
0.03s
0.00s
0.02s
0.00s
0.01s
0.22s
0.01s
0.05s
0.00s
0.01s

1 node1 node–13 nodes––3 nodes–
1 node–4 nodesInitial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,
Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .

x ∈ [0, 2],y ∈ [−2, 2]

Initial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,x ∈ [0, 2],y ∈ [−2, 2]

Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .
Since x 2 and y 2 are convex, we can use a tangent and secant on its graph, e.g.,
4−0
4 + 4(x − 2) ≤ x 2 ≤ 0 +(x − 0)
2−0
|
{z
}
{z
}
|
tangent at x=2

secant from x=0 to x=2⇒

4x − 4 ≤ Xxx ≤ 2x

Initial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,x ∈ [0, 2],y ∈ [−2, 2]

Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .
Since x 2 and y 2 are convex, we can use a tangent and secant on its graph, e.g.,
4−0
4 + 4(x − 2) ≤ x 2 ≤ 0 +(x − 0)
2−0
|
{z
}
{z
}
|
tangent at x=2⇒

4x − 4 ≤ Xxx ≤ 2x

secant from x=0 to x=2

Or derive inequalities by multiplying variable bound constraints:
0 ≤ (x − 0)2

= x2

= Xxx

→ Xxx ≥ 0

Initial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,x ∈ [0, 2],y ∈ [−2, 2]

Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .
Since x 2 and y 2 are convex, we can use a tangent and secant on its graph, e.g.,
4−0
4 + 4(x − 2) ≤ x 2 ≤ 0 +(x − 0)
2−0
|
{z
}
{z
}
|
tangent at x=2⇒

4x − 4 ≤ Xxx ≤ 2x

secant from x=0 to x=2

Or derive inequalities by multiplying variable bound constraints:
0 ≤ (x − 0)20 ≤ (2 − x)2= x2= x 2 − 4x + 4= Xxx= Xxx − 4x + 4→ Xxx ≥ 0
→ Xxx ≥ 4x − 4

Initial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,x ∈ [0, 2],y ∈ [−2, 2]

Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .
Since x 2 and y 2 are convex, we can use a tangent and secant on its graph, e.g.,
4−0
4 + 4(x − 2) ≤ x 2 ≤ 0 +(x − 0)
2−0
|
{z
}
{z
}
|
tangent at x=2⇒

4x − 4 ≤ Xxx ≤ 2x

secant from x=0 to x=2

Or derive inequalities by multiplying variable bound constraints:
0 ≤ (x − 0)20 ≤ (2 − x)20 ≤ (2 − x)(x − 0)

= x2
= x 2 − 4x + 4= −x 2 + 2x

= Xxx
= Xxx − 4x + 4= −Xxx + 2x

→ Xxx ≥ 0
→ Xxx ≥ 4x − 4→ Xxx ≤ 2x

Initial LP Relaxation: X enters the stage
Constraint:x 2 − xy + y 2 ≥ 2,x ∈ [0, 2],y ∈ [−2, 2]

Introduce Xxx = x 2 , Xxy = xy , Xyy = y 2 .
Since x 2 and y 2 are convex, we can use a tangent and secant on its graph, e.g.,
4−0
4 + 4(x − 2) ≤ x 2 ≤ 0 +(x − 0)
2−0
|
{z
}
{z
}
|
tangent at x=2⇒

4x − 4 ≤ Xxx ≤ 2x

secant from x=0 to x=2

Or derive inequalities by multiplying variable bound constraints:
0 ≤ (x − 0)2
= x2
= Xxx
→ Xxx ≥ 0
0 ≤ (2 − x)2= x 2 − 4x + 4= Xxx − 4x + 4→ Xxx ≥ 4x − 4
0 ≤ (2 − x)(x − 0)
= −x 2 + 2x
= −Xxx + 2x
→ Xxx ≤ 2x
0 ≤ (y − (−2))2= y 2 + 4y + 4= Xyy + 4y + 4→ Xyy ≥ −4y − 4
0 ≤ (y − (−2))(2 − y ) = −y 2 + 4= −Xyy + 4→ Xyy ≤ 4
0 ≤ (2 − y )2
= y 2 − 4y + 4= Xyy − 4y + 4→ Xyy ≥ 4y − 4
0 ≤ (x − 0)(y − (−2)) = xy + 2x
= Xxy + 2x
→ Xxy ≥ −2x
0 ≤ (x − 0)(2 − y )= −xy + 2x
= −Xxy + 2x
→ Xxy ≤ 2x
0 ≤ (2 − x)(y − (−2)) = −xy − 2x + 2y + 4 = −Xxy − 2x + 2y + 4 → Xxy ≤ −2x + 2y + 4
0 ≤ (2 − x)(2 − y )= xy − 2x − 2y + 4 = Xxy − 2x − 2y + 4 → Xxy ≥ 2x + 2y − 4

Initial LP Relaxation
Replace (x 2 , xy , y 2 ) by (Xxx , Xxy , Xyy )and add derived inequalities:

Projected on (x, y ):min − 2x + 3ys.t. x 2 − xy + y 2 ≥ 2
Xxx − Xxy + Xyy ≥ 2
x −y ≤1
Xxx ≥ 4x − 4
Xxx ≤ 2x
Xyy ≥ −4y − 4
Xyy ≥ 4y − 4
Xxy ≤ 2x
Xxy ≤ −2x + 2y + 4• Lower Bound = -3

Xxy ≥ 2x + 2y + 4⇒ none of the inequalities in(Xxx , Xxy , Xyy ) are active :-(x ∈ [0, 2], y ∈ [−2, 2]
Xxx ∈ [0, ∞], Xyy ∈ [−∞, 4]

Tighten variable bounds• inequalities for relaxation were
derived using bounds on x and y• tighter bounds could mean a tighter
relaxation

Tighten variable bounds• inequalities for relaxation were
derived using bounds on x and y• tighter bounds could mean a tighter
relaxationx − y ≤ 1, x ∈ [0, 2]⇒ y ≥ x − 1 ≥ −1

x − y ≤ 1, y ∈ [−2, 2]⇒x ≤y +1≤3

• updated bounds:x ∈ [0, 2],y ∈ [−1, 2]

Tighten variable bounds• inequalities for relaxation were
derived using bounds on x and y• tighter bounds could mean a tighter
relaxationx − y ≤ 1, x ∈ [0, 2]⇒ y ≥ x − 1 ≥ −1

x − y ≤ 1, y ∈ [−2, 2]⇒x ≤y +1≤3

• updated bounds:x ∈ [0, 2],y ∈ [−1, 2]• from x 2 − xy + y 2 ≥ 2, no boundtightening can be derived

In General: Variable Bounds Tightening (Domain Propagation)

1.0

Tighten variable bounds [ℓ, u] such that

0.5

• the optimal value of the problem is not changed, or

0.0• the set of optimal solutions is not changed, or-0.5• the set of feasible solutions is not changed.
-1.0
-1.0

-0.5

0.0

0.5

Formally:
min / max {xk : x ∈ R},k ∈ [n],where R = {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I} (MINLP-feasible set) or a relaxation
thereof.
Bound tightening can tighten the LP relaxation without branching.
Belotti, Lee, Liberti, Margot, and Wächter [2009]: overview on bound tightening for
MINLP

1.0

Feasibility-Based Bound Tightening
Feasbility-based Bound Tightening (FBBT):
Deduce variable bounds from single constraint and box [ℓ, u], that is
R = {x ∈ [ℓ, u] : gj (x) ≤ 0}
for some fixed j ∈ [m].
• cheap and effective ⇒ used for “probing”

Feasibility-Based Bound Tightening
Feasbility-based Bound Tightening (FBBT):
Deduce variable bounds from single constraint and box [ℓ, u], that is
R = {x ∈ [ℓ, u] : gj (x) ≤ 0}
for some fixed j ∈ [m].
• cheap and effective ⇒ used for “probing”
Linear Constraints:
b≤

⇒

xj ≤

xj ≥

X

ai xi +

X

i:ai >0i:ai <0



c −
1 

X

aj 

b −


b −
1 
aj 

c −

ai xi ≤ c,i:ai >0,i̸=jX

ai u i −

i:ai >0

ai u i −

i:ai >0,i̸=ji:ai >0i:ai <0X

ai u i ,if aj > 0ai ℓi ,

if aj < 0ai ℓi ,

if aj > 0

ai u i ,if aj < 0i:ai <0,i̸=jX
X

X

ai ℓi −ℓ≤x ≤uai ℓ i −X

i:ai <0X
i:ai <0,i̸=j• Belotti, Cafieri, Lee, and Liberti [2010]: fixed point of iterating FBBT on set of
linear constraints can be computed by solving one LP

Feasibility-Based Bound Tightening on Expression Tree
Example:√+√√x + 2 xy + 2 y ∈ [−∞, 7]

2

1x, y ∈ [1, 9]
y

√
·

8

2

√

√

·

6

∗

4

2

0
0

2

4

6

8

x

y

[1, 9][1, 9]x·Feasibility-Based Bound Tightening on Expression Tree
Example:√√[−∞, 7]√x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y

2

1

8

√
·

2

√

√

·

·

6

4

[1, 81]

∗

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)xy[1, 9][1, 9][1, 9] ∗ [1, 9] = [1, 81]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[−∞, 7]√x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 9]√·[1, 3][1, 81]∗1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)xy[1, 9][1, 9]
pp[1, 9] = [1, 3][1, 81] = [1, 9]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[−∞, 7]∩[5, 27]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 9]√·[1, 3][1, 81]∗1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)xy[1, 9][1, 9][1, 3] + 2 [1, 9] + 2 [1, 3] = [5, 27]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 9]√·[1, 3][1, 81]∗1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 9][1, 9][5, 7] − 2 [1, 9] − 2 [1, 3] = [−19, 3]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 2]√·[1, 3][1, 81]∗1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 9][1, 9]([5, 7] − [1, 3] − 2 [1, 3])/2 = [−2, 2]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 2]√·[1, 2][1, 81]∗1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 9][1, 9]([5, 7] − [1, 3] − 2 [1, 2])/2 = [−1, 2]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 9][1, 9][1, 2]2 = [1, 4]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)[1, 3]2 = [1, 9]xy[1, 4][1, 9][1, 4]/[1, 9] = [1/9, 4]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 9]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 3]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)[1, 2]2 = [1, 4]

xy[1, 4][1, 4][1, 4]/[1, 4] = [1/4, 4]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[−∞, 7]√x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y

2

1

8

√
·

2

√

√

·

·

6

4

[1, 16]

∗

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4][1, 4] ∗ [1, 4] = [1, 16]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[−∞, 7]√x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 4]√·[1, 2][1, 16]∗1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4]
pp[1, 4] = [1, 2][1, 16] = [1, 4]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 4]√·[1, 2][1, 16]∗1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4][1, 2] + 2 [1, 4] + 2 [1, 2] = [5, 14]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 4]√·[1, 2][1, 16]∗1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4][5, 7] − 2 [1, 4] − 2 [1, 2] = [−7, 3]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 2]√·[1, 2][1, 16]∗1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4]([5, 7] − [1, 2] − 2 [1, 2])/2 = [−0.5, 2]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 2]√·[1, 2][1, 16]∗1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4]([5, 7] − [1, 2] − 2 [1, 4])/2 = [−2.5, 2]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)xy[1, 4][1, 4][1, 2]2 = [1, 4]

Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)[1, 2]2 = [1, 4]

xy[1, 4][1, 4][1, 4]/[1, 4] = [1/4, 4]Application of Interval Arithmetics [Moore,
1966]

Feasibility-Based Bound Tightening on Expression Tree
Example:√√[5, 7]√

x + 2 xy + 2 y ∈ [−∞, 7]+x, y ∈ [1, 4]
y2

2[1, 2]√·[1, 2][1, 4]∗

1

8[1, 2]

√
·

√

·

6

4

2

0
0

2

4

6

8

x

Forward propagation:• compute bounds on intermediate
nodes (bottom-up)
Backward propagation:• reduce bounds using reverse
operations (top-down)[1, 2]2 = [1, 4]

xy[1, 4][1, 4][1, 4]/[1, 4] = [1/4, 4]Application of Interval Arithmetics [Moore,
1966]

Problem: Overestimation

Back to Example: Relaxation after bound update

Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−1, 2]}
Linearization: x 2 → Xxx , xy → Xxy , y 2 → Xyy
Recompute initial relaxation with lower bound on y updated to −1:
0 ≤ (x − 0)2
= x2
= Xxx
→ Xxx ≥ 0
0 ≤ (2 − x)2= x 2 − 4x + 4= Xxx − 4x + 4→ Xxx ≥ 4x − 4
0 ≤ (2 − x)(x − 0)
= −x 2 + 2x
= −Xxx + 2x
→ Xxx ≤ 2x
0 ≤ (y − (−1))2= y2 + y + 1= Xyy + y + 1→ Xyy ≥ −y − 1
0 ≤ (y − (−1))(2 − y ) = −y 2 + y + 2= −Xyy + y + 2→ Xyy ≤ y + 2
0 ≤ (2 − y )2
= y 2 − 4y + 4= Xyy − 4y + 4→ Xyy ≥ 4y − 4
0 ≤ (x − 0)(y − (−1)) = xy + x= Xxy + x
→ Xxy ≥ −x
0 ≤ (x − 0)(2 − y )= −xy + 2x
= −Xxy + 2x
→ Xxy ≤ 2x
0 ≤ (2 − x)(y − (−1)) = −xy − x + 2y + 2 = −Xxy − x + 2y + 2 → Xxy ≤ −x + 2y + 2
0 ≤ (2 − x)(2 − y )= xy − 2x − 2y + 4 = Xxy − 2x − 2y + 4 → Xxy ≥ 2x + 2y − 4

LP Relaxation after Bound Tightening
With y ≥ −1:
min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2

Projected on (x, y ):x −y ≤1
Xxx ≥ 0Xxx ≥ 4x − 4
Xxx ≤ 2x
Xyy ≥ −y − 1
Xyy ≤ y + 2
Xyy ≥ 4y − 4
Xxy ≥ −x
Xxy ≤ 2x
Xxy ≤ −x + 2y + 2
Xxy ≥ 2x + 2y + 4
x ∈ [0, 2], y ∈ [−1, 2]• Lower Bound = -2.75 (improvementfrom -3)

Can we get more cuts?

• we should make use of the inequality x − y ≤ 1• Idea: multiply bounds with linear inequality

Can we get more cuts?

• we should make use of the inequality x − y ≤ 1• Idea: multiply bounds with linear inequality0 ≤ (1 − x + y )(x − 0)

= x − x 2 + xy

= x − Xxx + Xxy

Can we get more cuts?

• we should make use of the inequality x − y ≤ 1• Idea: multiply bounds with linear inequality0 ≤ (1 − x + y )(x − 0)0 ≤ (1 − x + y )(2 − x)

= x − x 2 + xy
= x − Xxx + Xxy= 2 − x − 2x + x 2 + 2y − xy = 2 − 3x + Xxx + 2y − XxyCan we get more cuts?

• we should make use of the inequality x − y ≤ 1• Idea: multiply bounds with linear inequality0 ≤ (1 − x + y )(x − 0)
= x − x 2 + xy
= x − Xxx + Xxy
0 ≤ (1 − x + y )(2 − x)
= 2 − x − 2x + x 2 + 2y − xy = 2 − 3x + Xxx + 2y − Xxy
0 ≤ (1 − x + y )(y − (−1)) = y + 1 − xy − x + y 2 + y = 2y + 1 − Xxy − x + Xyy
0 ≤ (1 − x + y )(2 − y )= 2 − y − 2x + xy + 2y − y 2 = 2 + y − 2x + Xxy − Xyy
Inequalities that couple several X → looks promisingLP Relaxation with additional cuts
Projected on (x, y ):min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1
Xxx ≥ 0Xxx ≥ 4x − 4
Xxx ≤ 2x
Xyy ≥ −y − 1
Xyy ≤ y + 2
Xyy ≥ 4y − 4
Xxy ≥ −x
Xxy ≤ 2x
Xxy ≤ −x + 2y + 2
Xxy ≥ 2x + 2y + 4
Xxx − Xxy ≤ x
Xxx − Xxy ≥ 3x − 2y − 2
Xxy − Xyy ≤ 2y − x + 1
Xxy − Xyy ≥ 2x − y − 2x ∈ [0, 2], y ∈ [−1, 2]• Lower Bound = -2.66 (improvementfrom -2.75)

LP Relaxation with additional cuts
Projected on (x, y ):min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1
Xxx ≥ 0Xxx ≥ 4x − 4
Xxx ≤ 2x
Xyy ≥ −y − 1
Xyy ≤ y + 2
Xyy ≥ 4y − 4
Xxy ≥ −x
Xxy ≤ 2x
Xxy ≤ −x + 2y + 2
Xxy ≥ 2x + 2y + 4
Xxx − Xxy ≤ x
Xxx − Xxy ≥ 3x − 2y − 2
Xxy − Xyy ≤ 2y − x + 1
Xxy − Xyy ≥ 2x − y − 2x ∈ [0, 2], y ∈ [−1, 2]• Lower Bound = -2.66 (improvementfrom -2.75)

In General: Reformulation Linearization Technique (RLT)
Consider the QCQP
min x T Q0 x + b0T x
s.t. xT

Qk x + bkT x ≤ ck

(quadratic)
k = 1, . . . , q(quadratic)Ax ≤ b(linear)ℓ≤x ≤u(linear)In General: Reformulation Linearization Technique (RLT)
Consider the QCQP
min x T Q0 x + b0T x
s.t. xT

Qk x + bkT x ≤ ck

(quadratic)
k = 1, . . . , q(quadratic)Ax ≤ b(linear)ℓ≤x ≤u(linear)Introduce new variables

Xi,j = xi xj :min ⟨Q0 , X ⟩ + b0T x
s.t. ⟨Qk , X ⟩ + bkT x ≤ ck

k = 1, . . . , q(linear)(linear)Ax ≤ bℓ≤x ≤uX = xx(linear)T(linear)(quadratic)

In General: Reformulation Linearization Technique (RLT)
Consider the QCQP
min x T Q0 x + b0T x
s.t. xT

Qk x + bkT x ≤ ck

(quadratic)
k = 1, . . . , q(quadratic)Ax ≤ b(linear)ℓ≤x ≤u(linear)Introduce new variables

Xi,j = xi xj :min ⟨Q0 , X ⟩ + b0T x
s.t. ⟨Qk , X ⟩ + bkT x ≤ ck

k = 1, . . . , q(linear)(linear)Ax ≤ bℓ≤x ≤uX = xx(linear)T(linear)(quadratic)

Adams and Sherali [1986], Sherali and Alameddine [1992], Sherali and Adams [1999]:• relax X = xx T by linear inequalities that are derived from multiplications of pairsof linear constraints

RLT: Multiplying Bound Constraints
Multiplying bounds ℓi ≤ xi ≤ ui and ℓj ≤ xj ≤ uj yields(xi − ℓi )(xj − ℓj ) ≥ 0(xi − ui )(xj − uj ) ≥ 0(xi − ℓi )(xj − uj ) ≤ 0(xi − ui )(xj − ℓj ) ≤ 0

RLT: Multiplying Bound Constraints
Multiplying bounds ℓi ≤ xi ≤ ui and ℓj ≤ xj ≤ uj and using Xi,j = xi xj yields(xi − ℓi )(xj − ℓj ) ≥ 0⇒

Xi,j ≥ ℓi xj + ℓj xi − ℓi ℓj(xi − ui )(xj − uj ) ≥ 0⇒

Xi,j ≥ ui xj + uj xi − ui uj(xi − ℓi )(xj − uj ) ≤ 0⇒

Xi,j ≤ ℓi xj + uj xi − ℓi uj(xi − ui )(xj − ℓj ) ≤ 0⇒

Xi,j ≤ ui xj + ℓj xi − ui ℓj

RLT: Multiplying Bound Constraints
Multiplying bounds ℓi ≤ xi ≤ ui and ℓj ≤ xj ≤ uj and using Xi,j = xi xj yields(xi − ℓi )(xj − ℓj ) ≥ 0⇒

Xi,j ≥ ℓi xj + ℓj xi − ℓi ℓj(xi − ui )(xj − uj ) ≥ 0⇒

Xi,j ≥ ui xj + uj xi − ui uj(xi − ℓi )(xj − uj ) ≤ 0⇒

Xi,j ≤ ℓi xj + uj xi − ℓi uj(xi − ui )(xj − ℓj ) ≤ 0⇒

Xi,j ≤ ui xj + ℓj xi − ui ℓj• these are more widely known as McCormick inequalities [McCormick, 1976]

RLT: Multiplying Bound Constraints
Multiplying bounds ℓi ≤ xi ≤ ui and ℓj ≤ xj ≤ uj and using Xi,j = xi xj yields(xi − ℓi )(xj − ℓj ) ≥ 0⇒

Xi,j ≥ ℓi xj + ℓj xi − ℓi ℓj(xi − ui )(xj − uj ) ≥ 0⇒

Xi,j ≥ ui xj + uj xi − ui uj(xi − ℓi )(xj − uj ) ≤ 0⇒

Xi,j ≤ ℓi xj + uj xi − ℓi uj(xi − ui )(xj − ℓj ) ≤ 0⇒

Xi,j ≤ ui xj + ℓj xi − ui ℓj• these are more widely known as McCormick inequalities [McCormick, 1976]• the resulting linear relaxation ismin ⟨Q0 , X ⟩ + b0T x
s.t. ⟨Qk , X ⟩ + bkT x ≤ ck
Ax ≤ b,k = 1, . . . , qℓ≤x ≤uXi,j ≥ ℓi xj + ℓj xi − ℓi ℓj

i, j = 1, . . . , n, i ≤ j

Xi,j ≥ ui xj + uj xi − ui uj

i, j = 1, . . . , n, i ≤ j

Xi,j ≤ ℓi xj + uj xi − ℓi uj

i, j = 1, . . . , n,

X = XT

RLT: Multiplying Bound Constraints
Multiplying bounds ℓi ≤ xi ≤ ui and ℓj ≤ xj ≤ uj and using Xi,j = xi xj yields(xi − ℓi )(xj − ℓj ) ≥ 0⇒

Xi,j ≥ ℓi xj + ℓj xi − ℓi ℓj(xi − ui )(xj − uj ) ≥ 0⇒

Xi,j ≥ ui xj + uj xi − ui uj(xi − ℓi )(xj − uj ) ≤ 0⇒

Xi,j ≤ ℓi xj + uj xi − ℓi uj(xi − ui )(xj − ℓj ) ≤ 0⇒

Xi,j ≤ ui xj + ℓj xi − ui ℓj• these are more widely known as McCormick inequalities [McCormick, 1976]• the resulting linear relaxation ismin ⟨Q0 , X ⟩ + b0T x
s.t. ⟨Qk , X ⟩ + bkT x ≤ ck
Ax ≤ b,k = 1, . . . , qℓ≤x ≤uXi,j ≥ ℓi xj + ℓj xi − ℓi ℓj

i, j = 1, . . . , n, i ≤ j

Xi,j ≥ ui xj + uj xi − ui uj

i, j = 1, . . . , n, i ≤ j

Xi,j ≤ ℓi xj + uj xi − ℓi uj

i, j = 1, . . . , n,

X = XT• these inequalities are used by all solvers• not every solver introduces Xi,j variables explicitly

RLT: Multiplying Bounds and Inequalities

Additional inequalities are derived by multiplying pairs of linear equations and boundconstraints:(ATk x − bk )(xj − ℓj ) ≥ 0

⇒

n
X
i=1

Ak,i xi (xj − ℓj ) − bk (xj − ℓj ) ≥ 0

RLT: Multiplying Bounds and Inequalities

Additional inequalities are derived by multiplying pairs of linear equations and boundconstraints:(ATk x − bk )(xj − ℓj ) ≥ 0

⇒

n
X
i=1

Ak,i (Xi,j − xi ℓj ) − bk (xj − ℓj ) ≥ 0

RLT: Multiplying Bounds and Inequalities

Additional inequalities are derived by multiplying pairs of linear equations and boundconstraints:(ATk x − bk )(xj − ℓj ) ≥ 0⇒nXAk,i (Xi,j − xi ℓj ) − bk (xj − ℓj ) ≥ 0

i=1
T
(AT
k x − bk )(Ak ′ x − bk ′ ) ≥ 0

⇒

T
T
T
AT
k xAk ′ x − bk Ak ′ x − bk ′ Ak x + bk bk ′ ≥ 0

RLT: Multiplying Bounds and Inequalities

Additional inequalities are derived by multiplying pairs of linear equations and boundconstraints:(ATk x − bk )(xj − ℓj ) ≥ 0⇒nXAk,i (Xi,j − xi ℓj ) − bk (xj − ℓj ) ≥ 0

i=1
T
(AT
k x − bk )(Ak ′ x − bk ′ ) ≥ 0

⇒

T
T
AT
k XAk ′ − (bk Ak ′ + bk ′ Ak )x + bk bk ′ ≥ 0

RLT: Multiplying Bounds and Inequalities

Additional inequalities are derived by multiplying pairs of linear equations and boundconstraints:(ATk x − bk )(xj − ℓj ) ≥ 0⇒nXAk,i (Xi,j − xi ℓj ) − bk (xj − ℓj ) ≥ 0

i=1
T
(AT
k x − bk )(Ak ′ x − bk ′ ) ≥ 0

⇒

T
T
AT
k XAk ′ − (bk Ak ′ + bk ′ Ak )x + bk bk ′ ≥ 0

RLT is also used for polynomial programs [Sherali and Tuncbilek, 1992]:
Q• any monomial i xiαi is replaced by a new variable• more than two bounds or (in)equalities are multiplied• solver: RAPOSa [González-Rodríguez et al., 2022]

Back to Example: Objective Cutoffmin{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−1, 2]}
Assume the optimal solution with objective =solver, but proof of optimality is still missing.

√

5−5
2

has been found, e.g., by a NLP

Objective cutoff: Look only for improving solutions: −2x + 3y ≤

√

5−5
2

Back to Example: Objective Cutoffmin{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−1, 2]}
Assume the optimal solution with objective =solver, but proof of optimality is still missing.

√

5−5
2

has been found, e.g., by a NLP

Objective cutoff: Look only for improving solutions: −2x + 3y ≤

√

5−5
2

RLT with this inequality:
√

5
5
x− x
2
2
√
√
5
13
0 ≤ −2Xxx + 3Xxy −x+x − 6y + 5 − 5
2
2
√
√
5
11
5
5
0 ≤ 2Xxy − 3Xyy +y + 2x −
y+
−
2
2
2
2
√
√
5
7
0 ≤ −2Xxy + 3Xyy −y + 4x − y + 5 − 52
2
0 ≤ 2Xxx − 3Xxy +• Lower bound = -2.46(improvement from -2.66)

Back to Example: Objective Cutoffmin{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−1, 2]}
Assume the optimal solution with objective =solver, but proof of optimality is still missing.

√

5−5
2

has been found, e.g., by a NLP

Objective cutoff: Look only for improving solutions: −2x + 3y ≤

√

5−5
2

RLT with this inequality:
√

5
5
x− x
2
2
√
√
5
13
0 ≤ −2Xxx + 3Xxy −x+x − 6y + 5 − 5
2
2
√
√
11
5
5
5
0 ≤ 2Xxy − 3Xyy +y + 2x −
y+
−
2
2
2
2
√
√
5
7
0 ≤ −2Xxy + 3Xyy −y + 4x − y + 5 − 52
2
0 ≤ 2Xxx − 3Xxy +• Lower bound = -2.46(improvement from -2.66)
√

√
1
5−5
Use objective cutoff for bound tightening: y ≤ 3+ 2x ≤ 5+3≈ 0.872
6

More Bound Tightening
Looking at the LP relaxation including objective cutoff only, it seems that variablebounds could be improved further:x −y ≤1√5−5−2x + 3y ≤2...
x ∈ [0, 2], y ∈ [−1, 0.87]
Apparently, x ≪ 2.

More Bound Tightening
Looking at the LP relaxation including objective cutoff only, it seems that variablebounds could be improved further:x −y ≤1√5−5−2x + 3y ≤2...
x ∈ [0, 2], y ∈ [−1, 0.87]
Apparently, x ≪ 2.
Propagating each inequality
individually works:x − y ≤ 1 ⇒ x ≤ 1.87
−2x + 3y ≤ −1.38 ⇒ y ≤ 0.79
x − y ≤ 1 ⇒ x ≤ 1.79
−2x + 3y ≤ −1.38 ⇒ y ≤ 0.73..
.
Belotti [2013]: FBBT on two linear constraints simultaneouslyMore Bound Tightening
Looking at the LP relaxation including objective cutoff only, it seems that variablebounds could be improved further:x −y ≤1√5−5−2x + 3y ≤2...
x ∈ [0, 2], y ∈ [−1, 0.87]
Apparently, x ≪ 2.
Propagating each inequality
individually works:x − y ≤ 1 ⇒ x ≤ 1.87
−2x + 3y ≤ −1.38 ⇒ y ≤ 0.79

Eventually, this terminates with upperbounds equal tox − y ≤ 1 ⇒ x ≤ 1.79

max{x : x − y ≤ 1, −2x + 3y ≤ −1.38}−2x + 3y ≤ −1.38 ⇒ y ≤ 0.73

max{y : x − y ≤ 1, −2x + 3y ≤ −1.38}..
.

Idea: Just solve this LP!

Belotti [2013]: FBBT on two linear constraints simultaneously

In General: Optimization-based bound tightening

Recall: Bound Tightening ≡ min / max {xk : x ∈ R}, k ∈ [n], whereR ⊇ {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I}?

In General: Optimization-based bound tightening

Recall: Bound Tightening ≡ min / max {xk : x ∈ R}, k ∈ [n], whereR ⊇ {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I}
Optimization-based Bound Tightening [Quesada andGrossmann, 1993, Maranas and Floudas, 1997, Smith andPantelides, 1999, . . . ]:• R = {x : Ax ≤ b, c T x ≤ z ∗ } linear relaxation(with obj. cutoff)

In General: Optimization-based bound tightening

Recall: Bound Tightening ≡ min / max {xk : x ∈ R}, k ∈ [n], whereR ⊇ {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I}
Optimization-based Bound Tightening [Quesada andGrossmann, 1993, Maranas and Floudas, 1997, Smith andPantelides, 1999, . . . ]:• R = {x : Ax ≤ b, c T x ≤ z ∗ } linear relaxation(with obj. cutoff)

In General: Optimization-based bound tightening

Recall: Bound Tightening ≡ min / max {xk : x ∈ R}, k ∈ [n], whereR ⊇ {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I}
Optimization-based Bound Tightening [Quesada andGrossmann, 1993, Maranas and Floudas, 1997, Smith andPantelides, 1999, . . . ]:• R = {x : Ax ≤ b, c T x ≤ z ∗ } linear relaxation(with obj. cutoff)• simple, but effective on nonconvex MINLP:
relaxation depends on domains• but: potentially many expensive LPs per node

In General: Optimization-based bound tightening
Recall: Bound Tightening ≡ min / max {xk : x ∈ R}, k ∈ [n], whereR ⊇ {x ∈ [ℓ, u] : g (x) ≤ 0, xi ∈ Z, i ∈ I}
Optimization-based Bound Tightening [Quesada andGrossmann, 1993, Maranas and Floudas, 1997, Smith andmin xkλ1

Pantelides, 1999, . . . ]:• R = {x : Ax ≤ b, c T x ≤ z ∗ } linear relaxation(with obj. cutoff)• simple, but effective on nonconvex MINLP:
relaxation depends on domains• but: potentially many expensive LPs per node

λ2

Advanced implementation [Gleixner, Berthold, Müller, and Weltge, 2017]:• solve OBBT LPs at root only, learn dual certificates xk ≥P

i ri xi + µz∗

+ λT b• propagate duality certificates during tree search (“approximate OBBT”)• greedy ordering for faster LP warmstarts, filtering of provably tight bounds

Back to Example: Bound Tightening by OBBT
We tightened upper bounds via
√
√


5−5
1+ 5
max x : x − y ≤ 1, −2x + 3y ≤=≈ 1.62
2
2
√
√


5−5
5−1
=
max y : x − y ≤ 1, −2x + 3y ≤≈ 0.622
2

Back to Example: Bound Tightening by OBBT
We tightened upper bounds via
√
√


5−5
1+ 5
max x : x − y ≤ 1, −2x + 3y ≤=≈ 1.62
2
2
√
√


5−5
5−1
=
max y : x − y ≤ 1, −2x + 3y ≤≈ 0.622
2
To tighten also lower bounds, consider the complete relaxation:
min x or ys.t. x − y ≤ 1

√

5−5
2
Xxx − Xxy + Xyy ≥ 2− 2x + 3y ≤RLT(X , x, y ),
√ 
√



1+ 5
5−1
x ∈ 0,, y ∈ −1,22

⇒ x ≥ 0.54, y ≥ −0.46

FBBT on quadratic constraint

With the tighter bounds from OBBT, let us try to derive further boundtightening fromthe quadratic constraint, that is
min / max{x or y : x 2 − xy + y 2 ≥ 2, x ∈ [0.54, 1.62], y ∈ [−0.46, 0.62]}

For y we cannot expect any tightening, but what about the lower bound for x?

FBBT on quadratic constraint – do the mathx 2 − xy + y 2 = (y − 12 x)2 + 43 x 2 is supposed to be ≥ 2

FBBT on quadratic constraint – do the mathx 2 − xy + y 2 = (y − 12 x)2 + 43 x 2 is supposed to be ≥ 2q⇒ (x − 12 y )2 ≥ 2 − 34 y 2 ⇒ |x − 12 y | ≥ 2 − 34 y 2qq⇒ x − 21 y ≥ 2 − 34 y 2 or x − 12 y ≤ − 2 − 43 y 2

FBBT on quadratic constraint – do the mathx 2 − xy + y 2 = (y − 12 x)2 + 43 x 2 is supposed to be ≥ 2q⇒ (x − 12 y )2 ≥ 2 − 34 y 2 ⇒ |x − 12 y | ≥ 2 − 34 y 2qq⇒ x − 21 y ≥ 2 − 34 y 2 or x − 12 y ≤ − 2 − 43 y 2
"
⇒x ∈

1
−∞, y −
2

r

# "
#!
r
3 2
3 2
1
2− y ∪
y + 2 − y ,∞∩ [0.54, 1.62]
4
2
4

The right-hand side now depends on y only.

FBBT on quadratic constraint – do the mathx 2 − xy + y 2 = (y − 12 x)2 + 43 x 2 is supposed to be ≥ 2q⇒ (x − 12 y )2 ≥ 2 − 34 y 2 ⇒ |x − 12 y | ≥ 2 − 34 y 2qq⇒ x − 21 y ≥ 2 − 34 y 2 or x − 12 y ≤ − 2 − 43 y 2
"
⇒x ∈

1
−∞, y −
2

r

# "
#!
r
3 2
3 2
1
2− y ∪
y + 2 − y ,∞∩ [0.54, 1.62]
4
2
4

The right-hand side now depends on y only.
We now need to find
r
1
3
max
y − 2 − y2y ∈[−0.46,0.62] 2
4

1
min
y+
y ∈[−0.46,0.62] 2

r
2−

3 2
y
4

FBBT on quadratic constraint – do the mathx 2 − xy + y 2 = (y − 12 x)2 + 43 x 2 is supposed to be ≥ 2q⇒ (x − 12 y )2 ≥ 2 − 34 y 2 ⇒ |x − 12 y | ≥ 2 − 34 y 2qq⇒ x − 21 y ≥ 2 − 34 y 2 or x − 12 y ≤ − 2 − 43 y 2
"
⇒x ∈

1
−∞, y −
2

r

# "
#!
r
3 2
3 2
1
2− y ∪
y + 2 − y ,∞∩ [0.54, 1.62]
4
2
4

The right-hand side now depends on y only.
We now need to find
r
1
3
max
y − 2 − y2y ∈[−0.46,0.62] 2
4

1
min
y+
y ∈[−0.46,0.62] 2

These are univariate bound-constrained optimization problems.

r
2−

3 2
y
4

FBBT on quadratic constraint – do the math (cont.)1y−y ∈[−0.46,0.62] 2

r

1
min
y+
y ∈[−0.46,0.62] 2

r

2−

max

3 2
0.62
y |{z}
=
−
4
2

r
2−

y =0.6230.46
2 − y 2 |{z}
= −
+
4
2
y =−0.46

3
0.622
4

r
2−

3
(−0.46)2
4≈ −1≈ 1.13

FBBT on quadratic constraint – do the math (cont.)1y−y ∈[−0.46,0.62] 2

r

1
min
y+
y ∈[−0.46,0.62] 2

r

2−

max

3 2
0.62
y |{z}
=
−
4
2

r
2−

y =0.62

30.46
2 − y 2 |{z}
= −
+
4
2

3
0.622
4

r
2−

y =−0.46

3(−0.46)2
4≈ −1≈ 1.13





r

r

≈−1

≈1.13




1
3 2
3 2


 1
⇒x ∈
−∞, 2 y − 2 − 4 y  ∪  2 y + 2 − 4 y , ∞∩[0.54, 1.62] = [1.13, 1.62]
|
{z
}
|
{z
}
Note: feasible range on x is
disconnected (2 intervals);
we used x ≥ 0.54 to exclude theleft interval and derive x ≥ 1.13
Vigerske and Gleixner [2017]: generalformulasUpdated Relaxation after FBBT and OBBTWe derived• x ≤ 1.62, y ≤ 0.62 via OBBT or alternating FBBT on x − y ≤ 1 and−2x + 3y ≤ −1.38• y ≥ −0.46 via OBBT on LP relaxation (incl. RLT cuts)• x ≥ 1.13 via careful (avoid overestimation of interval arith.) FBBT on x 2 − xy + y 2 ≥ 2Update RLT:
0 ≤ (x − 1.13)20 ≤ (1.62 − x)20 ≤ (x − 1.13)(1.62 − x)
0 ≤ (y + 0.46)2
0 ≤ (0.62 − y )20 ≤ (0.62 − y )(y + 0.46)
0 ≤ (x − 1.13)(y + 0.46)
0 ≤ (x − 1.13)(0.62 − y )0 ≤ (1.62 − x)(y + 0.46)
0 ≤ (1.62 − x)(0.62 − y )0 ≤ (x − 1.13)(1 − x + y )0 ≤ (1.62 − x)(1 − x + y )0 ≤ (y + 0.46)(1 − x + y )0 ≤ (0.62 − y )(1 − x + y )0 ≤ (x − 1.13)(−1.38 + 2x − 3y )0 ≤ (1.62 − x)(−1.38 + 2x − 3y )0 ≤ (y + 0.46)(−1.38 + 2x − 3y )0 ≤ (0.62 − y )(−1.38 + 2x − 3y )xx → Xxx , xy → Xxy , yy → Xyy

Updated Relaxation (cont.)

Lower bound = -1.76 (improvement from -2.46, optimal value = -1.38)

Updated Relaxation (cont.)

Lower bound = -1.76 (improvement from -2.46, optimal value = -1.38)
Next steps:• OBBT improves lower bound on y due to tighter RLT cuts
• FBBT on quad. cons. improves lower bound on x due to better bound on y
• RLT cuts tighten due to better lower bounds on x and yRecap

Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
Initial Relaxation:• replace any square and bilinear term by new variable (X )• derive cuts for X by multiplying variable bounds, e.g., (2 − x)(2 − y ) ≥ 0(also known as McCormick cuts)

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1
RLT(multiply bounds)x ∈ [0, 2]y ∈ [−2, 2]

Lower bound = -3

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
Bound Tightening:• FBBT on linear constraint: x − y ≤ 1 ⇒ y ≥ −1

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1
RLT(multiply bounds)x ∈ [0, 2]y ∈ [−1, 2]

Lower bound = -2.75

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
RLT with Linear Inequality:• multiply x − y ≤ 1 with variable bound, e.g., (2 − x)(1 − x + y ) ≥ 0

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1
RLT(bounds & x − y ≤ 1)x ∈ [0, 2]y ∈ [−1, 2]

Lower Bound = -2.66

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
Objective Cutoff:• look only for improving solutions: −2x + 3y ≤ −1.36• use for FBBT and RLT (improving upper bound can improve lower bound!)

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1− 2x + 3y ≤ 1.38
RLT(bounds & linear inequ.)x ∈ [0, 2]y ∈ [−1, 0.87]

Lower Bound = -2.46

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
Bound Tightening:• OBBT on relaxation: min / max x or y w.r.t. LP relaxation• expensive, best when objective cutoff included

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1− 2x + 3y ≤ 1.38
RLT(bounds & linear inequ.)x ∈ [0.54, 1.62]
y ∈ [−0.46, 0.62]

Recap
Problem: min{−2x + 3y : x 2 − xy + y 2 ≥ 2, x − y ≤ 1, x ∈ [0, 2], y ∈ [−2, 2]}
Bound Tightening:• FBBT on x 2 − xy + y 2 ≥ 2 ⇒ x ≥ 1.13

LP Relaxation:min − 2x + 3ys.t. Xxx − Xxy + Xyy ≥ 2
x −y ≤1− 2x + 3y ≤ 1.38
RLT(bounds & linear inequ.)x ∈ [1.13, 1.62]
y ∈ [−0.46, 0.62]

Lower bound = -1.76

Further TechniquesFurther Techniques
Dual Side (Tighter Relaxations)Semidefinite Programming (SDP) Relaxation

min x T Q0 x + b0T x⇔

s.t. x T Qk x + bkT x ≤ ck

min ⟨Q0 , X ⟩ + b0T x
s.t. ⟨Qk , X ⟩ + bkT x ≤ ck

Ax ≤ bAx ≤ bℓx ≤ x ≤ ux

ℓx ≤ x ≤ ux
X = xx T• relaxing X − xx T = 0 to X − xx T ⪰ 0, which is equivalent to
!
1 xT
X̃ :=
⪰ 0,
x X
yields a semidefinite programming relaxation• Anstreicher [2009]: the SDP and RLT relaxations do not dominate each other;
combining both can produce substantially better bounds

SDP Cuts

SDP is computationally demanding, so approximate by linear inequalities:• for X̃ ∗ ̸⪰ 0 compute eigenvector v with eigenvalue λ < 0, then⟨v , X̃ v ⟩ ≥ 0
is a valid cut that cuts off X̃ ∗ [Sherali and Fraticelli, 2002]• these cuts can be very dense (involve many variables), which slows down the LP
solverSDP Cuts

SDP is computationally demanding, so approximate by linear inequalities:• for X̃ ∗ ̸⪰ 0 compute eigenvector v with eigenvalue λ < 0, then⟨v , X̃ v ⟩ ≥ 0
is a valid cut that cuts off X̃ ∗ [Sherali and Fraticelli, 2002]• these cuts can be very dense (involve many variables), which slows down the LP
solverApproaches for sparser cuts:• Qualizza et al. [2009]: relax cut by setting entries of v to 0
• Saxena et al. [2011]: project into x-variables space (no X variables in cut)
• Sherali et al. [2012]: consider only a subset of variables and corresponding
submatrix of X
• Baltean-Lugojan et al. [2018]: pick submatrix via neural network• SCIP [Bestuzheva et al., 2021]: consider only two variables and corresponding 2 × 2
submatrix of X

Second Order Cones (SOC)
Consider a constraintx T Ax + b T x ≤ c.

If A has only one negative eigenvalue, it may be reformulated as a second-order cone
constraint [Mahajan and Munson, 2010], e.g.,
v
u N
N
uX
X
2
t
xk2 − xN+1
≤ 0, xN+1 ≥ 0⇔
xk2 ≤ xN+1
k=1

•

k=1

qP
N

2
k=1 xk is a convex term that can easily be linearized

Example: x 2 + y 2 − z 2 ≤ 0 in [−1, 1] × [−1, 1] × [0, 1]

feasible region

not recognizing SOC

recognizing SOC(initial relaxation)

Cone Disaggregation
For high-dimensional cones (large N), linearizations of⇒ slow LP solves.

qP
N2
k=1 xk generate dense cutsCone Disaggregation
For high-dimensional cones (large N), linearizations of⇒ slow LP solves.

qP
N2
k=1 xk generate dense cuts

Vielma et al. [2016]: consider disaggregated formulation in extended space:• introduce new variables zk , k = 1, . . . , N and add
constraints
zk ≥• then SOC

P

xk2
xN+1

,

N
X

zk ≤ xN+1

k=1

2
2
k xk ≤ xN+1 is satisfied because

1
xN+1

N
X
k=1

xk2 ≤

N
X

zk ≤ xN+1

k=1

2• new cons. xk /xN+1 ≤ zk are 3-dimensional SOC:
xk2 ≤ zk xN+1 = 1/4((zk + xN+1 )2 − (zk − xN+1 )2 )q⇔
4xk2 + (zk − xN+1 )2 ≤ zk + xN+1⇓

Convexity Detection
Analyze the Hessian:f (x) convex on [ℓ, u]⇔∇2 f (x) ⪰ 0∀x ∈ [ℓ, u]• f (x) quadratic: ∇2 f (x) constant ⇒ compute spectrum numerically• general f ∈ C 2 : estimate eigenvalues of Interval-Hessian [Nenov et al., 2004]

Convexity Detection
Analyze the Hessian:f (x) convex on [ℓ, u]⇔∇2 f (x) ⪰ 0∀x ∈ [ℓ, u]• f (x) quadratic: ∇2 f (x) constant ⇒ compute spectrum numerically• general f ∈ C 2 : estimate eigenvalues of Interval-Hessian [Nenov et al., 2004]
Analyze the Algebraic Expression:convex,f (x) convex ⇒ a · f (x)concave,a≥0a≤0f (x), g (x) convex ⇒ f (x) + g (x) convex
f (x) concave ⇒ log(f (x)) concaveei ≤ 0 ∀iconvex,Y ePif (x) =
xi , xi ≥ 0 ⇒ f (x) convex,∃j : ei ≤ 0 ∀i ̸= j;i ei ≥ 1Piconcave, ei ≥ 0 ∀i;
i ei ≤ 1[Maranas and Floudas, 1995, Bao, 2007, Fourer et al., 2009, Vigerske, 2013]

Analyze Expression for Hessian: Klaus, Merk, Wiedom, Laue, and Giesen [2022]

Stronger relaxations with semi-continuous variables
Considerx2 ≤ w,
That is, x ∈ {0} ∪ [ℓ, u].

ℓy ≤ x ≤ uy ,y ∈ {0, 1},(with ℓ > 0).

Stronger relaxations with semi-continuous variables
Considerx2 ≤ w,ℓy ≤ x ≤ uy ,y ∈ {0, 1},(with ℓ > 0).

That is, x ∈ {0} ∪ [ℓ, u].
A tight relaxation would be the convex hull of relaxations for y = 0 and y = 1:conv 

{(0, w , 0) : w ≥ 0}
|
{z
}
y =0

∪

{(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]}
{z
}
|
y =1

By just relaxing y ∈ {0, 1} to y ∈ [0, 1], one does not get this set.

Stronger relaxations with semi-continuous variables
Considerx2 ≤ w,ℓy ≤ x ≤ uy ,y ∈ {0, 1},(with ℓ > 0).

That is, x ∈ {0} ∪ [ℓ, u].
A tight relaxation would be the convex hull of relaxations for y = 0 and y = 1:conv 

{(0, w , 0) : w ≥ 0}
|
{z
}
y =0

∪

{(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]}
{z
}
|




y =1

By just relaxing y ∈ {0, 1} to y ∈ [0, 1], one does not get this set.
However, replacing x 2 ≤ w by the SOC x 2 ≤ w y and w ≥ 0 is sufficient.
[Günlük and Linderoth, 2012]

Why x 2 ≤ wy ?

conv({(0, w , 0) : w ≥ 0} ∪ {(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]})Why x 2 ≤ wy ?

conv({(0, w , 0) : w ≥ 0} ∪ {(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]})
|
{z
}
{z
}
|
∋(x0 ,w0 ,y0 )











= (x, w , y ) :










∋(x1 ,w1 ,y1 )
x = λx1 + (1 − λ)x0 ,w = λw1 + (1 − λ)w0 ,y = λy1 + (1 − λ)y0 ,
x0 = 0, y0 = 0, w0 ≥ 0,
2
x1 ≤ w1 , x1 ∈ [ℓ, u], y1 = 1 λ ∈ [0, 1]

Why x 2 ≤ wy ?

conv({(0, w , 0) : w ≥ 0} ∪ {(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]})
|
{z
}
{z
}
|
∋(x0 ,w0 ,y0 )











= (x, w , y ) :










x = λx1
w = λw1 + (1 − λ)w0 ,y =λ
w0 ≥ 0,2
x1 ≤ w1 , x1 ∈ [ℓ, u],
λ ∈ [0, 1]∋(x1 ,w1 ,y1 )





















Why x 2 ≤ wy ?

conv({(0, w , 0) : w ≥ 0} ∪ {(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]})
|
{z
}
{z
}
|
∋(x0 ,w0 ,y0 )











= (x, w , y ) :











= (x, w , y ) :
|for w0 =0,λ>0,∋(x1 ,w1 ,y1 )
x = λx1
w = λw1 + (1 − λ)w0 ,




y =λ

w0 ≥ 0,2
x1 ≤ w1 , x1 ∈ [ℓ, u],λ ∈ [0, 1]

 2
x
w x

≤ , ∈ [ℓ, u],∪ {(0, w , 0) : w ≥ 0}
y
y y
 |
{z
}
y ∈ (0, 1]
for w0 ≥0,λ=0{z}using x1 =x/λ,w1 =w /λ,λ=y

Why x 2 ≤ wy ?

conv({(0, w , 0) : w ≥ 0} ∪ {(x, w , 1) : x 2 ≤ w , x ∈ [ℓ, u]})
|
{z
}
{z
}
|
∋(x0 ,w0 ,y0 )











= (x, w , y ) :











= (x, w , y ) :
|for w0 =0,λ>0,∋(x1 ,w1 ,y1 )
x = λx1
w = λw1 + (1 − λ)w0 ,




y =λ

w0 ≥ 0,2
x1 ≤ w1 , x1 ∈ [ℓ, u],λ ∈ [0, 1]

 2
x
w x

≤ , ∈ [ℓ, u],∪ {(0, w , 0) : w ≥ 0}
y
y y
 |
{z
}
y ∈ (0, 1]
for w0 ≥0,λ=0{z}using x1 =x/λ,w1 =w /λ,λ=y
= (x, w , y ) : x 2 ≤ wy , ℓy ≤ x ≤ uy , w ≥ 0, y ∈ [0, 1]

Convex Hull of Point and Convex Set

More general, consider{(0, 0)}∪{(x, 1) : f (x) ≤ 0, ℓ ≤ x ≤ u}

(f convex)

As before, build the convex combination of both sets and eliminate variables:{(x, y ) : f (x/y ) ≤ 0, ℓy ≤ x ≤ uy , y ∈ (0, 1]} ∪ {(0, 0)}[Günlük and Linderoth, 2012]

Convex Hull of Point and Convex Set

More general, consider{(0, 0)}∪{(x, 1) : f (x) ≤ 0, ℓ ≤ x ≤ u}

(f convex)

As before, build the convex combination of both sets and eliminate variables:{(x, y ) : f (x/y ) ≤ 0, ℓy ≤ x ≤ uy , y ∈ (0, 1]} ∪ {(0, 0)}= {(x, y ) : f˜(x, y ) ≤ 0, ℓy ≤ x ≤ uy , y ∈ [0, 1]},

where f˜(x, y ) =y f (x/y ),
0,



∞,

if y > 0,
if y = 0,

is the perspective function of f (x).

otherwise,

Important property: If f is convex, then f˜ is convex.

[Günlük and Linderoth, 2012]

Perspective Cuts
Applying the perspective reformulation (replacing f (x) by f˜(x, y )) in a problem can beproblematic, because f˜(x, y ) is not differentiable at y = 0.
Frangioni and Gentile [2006]: effect of perspective reformulation can be captured in
LP relaxation by supporting hyperplanes on the epigraph of f˜(x, y ):

Perspective Cuts
Applying the perspective reformulation (replacing f (x) by f˜(x, y )) in a problem can beproblematic, because f˜(x, y ) is not differentiable at y = 0.
Frangioni and Gentile [2006]: effect of perspective reformulation can be captured in
LP relaxation by supporting hyperplanes on the epigraph of f˜(x, y ):• linearization of f (x) ≤ 0 at x = x̂:
f (x̂) + ∇f (x̂)(x − x̂) ≤ 0• perspective cut tilts cut to be tight at (x, y ) = (0, 0) by adding(f (0) − f (x̂) + ∇f (x̂)x̂)(1 − y ):f (x̂)y + ∇f (x̂)(x − x̂y ) + f (0)(1 − y ) ≤ 0
Check: y = 0 ⇒ x = 0 ⇒ left-hand-side = f (0)y = 1 ⇒ left-hand-side = f (x̂) + ∇f (x̂)(x − x̂)Perspective Cuts
Applying the perspective reformulation (replacing f (x) by f˜(x, y )) in a problem can beproblematic, because f˜(x, y ) is not differentiable at y = 0.
Frangioni and Gentile [2006]: effect of perspective reformulation can be captured in
LP relaxation by supporting hyperplanes on the epigraph of f˜(x, y ):• linearization of f (x) ≤ 0 at x = x̂:
f (x̂) + ∇f (x̂)(x − x̂) ≤ 0• perspective cut tilts cut to be tight at (x, y ) = (0, 0) by adding(f (0) − f (x̂) + ∇f (x̂)x̂)(1 − y ):f (x̂)y + ∇f (x̂)(x − x̂y ) + f (0)(1 − y ) ≤ 0
Check: y = 0 ⇒ x = 0 ⇒ left-hand-side = f (0)y = 1 ⇒ left-hand-side = f (x̂) + ∇f (x̂)(x − x̂)• example: f (x) = x 2 , x̂ = 1• linearization cut: 1 + 2(x − 1) ≤ 0; at x = 0: −1 ≤ 0 ⇒ not active• perspective cut: y + 2(x − y ) ≤ 0; at (x, y ) = (0, 0): 0 ≤ 0 ⇒ active, thus tighter

Further Techniques
Primal Side (Find Feasible Solutions)Sub-NLP Heuristics

Given a solution satisfying all integrality constraints,• fix all integer variables in the MINLP• call an NLP solver to find a local solution to theremaining NLP

minSub-NLP Heuristics

Given a solution satisfying all integrality constraints,• fix all integer variables in the MINLP• call an NLP solver to find a local solution to theremaining NLP• variable fixings given by integer-feasible solution to LP
relaxation (maybe from running MIP heuristics on MIP
relaxation)minSub-NLP Heuristics

Given a solution satisfying all integrality constraints,• fix all integer variables in the MINLP• call an NLP solver to find a local solution to theremaining NLP• variable fixings given by integer-feasible solution to LP
relaxation (maybe from running MIP heuristics on MIP
relaxation)min

Multistart: run local NLP solver from random starting points to increase likelihood offinding global optimum
Smith, Chinneck, and Aitken [2013]: sample many random starting points, move themcheaply towards feasible region (average gradients of violated constraints), cluster, run
NLP solvers from (few) center of cluster

Sub-NLP Heuristics

Given a solution satisfying all integrality constraints,• fix all integer variables in the MINLP• call an NLP solver to find a local solution to theremaining NLP• variable fixings given by integer-feasible solution to LP
relaxation (maybe from running MIP heuristics on MIP
relaxation)min

Multistart: run local NLP solver from random starting points to increase likelihood offinding global optimum
Smith, Chinneck, and Aitken [2013]: sample many random starting points, move themcheaply towards feasible region (average gradients of violated constraints), cluster, run
NLP solvers from (few) center of cluster
NLP-Diving: solve NLP relaxation, restrict bounds on fractional variable, repeat

Sub-MIP / Sub-MINLP Heuristics“Undercover” (SCIP) [Berthold and Gleixner, 2014]:• Fix nonlinear variables, so problem becomes MIP• not always necessary to fix all nonlinear variables, e.g.,consider x · y• find a minimal set of variables to fix by solving a Set
Covering Problem

Sub-MIP / Sub-MINLP Heuristics“Undercover” (SCIP) [Berthold and Gleixner, 2014]:• Fix nonlinear variables, so problem becomes MIP• not always necessary to fix all nonlinear variables, e.g.,consider x · y• find a minimal set of variables to fix by solving a Set
Covering Problem
Large Neighborhood Search [Berthold et al., 2011]:• RENS [Berthold, 2014]: fix integer variables with integral
value in LP relaxation• RINS, DINS, Crossover, Local BranchingAlternating Direction

Feasibility Pump [D’Ambrosio, Frangioni, Liberti, and Lodi, 2010, 2012, Belotti andBerthold, 2017]:• originally for MIP [Fischetti, Glover, and Lodi, 2005]• MINLP: alternately find feasible solutions to MIP and NLP relaxations• solution of NLP relaxation is “rounded” to solution of MIP relaxation (by various
methods trading solution quality with computational effort)• solution of MIP relaxation is projected onto NLP relaxation (local search)• Geißler, Morsi, Schewe, and Schmidt [2017]: modifications for convergent
algorithm (avoid cycling)Solver Software

Solvers

The following gives a list of MINLP solvers.
• it is incomplete• omitted solvers that do not seem to be maintained anymore• omitted continuous-only (NLP) solvers, e.g., COCONUT [Neumaier, 2001], Ibex
(http://www.ibex-lib.org), RAPOSa [González-Rodríguez et al., 2022], . . .
• omitted solvers without guarantee for global optimality, e.g., LocalSolver• solver surveys:• Kronqvist, Bernal, Lundell, and Grossmann [2019]• Bussieck and Vigerske [2010]

Solver Software
Solvers for Mixed-Integer Quadratic
Programs

Solvers for Mixed-Integer Quadratic Programs

CPLEX:

https://www.ibm.com/products/ilog-cplex-optimization-studio• commercial solver by IBM, unclear future• available for all modeling languages and APIs to many languages• convex quadratic objective and constraints• second-order cone (SOC) constraints• nonconvex quadratic objective (spatial branch-and-bound)• branch-and-bound with LP and SOCP (SOC program) relaxation

Solvers for Mixed-Integer Quadratic Programs

CPLEX:

https://www.ibm.com/products/ilog-cplex-optimization-studio• commercial solver by IBM, unclear future• available for all modeling languages and APIs to many languages• convex quadratic objective and constraints• second-order cone (SOC) constraints• nonconvex quadratic objective (spatial branch-and-bound)• branch-and-bound with LP and SOCP (SOC program) relaxation
GUROBI:

https://www.gurobi.com• commercial solver by GUROBI• available for many modeling languages and APIs to many languages• convex and nonconvex quadratic objective and constraints• SOC constraints• branch-and-bound with LP and SOCP (SOC program) relaxation

Solvers for Mixed-Integer Quadratic Programs (cont.)

MINOTAUR:[Mahajan, Leyffer, Linderoth, Luedtke, and Munson, 2021]
https://github.com/coin-or/minotaur• open-source solver by IIT Bombay, Argonne Lab, and UW Madison• available for AMPL and C++ API• convex and nonconvex quadratic objective and constraints• spatial branch-and-bound with LP relaxation

Solvers for Mixed-Integer Quadratic Programs (cont.)

MINOTAUR:[Mahajan, Leyffer, Linderoth, Luedtke, and Munson, 2021]
https://github.com/coin-or/minotaur• open-source solver by IIT Bombay, Argonne Lab, and UW Madison• available for AMPL and C++ API• convex and nonconvex quadratic objective and constraints• spatial branch-and-bound with LP relaxation
MOSEK:

https://www.mosek.com• commercial solver by MOSEK ApS• available for many modeling languages and APIs to many languages• convex quadratic objectives and constraints• SOC constraints• branch-and-bound with LP and SOCP (SOC program) relaxation• also SDP and some other conesSolvers for Mixed-Integer Quadratic Programs (cont.)
Pajarito:[Coey, Lubin, and Vielma, 2020]

https://github.com/jump-dev/Pajarito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan Pablo Vielma• available for JuMP, implemented in Julia• SOC constraints, and other cones• outer-approximation algorithmSolvers for Mixed-Integer Quadratic Programs (cont.)
Pajarito:[Coey, Lubin, and Vielma, 2020]

https://github.com/jump-dev/Pajarito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan Pablo Vielma• available for JuMP, implemented in Julia• SOC constraints, and other cones• outer-approximation algorithm
SMIQP:[Elloumi and Lambert, 2019]https://github.com/amelie-lambert/SMIQP• open-source solver by Amélie Lambert (CNAM CEDRIC, Paris)• spatial branch-and-bound with quadratic convex relaxation (constructed via QCR
method)Solvers for Mixed-Integer Quadratic Programs (cont.)
Pajarito:[Coey, Lubin, and Vielma, 2020]

https://github.com/jump-dev/Pajarito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan Pablo Vielma• available for JuMP, implemented in Julia• SOC constraints, and other cones• outer-approximation algorithm
SMIQP:[Elloumi and Lambert, 2019]https://github.com/amelie-lambert/SMIQP• open-source solver by Amélie Lambert (CNAM CEDRIC, Paris)• spatial branch-and-bound with quadratic convex relaxation (constructed via QCR
method)XPRESS:https://www.fico.com/en/products/fico-xpress-optimization• commercial solver by FICO
• available for many modeling languages and APIs to many languages• convex quadratic objective and constraints• second-order cone (SOC) constraints• global MINLP solver announced

Solver Software
Solvers for Convex MINLPSolvers for Convex MINLP

AOA:

https://documentation.aimms.com/platform/solvers/aoa.html• integrated in AIMMS modeling system• outer-approximation algorithm[Kocis and Grossmann, 1989]

DICOPT:

https://distdocs.gams.com/41/docs/S_DICOPT.html• integrated in GAMS modeling system• outer-approximation algorithmSolvers for Convex MINLP

AOA:

https://documentation.aimms.com/platform/solvers/aoa.html• integrated in AIMMS modeling system• outer-approximation algorithm[Kocis and Grossmann, 1989]

DICOPT:

https://distdocs.gams.com/41/docs/S_DICOPT.html• integrated in GAMS modeling system• outer-approximation algorithm
Juniper:[Kröger, Coffrin, Hijazi, and Nagarajan, 2018]https://github.com/lanl-ansi/juniper.jl• open-source solver by Los Alamos Lab• available for JuMP, implemented in Julia• NLP-based branch-and-boundSolvers for Convex MINLP (cont.)
Knitro:https://www.artelys.com/solvers/knitro• commercial solver by Artelys• available for several modeling systems and many APIs
• LP/NLP-based branch-and-bound, mixed-integer sequential quadratic
programming

Solvers for Convex MINLP (cont.)
Knitro:https://www.artelys.com/solvers/knitro• commercial solver by Artelys• available for several modeling systems and many APIs
• LP/NLP-based branch-and-bound, mixed-integer sequential quadratic
programming
MINOTAUR:[Mahajan, Leyffer, Linderoth, Luedtke, and Munson, 2021]
https://github.com/coin-or/minotaur• open-source solver by IIT Bombay, Argonne Lab, and UW Madison• available for AMPL and C++ API• LP-, QP-, and NLP-based branch-and-bound with fast warmstarts,
outer-approximation

Solvers for Convex MINLP (cont.)
Knitro:https://www.artelys.com/solvers/knitro• commercial solver by Artelys• available for several modeling systems and many APIs
• LP/NLP-based branch-and-bound, mixed-integer sequential quadratic
programming
MINOTAUR:[Mahajan, Leyffer, Linderoth, Luedtke, and Munson, 2021]
https://github.com/coin-or/minotaur• open-source solver by IIT Bombay, Argonne Lab, and UW Madison• available for AMPL and C++ API• LP-, QP-, and NLP-based branch-and-bound with fast warmstarts,
outer-approximation
Muriqui:[Melo, Fampa, and Raupp, 2020]

https://wendelmelo.net/software• open-source solver by Wendel Melo, Marcia Fampa, and Fernanda Raupp• available for AMPL and GAMS and C++ API• LP/NLP-based branch-and-bound, outer-approximation, various hybrids

Solvers for Convex MINLP (cont.)
Pavito:https://github.com/jump-dev/Pavito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan P. Vielma• available for JuMP, implemented in Julia• LP/NLP-based branch-and-bound, outer-approximation• sibling of Pajarito [Coey et al., 2020]

Solvers for Convex MINLP (cont.)
Pavito:https://github.com/jump-dev/Pavito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan P. Vielma• available for JuMP, implemented in Julia• LP/NLP-based branch-and-bound, outer-approximation• sibling of Pajarito [Coey et al., 2020]
SHOT:[Lundell, Kronqvist, and Westerlund, 2022, Lundell and Kronqvist, 2022]

https://shotsolver.dev• open-source solver by Andreas Lundell and Jan Kronqvist• available for AMPL and GAMS, Mathematica, C++ API• LP-based branch-and-bound and outer-approximation with supporting hyperplanes(EHP algorithm)• can utilize GUROBI for nonconvex quadratics

Solvers for Convex MINLP (cont.)
Pavito:https://github.com/jump-dev/Pavito.jl• open-source solver by Chris Coey, Miles Lubin, and Juan P. Vielma• available for JuMP, implemented in Julia• LP/NLP-based branch-and-bound, outer-approximation• sibling of Pajarito [Coey et al., 2020]
SHOT:[Lundell, Kronqvist, and Westerlund, 2022, Lundell and Kronqvist, 2022]

https://shotsolver.dev• open-source solver by Andreas Lundell and Jan Kronqvist• available for AMPL and GAMS, Mathematica, C++ API• LP-based branch-and-bound and outer-approximation with supporting hyperplanes(EHP algorithm)• can utilize GUROBI for nonconvex quadratics
XPRESS-SLP:

https://www.fico.com/en/products/fico-xpress-optimization• commercial solver by FICO
• available for several modeling systems, several APIs
• mixed-integer sequential linear programming (NLP-based branch-and-bound orsequence of MIP approximations)Solver Software
Solvers for General MINLPSolvers for General MINLP
Alpine: [Nagarajan, Lu, Yamangil, and Bent, 2016, Nagarajan, Lu, Wang, Bent, andSundar, 2019]https://github.com/lanl-ansi/Alpine.jl• open-source solver by LANL-ANSI (Los Alamos)• available for JuMP, implemented in Julia• at most polynomials• adaptive, piecewise-linear McCormick convexification scheme

Solvers for General MINLP
Alpine: [Nagarajan, Lu, Yamangil, and Bent, 2016, Nagarajan, Lu, Wang, Bent, andSundar, 2019]https://github.com/lanl-ansi/Alpine.jl• open-source solver by LANL-ANSI (Los Alamos)• available for JuMP, implemented in Julia• at most polynomials• adaptive, piecewise-linear McCormick convexification scheme
BARON: [Sahinidis, 1996, Tawarmalani and Sahinidis, 2005, Khajavirad and Sahinidis,
2018]
https://minlp.com• commercial solver by The Optimization Firm
• available for AIMMS, AMPL, GAMS, JuMP, and more
• spatial branch-and-bound with LP (sometimes also MIP, NLP) relaxation

Solvers for General MINLP
Alpine: [Nagarajan, Lu, Yamangil, and Bent, 2016, Nagarajan, Lu, Wang, Bent, andSundar, 2019]https://github.com/lanl-ansi/Alpine.jl• open-source solver by LANL-ANSI (Los Alamos)• available for JuMP, implemented in Julia• at most polynomials• adaptive, piecewise-linear McCormick convexification scheme
BARON: [Sahinidis, 1996, Tawarmalani and Sahinidis, 2005, Khajavirad and Sahinidis,
2018]
https://minlp.com• commercial solver by The Optimization Firm
• available for AIMMS, AMPL, GAMS, JuMP, and more
• spatial branch-and-bound with LP (sometimes also MIP, NLP) relaxation
EAGO:[Wilhelm and Stuber, 2020]

https://github.com/PSORLab/EAGO.jl• open-source solver by Matthew Wilhelm, PSOR Lab at Uni. of Connecticut• available for JuMP, implemented in Julia• propagating McCormick relaxations along the factorable structure of each
expression (spatial branch-and-bound without auxiliary variables)

Solvers for General MINLP (cont.)
Lindo API:

[Lin and Schrage, 2009]https://www.lindo.com• commercial solver by Lindo Systems, Inc.
• available for LINGO and GAMS; APIs for MATLAB, C++, and other• spatial branch-and-bound with nonlinear relaxations

Solvers for General MINLP (cont.)
Lindo API:

[Lin and Schrage, 2009]https://www.lindo.com• commercial solver by Lindo Systems, Inc.
• available for LINGO and GAMS; APIs for MATLAB, C++, and other• spatial branch-and-bound with nonlinear relaxations
MAiNGO:[Bongartz, Najman, Sass, and Mitsos, 2018]https://git.rwth-aachen.de/avt-svt/public/maingo• open-source solver by RWTH Aachen, Germany• C++ and Python APIs
• propagating McCormick relaxations along the factorable structure of each
expression (spatial branch-and-bound without auxiliary variables)

Solvers for General MINLP (cont.)
Lindo API:

[Lin and Schrage, 2009]https://www.lindo.com• commercial solver by Lindo Systems, Inc.
• available for LINGO and GAMS; APIs for MATLAB, C++, and other• spatial branch-and-bound with nonlinear relaxations
MAiNGO:[Bongartz, Najman, Sass, and Mitsos, 2018]https://git.rwth-aachen.de/avt-svt/public/maingo• open-source solver by RWTH Aachen, Germany• C++ and Python APIs
• propagating McCormick relaxations along the factorable structure of each
expression (spatial branch-and-bound without auxiliary variables)
Octeract:• commercial solver by Octeract Limited• available for AIMMS, AMPL, GAMS, JuMP and C++ API• spatial branch-and-bound with linear relaxation

https://octeract.gg

Solvers for General MINLP (cont.)

SCIP:[Achterberg, 2009, Bestuzheva, Besançon, Chen, Chmiela, Donkiewicz, vanDoornmalen, Eifler, Gaul, Gamrath, Gleixner, Gottwald, Graczyk, Halbig, Hoen, Hojny,
van der Hulst, Koch, Lübbecke, Maher, Matter, Mühmer, Müller, Pfetsch, Rehfeldt,
Schlein, Schlösser, Serrano, Shinano, Sofranac, Turner, Vigerske, Wegscheider,
Wellner, Weninger, and Witzig, 2021, Bestuzheva, Chmiela, Müller, Serrano, Vigerske,
and Wegscheider, 2023]
https://www.scipopt.org/• open-source solver by Zuse Institute Berlin, TU Darmstadt, RWTH Aachen, TU
Eindhoven, FAU Erlangen, GAMS, etc• available for AMPL, GAMS, JuMP, . . . ; APIs for C, Matlab, Python, . . .
• part of a solver for constraint integer programs• spatial branch-and-bound with linear relaxation

End.

Thank you for your attention!

Some MINLP reviews:• Burer and Letchford [2012]• Belotti, Kirches, Leyffer, Linderoth, Luedtke, and Mahajan [2013]• Boukouvala, Misener, and Floudas [2016]• Kılınç and Sahinidis [2017]• Kronqvist, Bernal, Lundell, and Grossmann [2019]
Some books:• Lee and Leyffer [2012]• Locatelli and Schoen [2013]

Literature i

References
Tobias Achterberg. SCIP: Solving Constraint Integer Programs. Mathematical Programming
Computation, 1(1):1–41, 2009. doi:10.1007/s12532-008-0001-1.
Warren P. Adams and Hanif D. Sherali. A tight linearization and an algorithm for zero-one quadratic
programming problems. Management Science, 32(10):1274–1290, 1986.
doi:10.1287/mnsc.32.10.1274.
Kurt Anstreicher. Semidefinite programming versus the reformulation-linearization technique fornonconvex quadratically constrained quadratic programming. Journal of Global Optimization, 43(2):471–484, 2009. ISSN 0925-5001. doi:10.1007/s10898-008-9372-0.
Radu Baltean-Lugojan, Pierre Bonami, Ruth Misener, and Andrea Tramontani. Scoring positive
semidefinite cutting planes for quadratic optimization via trained neural networks. Technical Report6943, Optimization Online, 2018. URL https://optimization-online.org/2018/11/6943/.
X. Bao. Automatic convexity detection for global optimization. Master’s thesis, University of Illinois at
Urbana-Champaign, 2007.
Pietro Belotti. Bound reduction using pairs of linear inequalities. Journal of Global Optimization, 56(3):787–819, 2013. doi:10.1007/s10898-012-9848-9.
Pietro Belotti and Timo Berthold. Three ideas for a feasibility pump for nonconvex minlp. Optimization
Letters, 11(1):3–15, 2017. doi:10.1007/s11590-016-1046-0.

Literature ii
Pietro Belotti, Jon Lee, Leo Liberti, F. Margot, and Andreas Wächter. Branching and bounds
tightening techniques for non-convex MINLP. Optimization Methods and Software, 24(4-5):
597–634, 2009. doi:10.1080/10556780903087124.
Pietro Belotti, Sonia Cafieri, Jon Lee, and Leo Liberti. Feasibility-based bounds tightening via fixed
points. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications,volume 6508 of Lecture Notes in Computer Science, pages 65–76. Springer, Berlin/Heidelberg, 2010.
doi:10.1007/978-3-642-17458-2_7.
Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, Jim Luedtke, and Ashutosh Mahajan.
Mixed-integer nonlinear optimization. Acta Numerica, 22:1–131, 2013.
doi:10.1017/S0962492913000032.
F. Benhamou, C. Bliek, B. Faltings, L. Granvilliers, E. Huens, E. Monfroy, A. Neumaier,
D. Sam-Haroud, P. Spellucci, P. Van Hentenryck, and L. Vicente. Algorithms for solving nonlinear
constrained and optimization problems: The state of the art. Technical report, Universität Wien,
Fakultät für Mathematik, 2001. URL
http://www.mat.univie.ac.at/~neum/glopt/coconut/StArt.html.
Timo Berthold. RENS – the optimal rounding. Mathematical Programming Computation, 6(1):33–54,
2014. doi:10.1007/s12532-013-0060-9.
Timo Berthold and Ambros M. Gleixner. Undercover: a primal MINLP heuristic exploring a largest
sub-MIP. Mathematical Programming, 144(1-2):315–346, 2014. doi:10.1007/s10107-013-0635-2.
Timo Berthold, Stefan Heinz, Marc E. Pfetsch, and Stefan Vigerske. Large neighborhood search beyond
MIP. In Luca Di Gaspero, Andrea Schaerf, and Thomas Stützle, editors, Proceedings of the 9th
Metaheuristics International Conference (MIC 2011), pages 51–60, 2011. urn:nbn:de:0297-zib-12989.

Literature iii

Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van
Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph
Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch,
Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E.
Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro
Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, andJakob Witzig. The SCIP Optimization Suite 8.0. ZIB Report 21-41, Zuse Institute Berlin, 2021.
urn:nbn:de:0297-zib-85309.
Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller, Felipe Serrano, Stefan Vigerske, and Fabian
Wegscheider. Global optimization of mixed-integer nonlinear programs with SCIP 8. Technical
Report 2301.00587, arXiv, 2023.
D. Bongartz, J. Najman, S. Sass, and A. Mitsos. MAiNGO – McCormick-based algorithm formixed-integer nonlinear global optimization. Technical report, Process Systems Engineering(AVT.SVT), RWTH Aachen University, 2018. URL
http://permalink.avt.rwth-aachen.de/?id=729717.
Fani Boukouvala, Ruth Misener, and Christodoulos A. Floudas. Global optimization advances inmixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO.
European Journal of Operational Research, 252(3):701–727, 2016. doi:10.1016/j.ejor.2015.12.018.
Samuel Burer and Adam N. Letchford. Non-convex mixed-integer nonlinear programming: A survey.
Surveys in Operations Research and Management Science, 17(2):97–106, 2012.
doi:10.1016/j.sorms.2012.08.001.

Literature iv
Michael R. Bussieck and S. Vigerske. MINLP solver software. In J. J. Cochran et.al., editor, Wiley
Encyclopedia of Operations Research and Management Science. Wiley & Sons, Inc., 2010.
doi:10.1002/9780470400531.eorms0527.
Chris Coey, Miles Lubin, and Juan Pablo Vielma. Outer approximation with conic certificates formixed-integer convex problems. Mathematical Programming Computation, 12(2):249–293, 2020.
doi:10.1007/s12532-020-00178-3.
Claudia D’Ambrosio, Antonio Frangioni, Leo Liberti, and Andrea Lodi. Experiments with a feasibility
pump approach for non-convex MINLPs. In Paola Festa, editor, Proceedings of 9th International
Symposium on Experimental Algorithms, SEA 2010, volume 6049 of Lecture Notes in Computer
Science, pages 350–360. Springer, 2010. doi:10.1007/978-3-642-13193-6_30.
Claudia D’Ambrosio, Antonio Frangioni, Leo Liberti, and Andrea Lodi. A storm of feasibility pumps fornonconvex MINLP. Mathematical Programming, 136(2):375–402, 2012.
doi:10.1007/s10107-012-0608-x.
Marco A. Duran and Ignacio E. Grossmann. An outer-approximation algorithm for a class of
mixed-integer nonlinear programs. Mathematical Programming, 36(3):307–339, 1986.
doi:10.1007/BF02592064.
Sourour Elloumi and Amélie Lambert. Global solution of non-convex quadratically constrained
quadratic programs. Optimization Methods and Software, 34(1):98–114, 2019.
doi:10.1080/10556788.2017.1350675.
Matteo Fischetti, Fred Glover, and Andrea Lodi. The feasibility pump. Mathematical Programming,
104(1):91–104, 2005. doi:10.1007/s10107-004-0570-3.

Literature v
Robert Fourer, Chandrakant Maheshwari, Arnold Neumaier, Dominique Orban, and Hermann Schichl.
Convexity and concavity detection in computational graphs: Tree walks for convexity assessment.
INFORMS Journal on Computing, 22(1):26–43, 2009. doi:10.1287/ijoc.1090.0321.
Antonio Frangioni and Claudio Gentile. Perspective cuts for a class of convex 0–1 mixed integer
programs. Mathematical Programming, 106(2):225–236, 2006. doi:10.1007/s10107-005-0594-3.
Bjö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.
Ambros M. Gleixner, Timo Berthold, Benjamin Müller, and Stefan Weltge. Three enhancements for
optimization-based bound tightening. Journal of Global Optimization, 67:731–757, 2017.
doi:10.1007/s10898-016-0450-4.
Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bull. AMS, 64(5):275–278, 1958.
Brais González-Rodríguez, Joaquín Ossorio-Castillo, Julio González-Díaz, Ángel M. González-Rueda,
David R. Penas, and Diego Rodríguez-Martínez. Computational advances in polynomial
optimization: RAPOSa, a freely available global solver. Journal of Global Optimization, 2022. ISSN
1573-2916. doi:10.1007/s10898-022-01229-w.
Oktay Günlük and Jeff T. Linderoth. Perspective reformulation and applications. In Lee and Leyffer[2012], pages 61–89. doi:10.1007/978-1-4614-1927-3_3.
J. E. Kelley. The cutting-plane method for solving convex programs. Journal of the Society for
Industrial and Applied Mathematics, 8(4):703–712, 1960. doi:10.1137/0108053.

Literature vi
Aida Khajavirad and Nikolaos V. Sahinidis. A hybrid LP/NLP paradigm for global optimization
relaxations. Mathematical Programming Computation, 10(3):383–421, 2018.
doi:10.1007/s12532-018-0138-5.
Kamil A. Khan, Harry A. J. Watson, and Paul I. Barton. Differentiable McCormick relaxations. Journalof Global Optimization, 67(4):687–729, 2017. doi:10.1007/s10898-016-0440-6.
Julien Klaus, Niklas Merk, Konstantin Wiedom, Sören Laue, and Joachim Giesen. Convexity certificatesfrom hessians. Technical Report 2210.10430, arXiv, 2022. URL https://arxiv.org/abs/2210.10430.
Gary R. Kocis and Ignacio 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.
Ole Kröger, Carleton Coffrin, Hassan Hijazi, and Harsha Nagarajan. Juniper: An open-source nonlinear
branch-and-bound solver in Julia. In Integration of Constraint Programming, Artificial Intelligence,and Operations Research, pages 377–386. Springer, 2018. doi:10.1007/978-3-319-93031-2_27.
Jan Kronqvist, Andreas Lundell, and Tapio Westerlund. The extended supporting hyperplane algorithm
for convex mixed-integer nonlinear programming. Journal of Global Optimization, 64(2):249–272,
2016. doi:10.1007/s10898-015-0322-3.
Jan Kronqvist, David E. Bernal, Andreas Lundell, and Ignacio E. Grossmann. A review and comparisonof solvers for convex MINLP. Optimization and Engineering, 20(2):397–455, 2019.
doi:10.1007/s11081-018-9411-8.
Mustafa R. Kılınç and Nikolaos V. Sahinidis. Advances and Trends in Optimization with Engineering
Applications, chapter State of the Art in Mixed-Integer Nonlinear Optimization, pages 273–292.
MOS-SIAM Series on Optimization. 2017. doi:10.1137/1.9781611974683.ch21.

Literature vii
Alisa H. Land and Alison G. Doig. An automatic method of solving discrete programming problems.
Econometrica, 28(3):497–520, 1960. doi:10.2307/1910129.
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-4614-1927-3.
Sven Leyffer. Deterministic Methods for Mixed-Integer Nonlinear Programming. PhD thesis,
Department of Mathematics and Computer Science, University of Dundee, 1993.
Youdong Lin and Linus Schrage. The global solver in the LINDO API. Optimization Methods &Software, 24(4–5):657–668, 2009. doi:10.1080/10556780902753221.
Marco Locatelli and Fabio Schoen. Global Optimization: Theory, Algorithms, and Applications.
Number 15 in MOS-SIAM Series on Optimization. SIAM, 2013.
Andreas Lundell and Jan Kronqvist. Polyhedral approximation strategies for nonconvex mixed-integer
nonlinear programming in SHOT. Journal of Global Optimization, 82(4):863–896, 2022.
doi:10.1007/s10898-021-01006-1.
Andreas Lundell, Jan Kronqvist, and Tapio Westerlund. The supporting hyperplane optimization toolkit
for convex MINLP. Journal of Global Optimization, 84(1):1–41, 2022.
doi:10.1007/s10898-022-01128-0.
Ashutosh Mahajan and Todd Munson. Exploiting second-order cone structure for global optimization.
Technical Report ANL/MCS-P1801-1010, Argonne National Laboratory, 2010. URL
http://www.optimization-online.org/DB_HTML/2010/10/2780.html.
Ashutosh Mahajan, Sven Leyffer, and Christian Kirches. Solving mixed-integer nonlinear programs by
QP-diving. Preprint ANL/MCS-P2071-0312, Argonne National Laboratory, 2012. URL
http://www.optimization-online.org/DB_HTML/2012/03/3409.html.

Literature viii
Ashutosh Mahajan, Sven Leyffer, Jeff Linderoth, James Luedtke, and Todd Munson. Minotaur: amixed-integer nonlinear optimization toolkit. Mathematical Programming Computation, 13(2):301–338, 2021. doi:10.1007/s12532-020-00196-1.
Costas D. Maranas and Christodoulos A. Floudas. Finding all solutions of nonlinearly constrained
systems of equations. Journal of Global Optimization, 7(2):143–182, 1995.
doi:10.1007/BF01097059.
Costas D. Maranas and Christodoulos A. Floudas. Global optimization in generalized geometricprogramming. Computers & Chemical Engineering, 21(4):351–369, 1997.
doi:10.1016/S0098-1354(96)00282-7.
Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I –convex underestimating problems. Mathematical Programming, 10(1):147–175, 1976.
doi:10.1007/BF01580665.
Wendel Melo, Marcia Fampa, and Fernanda Raupp. An overview of MINLP algorithms and theirimplementation in Muriqui Optimizer. Annals of Operations Research, 286(1):217–241, 2020.
doi:10.1007/s10479-018-2872-5.
Ruth Misener and Christodoulos A. Floudas. ANTIGONE: Algorithms for coNTinuous / Integer Global
Optimization of Nonlinear Equations. Journal of Global Optimization, 59(2-3):503–526, 2014.
doi:10.1007/s10898-014-0166-2.
Alexander Mitsos, Benoit Chachuat, and Paul I. Barton. McCormick-based relaxations of algorithms.
SIAM Journal on Optimization, 20(2):573–601, 2009. doi:10.1137/080717341.
Ramon E. Moore. Interval Analysis. Englewood Cliffs, NJ: Prentice Hall, 1966.

Literature ix
Harsha Nagarajan, Mowen Lu, Emre Yamangil, and Russell Bent. Tightening McCormick relaxations fornonlinear programs via dynamic multivariate partitioning. In International Conference on Principles
and Practice of Constraint Programming, pages 369–387. Springer, 2016.
doi:10.1007/978-3-319-44953-1_24.
Harsha Nagarajan, Mowen Lu, Site Wang, Russell Bent, and Kaarthik Sundar. An adaptive,
multivariate partitioning algorithm for global optimization of nonconvex programs. Journal of Global
Optimization, 2019. doi:10.1007/s10898-018-00734-1.
Ivo P. Nenov, Daniel H. Fylstra, and Lubomir V. Kolev. Convexity determination in the Microsoft Excel
solver using automatic differentiation techniques. Extended abstract, Frontline Systems Inc., 2004.
URL http://www.autodiff.org/ad04/abstracts/Nenov.pdf.
Arnold Neumaier. Constrained global optimization. In Algorithms for Solving Nonlinear Constrained
and Optimization Problems: The State of The Art Benhamou et al. [2001], chapter 4, pages
55–111. URL http://www.mat.univie.ac.at/~neum/glopt/coconut/StArt.html.
Andrea Qualizza, Pietro Belotti, and François Margot. Linear programming relaxations of quadraticallyconstrained quadratic programs. In Lee and Leyffer [2012], pages 407–426.
doi:10.1007/978-1-4614-1927-3_14.
Ignacio Quesada and Ignacio E. Grossmann. An LP/NLP based branch and bound algorithm for convex
MINLP optimization problems. Computers & Chemical Engineering, 16(10-11):937–947, 1992.
doi:10.1016/0098-1354(92)80028-8.
Ignacio Quesada and Ignacio E. Grossmann. Global optimization algorithm for heat exchanger networks.
Industrial & Engineering Chemistry Research, 32(3):487–499, 1993. doi:10.1021/ie00015a012.
Nikolaos V. Sahinidis. BARON: A general purpose global optimization software package. Journal of
Global Optimization, 8(2):201–205, 1996. doi:10.1007/BF00138693.

Literature x
Anureet Saxena, Pierre Bonami, and Jon Lee. Convex relaxations of non-convex mixed integer
quadratically constrained programs: projected formulations. Mathematical Programming, 130(2):359–413, 2011. ISSN 0025-5610. doi:10.1007/s10107-010-0340-3.
Felipe Serrano, Robert Schwarz, and Ambros Gleixner. On the relation between the extended
supporting hyperplane algorithm and kelley’s cutting plane algorithm. Journal of Global
Optimization, 78:161 – 179, 2020. doi:10.1007/s10898-020-00906-y.
Hanif D. Sherali and W. P. Adams. A Reformulation-Linearization Technique for Solving Discrete andContinuous Nonconvex Problems, volume 31 of Nonconvex Optimization and Its Applications.
Kluwer Academic Publishers, 1999. ISBN 978-0-7923-5487-1.
Hanif D. Sherali and Amine Alameddine. A new reformulation-linearization technique for bilinear
programming problems. Journal of Global Optimization, 2(4):379–410, 1992.
doi:10.1007/BF00122429.
Hanif D. Sherali and Barbara M. P. Fraticelli. Enhancing RLT relaxations via a new class of semidefinite
cuts. Journal of Global Optimization, 22(1):233–261, 2002. ISSN 0925-5001.
doi:10.1023/A:1013819515732.
Hanif D. Sherali and C. H. Tuncbilek. A global optimization algorithm for polynomial programming
problems using a reformulation-linearization technique. Journal of Global Optimization, 2:101–112,
1992. doi:10.1007/BF00121304.
Hanif D. Sherali, Evrim Dalkiran, and Jitamitra Desai. Enhancing RLT-based relaxations for polynomial
programming problems via a new class of v -semidefinite cuts. Computational Optimization andApplications, 52(2):483–506, 2012. doi:10.1007/s10589-011-9425-z.

Literature xi
Edward M. B. Smith and Constantinos C. Pantelides. Global optimization of general process models. In
I. E. Grossmann, editor, Global Optimization in Engineering Design, volume 9 of Nonconvex
Optimization and Its Applications, pages 355–386. Kluwer Academic Publishers, 1996.
doi:10.1007/978-1-4757-5331-8_12.
Edward M. B. Smith and Constantinos C. Pantelides. Global optimisation of nonconvex MINLPs.
Computers & Chemical Engineering, 21(suppl.):S791–S796, 1997.
doi:10.1016/S0098-1354(97)87599-0.
Edward M. B. Smith and Constantinos C. Pantelides. A symbolic reformulation/spatial
branch-and-bound algorithm for the global optimization of nonconvex MINLPs. Computers &Chemical Engineering, 23(4-5):457–478, 1999. doi:10.1016/S0098-1354(98)00286-5.
Laurence Smith, John Chinneck, and Victor Aitken. Improved constraint consensus methods for seeking
feasibility in nonlinear programs. Computational Optimization and Applications, 54(3):555–578,
2013. doi:10.1007/s10589-012-9473-z.
Mohit Tawarmalani and Nikolaos V. Sahinidis. A polyhedral branch-and-cut approach to global
optimization. Mathematical Programming, 103(2):225–249, 2005. doi:10.1007/s10107-005-0581-8.
Arthur F. Veinott. The supporting hyperplane method for unimodal programming. Operations
Research, 15(1):147–152, feb 1967. doi:10.1287/opre.15.1.147.
Juan Pablo Vielma, Iain Dunning, Joey Huchette, and Miles Lubin. Extended formulations in mixed
integer conic quadratic programming. Mathematical Programming Computation, 9(3):369–418,
2016. doi:10.1007/s12532-016-0113-y.
Stefan Vigerske. Decomposition of Multistage Stochastic Programs and a Constraint Integer
Programming Approach to Mixed-Integer Nonlinear Programming. PhD thesis,
Humboldt-Universität zu Berlin, 2013. urn:nbn:de:kobv:11-100208240.

Literature xii

Stefan Vigerske and Ambros Gleixner. SCIP: global optimization of mixed-integer nonlinear programs ina branch-and-cut framework. Optimization Methods and Software, to appear, 2017.
doi:10.1080/10556788.2017.1335312.
Tapio Westerlund and Frank Petterson. An extended cutting plane method for solving convex MINLP
problems. Computers & Chemical Engineering, 19(suppl.):131–136, 1995.
doi:10.1016/0098-1354(95)87027-X.
M. E. Wilhelm and M. D. Stuber. EAGO.jl: easy advanced global optimization in Julia. Optimization
Methods and Software, pages 1–26, 2020. doi:10.1080/10556788.2020.1786566.