View
4
Download
0
Category
Preview:
Citation preview
MINLP: Theory, Algorithms, Applications:Lecture 4, Modeling with MINLP
Jeff LinderothIndustrial and Systems Engineering
University of Wisconsin-Madison
Jonas SchweigerFriedrich-Alexander-Universitat Erlangen-Nurnberg
June 28, 2016
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 1 / 34
Outline
Modeling logical conditions with integer variables
Second-Order Cone Modeling
Piecewise-linear modeling?
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 2 / 34
(Quadratic) Uncapacitated FacilityLocation
Problem studied by Gunluk, Lee, Weismantel [4] and classes of strongcutting planes derived
M : Facility
N : Customer
xij : percentage of customer j ∈ N demand met by facility i ∈Mzi = 1⇔ facility i ∈M is built
Fixed cost for opening facility i ∈MQuadratic cost for meeting demand j ∈ N from facility i ∈M
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 3 / 34
Quadratic Facility Location Problem
A very simple MIQP
min∑i∈M
cizi +∑i∈M
∑j∈N
qijx2ij
subject to
xij ≤ zi ∀i ∈M,∀j ∈ N∑i∈M
xij = 1 ∀j ∈ N
xij ≥ 0 ∀i ∈M,∀j ∈ Nzi ∈ {0, 1} ∀i ∈M
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 4 / 34
Some Additional Problems on UFL
1 If you open k or more facilities, then you must pay a penalty cost of λ
2 If you open facility one or two, then you may not open both facility 3and 4
3 I would like to minimize the maximum (transportation) cost that isrequired to serve any customer
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 5 / 34
How the ????? Do We Do That?
Integer variables are a very powerful modeling tool
Allow one to turn constraints on and off.Indicate whether or not constraints hold.Enforce logical restrictions/conditions in a problem
It is often quite difficult1 to quickly see how one can write theselogical conditions as algebraic conditions (that can then beimplemented in an algebraic modeling language like GAMS)
What follows is the derivation of a kind of “calculus” for automaticallyconverting logical conditions into equivalent algebraic ones
1At least for my puny brainLinderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 6 / 34
How the ????? Do We Do That?
Integer variables are a very powerful modeling tool
Allow one to turn constraints on and off.Indicate whether or not constraints hold.Enforce logical restrictions/conditions in a problem
It is often quite difficult1 to quickly see how one can write theselogical conditions as algebraic conditions (that can then beimplemented in an algebraic modeling language like GAMS)
What follows is the derivation of a kind of “calculus” for automaticallyconverting logical conditions into equivalent algebraic ones
1At least for my puny brainLinderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 6 / 34
General Modeling Forcing Constraints to Hold
A “Calculus” for Logical Modeling
Variable = 1 ⇒ constraint must be satisfied
Suppose we wish to have a constraint hold if an associatedindicator variable δ is flipped to 1. That is...
δ = 1⇒∑
j∈N ajxj ≤ b
This can be represented by the constraint∑j∈N ajxj +Mδ ≤M + b
M is an upper bound for the expression∑
j∈N ajxj − b.
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 7 / 34
General Modeling Forcing Constraints to Hold
The Logic
δ = 1⇒∑
j∈N ajxj ≤ b⇔∑
j∈N ajxj +Mδ ≤M + b
Equivalent to∑
j∈N ajxj − b ≤M(1− δ)δ = 0⇒
∑j∈N ajxj − b ≤M
(true by definition of M)
δ = 1⇒∑
j∈N ajxj − b ≤ 0
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 8 / 34
General Modeling Constraint Holds Implies Variable = 1
Modeling Trick #2: Converse of First
∑j∈N ajxj ≤ b⇒ δ = 1
δ = 0⇒∑
j∈N ajxj 6≤ bδ = 0⇒
∑j∈N ajxj > b
δ = 0⇒∑
j∈N ajxj ≥ b+ ε
If aj , xj are integer, we can choose ε = 1
Model as∑
j∈N ajxj − (m− ε)δ ≥ b+ ε
m is a lower bound for the expression∑
j∈N ajxj − bδ = 0 :
∑j∈N ajxj ≥ b+ ε
δ = 1 : m ≤∑
j∈N ajxj − b (nothing)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 9 / 34
General Modeling Constraint Holds Implies Variable = 1
Modeling Trick #2: Converse of First
∑j∈N ajxj ≤ b⇒ δ = 1
δ = 0⇒∑
j∈N ajxj 6≤ bδ = 0⇒
∑j∈N ajxj > b
δ = 0⇒∑
j∈N ajxj ≥ b+ ε
If aj , xj are integer, we can choose ε = 1
Model as∑
j∈N ajxj − (m− ε)δ ≥ b+ ε
m is a lower bound for the expression∑
j∈N ajxj − bδ = 0 :
∑j∈N ajxj ≥ b+ ε
δ = 1 : m ≤∑
j∈N ajxj − b (nothing)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 9 / 34
General Modeling Constraint Holds Implies Variable = 1
Modeling Trick #2: Converse of First
∑j∈N ajxj ≤ b⇒ δ = 1
δ = 0⇒∑
j∈N ajxj 6≤ bδ = 0⇒
∑j∈N ajxj > b
δ = 0⇒∑
j∈N ajxj ≥ b+ ε
If aj , xj are integer, we can choose ε = 1
Model as∑
j∈N ajxj − (m− ε)δ ≥ b+ ε
m is a lower bound for the expression∑
j∈N ajxj − bδ = 0 :
∑j∈N ajxj ≥ b+ ε
δ = 1 : m ≤∑
j∈N ajxj − b (nothing)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 9 / 34
General Modeling Constraint Holds Implies Variable = 1
Some Last Modeling Tricks
δ = 1⇒∑
j∈N ajxj ≥ b
Model as∑
j∈N ajxj +mδ ≥ m+ b
∑j∈N ajxj ≥ b⇒ δ = 1
Model as∑
j∈N ajxj − (M + ε)δ ≤ b− ε
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 10 / 34
General Modeling Constraint Holds Implies Variable = 1
The Slide of Tricks
δ = 1⇒∑
j∈N ajxj ≤ b∑j∈N ajxj +Mδ ≤M + b∑
j∈N ajxj ≤ b⇒ δ = 1∑j∈N ajxj − (m− ε)δ ≥ b+ ε
δ = 1⇒∑
j∈N ajxj ≥ b∑j∈N ajxj +mδ ≥ m+ b∑
j∈N ajxj ≥ b⇒ δ = 1∑j∈N ajxj − (M + ε)δ ≤ b− ε
∑j∈N ajxj : Constraint
LHS
b: Constraint RHS
M : Upper bound on∑j∈N ajxj − b
m: Lower bound on∑j∈N ajxj − b
ε: Constraint violationamount (ε = 0.01or1)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 11 / 34
General Modeling Constraint Holds Implies Variable = 1
Simple Tricks
These two tricks are very common and can be derived from the “Slideof Tricks”
x > 0⇒ δ = 1
x ≤Mδ
δ = 1⇒ x ≥ mx ≥ mδ
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 12 / 34
General Modeling Constraint Holds Implies Variable = 1
Recall (Quadratic) UFL
min∑i∈M
cizi +∑i∈M
∑j∈N
qijx2ij
subject to
xij ≤ zi ∀i ∈M,∀j ∈ N∑i∈M
xij = 1 ∀j ∈ N
xij ≥ 0 ∀i ∈M,∀j ∈ Nzi ∈ {0, 1} ∀i ∈M
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 13 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 1
If you open k or more facilities, then you must pay a penalty cost of λ
Need (earlier) “fixed cost” logic for zi : (xi ≤ zi)Model
∑i∈M zi ≥ k ⇒ δ1 = 1
Add λδ1 to objective function
Appropriate trick is∑j∈N
ajxj ≥ b⇒ δ = 1⇔∑j∈N
ajxj − (M + ε)δ ≤ b− ε
′′M ′′ = |M | − k2. ε = 1:∑i∈M
zi − (|M | − k + 1)δ1 ≤ k − 1.
2bad notation clash, sorry!Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 14 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 1
If you open k or more facilities, then you must pay a penalty cost of λ
Need (earlier) “fixed cost” logic for zi : (xi ≤ zi)Model
∑i∈M zi ≥ k ⇒ δ1 = 1
Add λδ1 to objective function
Appropriate trick is∑j∈N
ajxj ≥ b⇒ δ = 1⇔∑j∈N
ajxj − (M + ε)δ ≤ b− ε
′′M ′′ = |M | − k2. ε = 1:∑i∈M
zi − (|M | − k + 1)δ1 ≤ k − 1.
2bad notation clash, sorry!Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 14 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 1
If you open k or more facilities, then you must pay a penalty cost of λ
Need (earlier) “fixed cost” logic for zi : (xi ≤ zi)Model
∑i∈M zi ≥ k ⇒ δ1 = 1
Add λδ1 to objective function
Appropriate trick is∑j∈N
ajxj ≥ b⇒ δ = 1⇔∑j∈N
ajxj − (M + ε)δ ≤ b− ε
′′M ′′ = |M | − k2. ε = 1:∑i∈M
zi − (|M | − k + 1)δ1 ≤ k − 1.
2bad notation clash, sorry!Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 14 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 2
If you open facility one or two, then you may not open both facility 3and 4
Then need to model z1 + z2 ≥ 1⇒ z3 + z4 ≤ 1
z1 + z2 ≥ 1⇒ δ2 = 1δ2 = 1⇒ z3 + z4 ≤ 1
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 15 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 2
If you open facility one or two, then you may not open both facility 3and 4
Then need to model z1 + z2 ≥ 1⇒ z3 + z4 ≤ 1
z1 + z2 ≥ 1⇒ δ2 = 1δ2 = 1⇒ z3 + z4 ≤ 1
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 15 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 2, cont.
First trick is:∑j∈N
ajxj ≥ b⇒ δ = 1⇔∑j∈N
ajxj − (M + ε)δ ≤ b− ε
M = 1, ε = 1:z1 + z2 − 2δ2 ≤ 0.
(Note: could also model (better) as δ2 ≥ z1, δ2 ≥ z2)
Second trick is:
δ = 1⇒∑j∈N
ajxj ≤ b⇔∑j∈N
ajxj +Mδ ≤M + b
M = 1, ε = 1:z3 + z4 + δ2 ≤ 2.
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 16 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 3
I would like to minimize the maximum (transportation) cost that isrequired to serve any customer
Let tj : Transportation cost for customer j ∈ N : tj =∑
i∈M qijx2ij
Objective is: minmaxj∈N tjWe (should now know) that the maximum of linear function isconvex. And minimizing convex functions is “easy.”
So there should be a simple “trick” to model this problem – and thereis.
MINIMAX. (No integer variables needed)
Let C ≥ maxj∈N{tj}.
minC
C ≥ tj :=∑i∈M
qijx2ij ∀j ∈ N
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 17 / 34
General Modeling Constraint Holds Implies Variable = 1
UFL 3
I would like to minimize the maximum (transportation) cost that isrequired to serve any customer
Let tj : Transportation cost for customer j ∈ N : tj =∑
i∈M qijx2ij
Objective is: minmaxj∈N tjWe (should now know) that the maximum of linear function isconvex. And minimizing convex functions is “easy.”
So there should be a simple “trick” to model this problem – and thereis.
MINIMAX. (No integer variables needed)
Let C ≥ maxj∈N{tj}.
minC
C ≥ tj :=∑i∈M
qijx2ij ∀j ∈ N
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 17 / 34
Second Order Cone Programming
Second Order Cone Programming
Cone Programming
max cTx
Ax ≤ bx ∈ C
Where C is a (convex) cone
C is a cone if x ∈ C, λ ≥ 0⇒ λx ∈ C
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 18 / 34
Second Order Cone Programming
Special Cases
maxx∈C{cTx | Ax ≤ b}
C = C`def= {x ∈ Rn | x ≥ 0} ⇒ Linear Programming
C = Cqdef= {(x, z) ∈ Rn × R | z ≥ ‖x‖2 =
√∑nj=1 x
2j ⇒ Second
Order Cone Programming
C = Crdef= {(x, y, z) ∈ Rn × R2
+ |2yz ≥ ‖x‖22 = xTx} ⇒ (Rotated)Secon Order Cone Programming
C = Sn+def= {X ∈ Rn×n | X � 0, Xsymmetric} ⇒ Semidefinite
Programming
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 19 / 34
Second Order Cone Programming
Another notation for SOCP
Qn =
{x ∈ Rn
∣∣∣∣x1 ≥√x22 + . . .+ x2n
}and the rotated seconds order cone
Qnr =
{x ∈ Rn
∣∣ 2x1x2 ≥ x23 + . . .+ x2n, (x1, x2) ≥ 0}
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 20 / 34
Second Order Cone Programming
What epigraphs are representable as SOCP?
Squared Euclidean Norm:
xTx ≤ t⇔ xTx+ (t− 1)2/4 ≤ (t+ 1)2/4⇔∥∥∥∥ xt−12
∥∥∥∥2
≤ t+ 1
2
Fractional quadratic:
xTx
s≤ t, s ≥ 0⇔ xTx ≤ ts, t ≥ 0, s ≥ 0⇔
xTx+(t− s)2
4≤ (t+ s)2
4, t, s,≥ 0⇔
From the last you see why they call Cr a rotated second order cone. Itis the (inverse) image of the mapping
(x, y, z) 7→ (x, (y − z)/2, (y + z)/2)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 21 / 34
Second Order Cone Programming
What epigraphs are representable as SOCP?
Convex Quadratic: g(x) = xTQx+ qTx+ r ≤ tg(x) is convex if Q is positive semidefinite, so Q has a Choleskyfactorization Q = LTL
So it is SOCP. (There are many different SOCP representations).
y = Lx⇒ g(x) = yT y + rTx+ r ≤ t
{(x, t) ∈ Rn+1 | xTQx+ qTx+ r ≤ t} =Proj(x,t){(x, y, t, p) ∈ R2n+2 | y = Lx, p+ qTx+ r ≤ t, p ≥ ‖y‖2}
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 22 / 34
Second Order Cone Programming
Convex Quadratic is SOCP
{(x, y, t, p) ∈ R2n+2 | y = Lx, p+ qTx+ r ≤ t, p ≥ ‖y‖2}
Note again that the last constraint is the same as:∥∥∥∥ yp−12
∥∥∥∥2
≤ p+ 1
2
It is also the same as
2sp ≥ ‖y‖2, 2s = 1
Important Safety Tip
When writing conic constraints in GAMS, you may need tointroduce new variables
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 23 / 34
Second Order Cone Programming
New ProblemRound-Up
Given points {p1, p2, . . . pm} with pi ∈ Rn, find the smallest spherethat encloses all the points
Let x ∈ Rn be the center coordinates
r ∈ R+ be the radius
min r
r ≥
√√√√ n∑j=1
(pij − xj)2 ∀i = 1 . . .m (1)
r2 ≥n∑
j=1
(pij − xj)2 ∀i = 1 . . .m (2)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 24 / 34
Second Order Cone Programming
New ProblemRound-Up
Given points {p1, p2, . . . pm} with pi ∈ Rn, find the smallest spherethat encloses all the points
Let x ∈ Rn be the center coordinates
r ∈ R+ be the radius
min r
r ≥
√√√√ n∑j=1
(pij − xj)2 ∀i = 1 . . .m (1)
r2 ≥n∑
j=1
(pij − xj)2 ∀i = 1 . . .m (2)
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 24 / 34
Second Order Cone Programming
Could also formulate as SOCP
We’ll go to the GAMS code
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 25 / 34
Piecewise Linear Modeling
Modeling Piecewise-Linear Functions
There are many ways to model piecewise linear functions using integervariables. I really recommend [11, 10] as references
Take Your Pick
SOS2 Model [2, 1]
Incremental Model [6]
Multiple Choice Model [5]
Convex Combination Model [3, 8]
Disaggregated Convex Combination Model [7]
Logarithmic Model [11]
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 26 / 34
Piecewise Linear Modeling
Multiple Choice Model
Want to model (∀i)
f(q) = miq+ ci, q ∈ [Bi−1, Bi]
Introduce New Variables
wi: = q if q ∈ [Bi−1, Bi]
bi: = 1 if q ∈ [Bi−1, Bi]
t ≈ f(q)
q
f(q) ≈ sgn(q)|q|c2
B0 B1 B2
B3 B4
q =n∑
i=1
wi,
t =n∑
i=1
(miwi + cibi)
Bi−1bi ≤ wi ≤ Bibi ∀i ∈ 1, . . . , n
1 =n∑
i=1
bi
B0y ≤ q ≤ Bny
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 27 / 34
Piecewise Linear Modeling
Multiple Choice Model
Want to model (∀i)
f(q) = miq+ ci, q ∈ [Bi−1, Bi]
Introduce New Variables
wi: = q if q ∈ [Bi−1, Bi]
bi: = 1 if q ∈ [Bi−1, Bi]
t ≈ f(q)
q
f(q) ≈ sgn(q)|q|c2
B0 B1 B2
B3 B4
q =n∑
i=1
wi,
t =n∑
i=1
(miwi + cibi)
Bi−1bi ≤ wi ≤ Bibi ∀i ∈ 1, . . . , n
1 =n∑
i=1
bi
B0y ≤ q ≤ Bny
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 27 / 34
Piecewise Linear Modeling
Multiple Choice Model
Want to model (∀i)
f(q) = miq+ ci, q ∈ [Bi−1, Bi]
Introduce New Variables
wi: = q if q ∈ [Bi−1, Bi]
bi: = 1 if q ∈ [Bi−1, Bi]
t ≈ f(q)
q
f(q) ≈ sgn(q)|q|c2
B0 B1 B2
B3 B4
q =
n∑i=1
wi,
t =
n∑i=1
(miwi + cibi)
Bi−1bi ≤ wi ≤ Bibi ∀i ∈ 1, . . . , n
1 =
n∑i=1
bi
B0y ≤ q ≤ Bny
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 27 / 34
Piecewise Linear Modeling
Multiple Choice Model
Want to model (∀i)
f(q) = miq+ ci, q ∈ [Bi−1, Bi]
Introduce New Variables
wi: = q if q ∈ [Bi−1, Bi]
bi: = 1 if q ∈ [Bi−1, Bi]
t ≈ f(q)
q
f(q) ≈ sgn(q)|q|c2
B0 B1 B2
B3 B4
q =
n∑i=1
wi,
t =
n∑i=1
(miwi + cibi)
Bi−1bi ≤ wi ≤ Bibi ∀i ∈ 1, . . . , n
1 =
n∑i=1
bi
B0y ≤ q ≤ Bny
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 27 / 34
Piecewise Linear Modeling
A Simple Trick
Instead of modeling the piecewise-linear indicator in the standard way:
B0y ≤ q ≤ Bny, 1 =
n∑i=1
bi
Model it as
y =
n∑i=1
bi
Resulting formulation is provably stronger (locally-ideal)
All piecewise-linear functions turned on/off by an indicator have asimilar modeling trick [9]
It is the exact extension of the “perspective reformulation” (whichyou will learn next time) to this case
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 28 / 34
Piecewise Linear Modeling
A Simple Trick
Instead of modeling the piecewise-linear indicator in the standard way:
B0y ≤ q ≤ Bny, 1 =
n∑i=1
bi
Model it as
y =
n∑i=1
bi
Resulting formulation is provably stronger (locally-ideal)
All piecewise-linear functions turned on/off by an indicator have asimilar modeling trick [9]
It is the exact extension of the “perspective reformulation” (whichyou will learn next time) to this case
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 28 / 34
Piecewise Linear Modeling
A Simple Trick
Instead of modeling the piecewise-linear indicator in the standard way:
B0y ≤ q ≤ Bny, 1 =
n∑i=1
bi
Model it as
y =
n∑i=1
bi
Resulting formulation is provably stronger (locally-ideal)
All piecewise-linear functions turned on/off by an indicator have asimilar modeling trick [9]
It is the exact extension of the “perspective reformulation” (whichyou will learn next time) to this case
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 28 / 34
Piecewise Linear Modeling SOS2
SOS2
A different formulation involves the use of special ordered sets of type2
SOS2
A set of variables of which at most two can be positive. If two arepositive, they must be adjacent in the set.
min
k∑i=1
λif(ai)
s.t.k∑
i=1
λi = 1
λi ≥ 0
{λ1, λ2, . . . , λk} SOS2
The adjacency conditions ofSOS2 are enforced by thesolution algorithm
Commercial solvers allow you tospecify SOS2.
In GAMS, the rightmost indexbelongs to the ordered set
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 29 / 34
Piecewise Linear Modeling SOS2
SOS2
A different formulation involves the use of special ordered sets of type2
SOS2
A set of variables of which at most two can be positive. If two arepositive, they must be adjacent in the set.
min
k∑i=1
λif(ai)
s.t.k∑
i=1
λi = 1
λi ≥ 0
{λ1, λ2, . . . , λk} SOS2
The adjacency conditions ofSOS2 are enforced by thesolution algorithm
Commercial solvers allow you tospecify SOS2.
In GAMS, the rightmost indexbelongs to the ordered set
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 29 / 34
Piecewise Linear Modeling SOS2
Example
I: Set of suppliers
B: Set of Cost Breakpoints
cib: Per Units cost of item from supplier i ∈ I in cost region b ∈ Bvib: Maximum number of item from supplier i ∈ I to purchase inregion b ∈ Bb: Number to purchase
αi: Maximum percentage to purchase from any supplier
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 30 / 34
Piecewise Linear Modeling SOS2
Example:
table COST(SUPPL,BREAK0) ’Unit cost’
COST 1 2 3
1 9.2 9 7
2 9 8.5 8.3
3 11 8.5 7.5
;
table BR(SUPPL,BREAK0) ’Breakpoints (quantities at which unit cost changes)’
BR 0 1 2 3
1 0 100 200 1000
2 0 50 250 2000
3 0 100 300 4000
;
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 31 / 34
Piecewise Linear Modeling SOS2
Model
Variables
xi: Amount to purchase from supplier i ∈ Iλib: Convex combination multipliers for each xi ∈ I
(Computed) Parameters
Hint: Compute total cost γib at all breakpoints
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 32 / 34
Piecewise Linear Modeling SOS2
Model
Variables
xi: Amount to purchase from supplier i ∈ Iλib: Convex combination multipliers for each xi ∈ I
(Computed) Parameters
Hint: Compute total cost γib at all breakpoints
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 32 / 34
Piecewise Linear Modeling SOS2
Model:
min∑i∈I
∑b∈B
γibλib
∑b∈B
vibλib = xi ∀i ∈ I∑b∈B
λib = 1 ∀i ∈ I
xi ≤ αib ∀i ∈ I∑i∈I
xi ≥ b
λibSOS2 ∀i ∈ Ixi ≥ 0 ∀i ∈ I
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 33 / 34
Piecewise Linear Modeling SOS2
Conclusions
Learned a “calculus” for turning logical restrictions into algebraicdecriptions
Learned about which types of sets can be modeled with SOCconstraints.
To make sure that solvers “recognize” the conic structure, be sure towrite it in its quadratic form, using only “simple” variables
Introduction to modeling piecewise linear functions
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 34 / 34
Piecewise Linear Modeling SOS2
E. M. L. Beale and J. J. H. Forrest.Global optimization using special ordered sets.Mathematical Programming, 10:52–69, 1976.
E. W. L. Beale and J. A. Tomlin.Special facilities in a general mathematical programming system for non-convex problemsusing ordered sets of variables.In J. Lawrence, editor, Proceedings of the 5th International Conference on OperationsResearch, pages 447–454, 1970.
George Bernard Dantzig.On the significance of solving linear programming problems with some integer variables.Econometrica, 28:30–44, 1960.
O. Gunluk, J. Lee, and R. Weismantel.MINLP strengthening for separaable convex quadratic transportation-cost ufl.Technical Report RC24213 (W0703-042), IBM Research Division, March 2007.
R. G. Jeroslow and J. K. Lowe.Modeling with integer variables.Mathematical Programming Studies, 22:167–184, 1984.
Harry M. Markowitz and Alan S. Manne.On the solution of discrete programming problems.Econometrica, 25(1):84–110, 1957.
R. R. Meyer.Integer and mixed-integer programming models: General properties.
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 34 / 34
Piecewise Linear Modeling SOS2
Journal of Optimization Theory and Applications, 16:191–206, 1976.
M. Padberg.Approximating separable nonlinear functions via mixed zero-one programs.Operations Research Letters, 27(1):1–5, 2000.
S. Sridhar, J. Linderoth, and J. Luedtke.Locally ideal formulations for piecewise linear functions with indicator variables.Operations Research Letters, 41:627–632, 2013.
J. P. Vielma.Mixed integer linear programming formulation techniques.SIAM Review, 57:3–57, 2015.
J. P. Vielma, S. Ahmed, and G. Nemhauser.Mixed-integer models for nonseparable piecewise linear optimization: Unifying frameworkand extensions.Operations Research, 58:303–315, 2010.
Linderoth/Schweiger (UW-Madison/FAU) MSRI MINLP:Lecture 4 Lecture Notes 34 / 34
Recommended