Integer Programming
Formulations
Lecture 2
Integer Programming Formulations Integer Programming
Logical constraints
MATH3220 Operations Research and Logistics Nonlinear Functions
Jan. 8, 2015
Pan Li
The Chinese University of Hong Kong
2.1
Integer Programming
Agenda Formulations
Integer Programming
Logical constraints
1 Integer Programming Nonlinear Functions
2 Logical constraints
3 Nonlinear Functions
2.2
Integer Programming
Integer Programming Formulations
Integer Programming
Logical constraints
Integer Programming: a linear program plus the additional Nonlinear Functions
constraints that some or all of the variables must be integer
valued.
We also permit "xj ∈ {0, 1}", or equivalently, "xj is binary".
This is a shortcut for writing the constraints:
0 ≤ xj ≤ 1 and xj is integer.
2.3
Integer Programming
Simple logical constraints Formulations
Here, we address different logical constraints that can be
transformed into integer programming constraints.
selection of items from a subset Integer Programming
Logical constraint IP constraint Logical constraints
Nonlinear Functions
If item i is selected, then item j is also selected. xi − xj ≤ 0
Either item i is selected or item j is selected, xi + xj = 1
but not both.
Item i is selected or item j is selected or both. xi + xj ≥ 1
If item i is selected, then item j is not selected. xi + xj ≤ 1
If item i is not selected, then item j is −xi + xj ≤ 0
not selected.
At most one of item i, j and k are selected. xi + xj + xk ≤1
At most two of items i, j and k are selected. xi + xj + xk ≤2
Exactly one of items i, j, and k are selected. xi + xj + xk =1
At least one of items i, j and k are selected. xi + xj + xk ≥1
2.4
Integer Programming
Simple logical constraints - con’t Formulations
Restricting a variable to take on one of several values.
Suppose that we want to restrict x to be one of the elements
{4, 8, 13}. This is accomplished as follows. Integer Programming
Logical constraints
x = 4w1 + 8w2 + 13w3 Nonlinear Functions
w1 + w2 + w3 = 1
wi ∈ {0, 1}for i = 1 to 3.
Question: If we want to restrict x to be one of the elements {0,
4, 8, 13}, how should we model it?
2.5
Integer Programming
Simple logical constraints - con’t Formulations
Restricting a variable to take on one of several values.
Suppose that we want to restrict x to be one of the elements
{4, 8, 13}. This is accomplished as follows. Integer Programming
Logical constraints
x = 4w1 + 8w2 + 13w3 Nonlinear Functions
w1 + w2 + w3 = 1
wi ∈ {0, 1}for i = 1 to 3.
Question: If we want to restrict x to be one of the elements {0,
4, 8, 13}, how should we model it?
Answer: It suffices to use the above formulation with the
equality constraint changed to "w1 + w2 + w3 ≤ 1".
2.6
Integer Programming
Simple logical constraints - con’t Formulations
Restricting a variable to take on discontinuous values.
Suppose that we want to restrict x must be either 0 or between
particular positive bounds. In algebraic notation: Integer Programming
Logical constraints
x =0 or l ≤x ≤u Nonlinear Functions
Define:
0 for x = 0
y=
1 for l ≤ x ≤ u
Then, the logical constraints can be modeled by:
ly ≤ x ≤ uy
y ∈ {0, 1}
2.7
Integer Programming
Other logical constraints, and the big M method. Formulations
Big-M method for IP formulations
Assume that all variables are integer valued.
Assume a bound u ∗ on coefficients and variables;
Integer Programming
Logical constraints
Nonlinear Functions
e.g. xj ≤ 1, 000 for all j.
|aij | ≤ 1, 000 for all i, j
Choose M really large so that for every constraint i,
|ai1 x1 + ai2 x2 + . . . + ain xn − bi | ≤ M
That is, we will be able to satisfy any "≤" constraint by
adding M to the RHS.
And we can satisfy any "≥" constraint by
subtracting M from the RHS.
2.8
Integer Programming
Logical constraint - Constraint feasibility Formulations
Binary variables that are 1 when a constraint is satisfied.
1 if f (x1 , x2 , . . . , xn ) ≤ b Integer Programming
w= Logical constraints
0 otherwise
Nonlinear Functions
Here we assume that f (x) is bounded.
Equivalent constraints:
f (x1 , x2 , . . . , xn ) ≤ b + M(1 − w).
f (x1 , x2 , . . . , xn ) ≥ b − Mw.
w ∈ {0, 1}
where the constant M is chosen to be large enough so that the
constraint is always satisfied if w = 0. Whenever w = 1 gives a
feasible solution to IP constraint, the logical constraint must be
satisfied.
2.9
Integer Programming
Logical constraint - Alternative constraint Formulations
We formulate the logical constraint, "x ≤ 2 or x ≥ 6" as follows.
Choose a binary variable w so that
Integer Programming
if w = 1, then x ≤ 2 Logical constraints
if w = 0, then x ≥ 6 Nonlinear Functions
x ≤2 + M(1 − w)
x ≥6 − Mw
w ∈ {0, 1}
To validate the formulation one needs to show:
The logical constraints are equivalent to the IP constraints.
2.10
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations
Logical constraint IP constraints
x ≤ 2 + M(1 − w)
x ≤ 2 or x ≥ 6 x ≥ 6 − Mw Integer Programming
Logical constraints
w ∈ {0, 1} Nonlinear Functions
Suppose (x, w) is feasible for the IP,
if w = 1, thenx ≤ 2.
if w = 0, thenx ≥ 6.
In both cases, the logical constraints are satisfied.
Suppose that x satisfies the logical constraints.
If x ≤ 2, then let w = 1 ⇒ x ≤2 and x ≥6−M
If x ≥ 6, then let w = 0 ⇒ x ≤2+M and x ≥6
In both cases, the IP constraints are satisfied.
2.11
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations
Logical constraint IP constraints
2x1 + 3x2 ≥ 14 or 2x1 + 3x2 ≥ 14 − M(1 − w)
5x2 − 7x3 ≤ 3 5x2 − 7x3 ≤ 3 + Mw Integer Programming
Logical constraints
w ∈ {0, 1} Nonlinear Functions
Suppose xi is Suppose that M is very large.
bounded for all i.
To show:
The logical constraints are equivalent to the IP constraints.
Suppose (x, w) is feasible for the IP,
if w = 1, then 2x1 + 3x2 ≥ 14.
if w = 0, then 5x2 − 7x3 ≤ 3.
Therefore, the logical constraints are satisfied.
2.12
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations
Logical constraint IP constraints
2x1 + 3x2 ≥ 14 or 2x1 + 3x2 ≥ 14 − M(1 − w)
5x2 − 7x3 ≤ 3 5x2 − 7x3 ≤ 3 + Mw Integer Programming
Logical constraints
w ∈ {0, 1} Nonlinear Functions
To show:
The logical constraints are equivalent to the IP constraints.
Suppose that x satisfies the logical constraints.
If 2x1 + 3x2 ≥ 14, then let w = 1 ⇒ 2x1 + 3x2 ≥ 14 and
5x2 − 7x3 ≤ 3 + M
If 5x2 − 7x3 ≤ 3, then let w = 0 ⇒ 2x1 + 3x2 ≥ 14 − M and
5x2 − 7x3 ≤ 3
In both cases, the IP constraints are satisfied.
2.13
Integer Programming
Logical constraint - Conditional constraints Formulations
These constraints have the form:
if f1 (x1 , x2 , . . . , xn ) > b1 , then f2 (x1 , x2 , . . . , xn ) ≤ b2 .
Integer Programming
Logical constraints
Since this implication is not satisfied only when both
Nonlinear Functions
f1 (x1 , x2 , . . . , xn ) > b1 and f2 (x1 , x2 , . . . , xn ) > b2 , the conditional
constraint is logically equivalent to the alternate constraints
f1 (x1 , x2 , . . . , xn ) ≤ b1 and/or f2 (x1 , x2 , . . . , xn ) ≤ b2
where at least one must be satisfied. Hence, this situation can
be modeled by alternative constraints:
f1 (x1 , x2 , . . . , xn ) ≤ b1 + B1 y ,
f2 (x1 , x2 , . . . , xn ) ≤ b2 + B2 (1 − y ),
y ∈ {0, 1}
2.14
Integer Programming
At least one of three inequalities is satisfied. Formulations
x1 + 4x2 + 2x4 ≥ 7 or 3x1 − 5x2 ≤ 12 or 2x2 + x3 ≥ 6
Create three binary variables w1 , w2 , and w3 and reformulate
the above constraint as the following system of logical, linear Integer Programming
and integer constraints. Logical constraints
Nonlinear Functions
If w1 = 1, then x1 + 4x2 + 2x4 ≥ 7
If w2 = 1, then 3x1 − 5x2 ≤ 12
If w3 = 1, then 2x2 + x3 ≥ 6
w1 + w2 + w3 ≥ 1
wi ∈ {0, 1} for i = 1 to 3.
This above system of constraints is equivalent to the following.
x1 + 4x2 + 2x4 ≥ 7 − M(1 − w1 )
3x1 − 5x2 ≤ 12 + M(1 − w2 )
2x2 + x3 ≥ 6 − M(1 − w3 )
w1 + w2 + w3 ≥ 1
wi ∈ {0, 1} for i = 1 to 3 .
2.15
Integer Programming
Logical constraint - k-Fold alternative Formulations
Suppose we must satisfy at least k of the constraints:
fi (x) ≤ bi (j = 1, 2, . . . , m)
Integer Programming
Assuming that Bi are chosen so that the ignored constraints Logical constraints
will not be binding, the general problem can be formulated as Nonlinear Functions
follows:
fi (x) ≤ bi + Bi (1 − yi )
Pm
i=1 yi ≥ k ,
yi ∈ {0, 1} (i = 1, 2, . . . , m)
2.16
Integer Programming
Nonlinear Functions Formulations
Nonlinear functions can be represented by integer
programming formulations.
Integer Programming
Logical constraints
Nonlinear Functions
2.17
Integer Programming
Fixed costs Formulations
In a typical production planning problem involving N products,
the production cost for product j may consist of a fixed cost dj
independent of the amount produced and a variable cost cj per
unit. Thus if xj is the production level of product j, its production Integer Programming
cost function may be written as Logical constraints
Nonlinear Functions
dj + cj xj xj > 0
fj (xj ) =
0 xj = 0
This is nonlinear in xj because of the discontinuity of fj (xj ) at
the origin. Consequently, the following minimum cost problem
is also nonlinear:
PN
Min z = j=1 fj (xj )
s.t. Ax = b, x ≥ 0.
2.18
Integer Programming
Fixed costs (con’t) Formulations
If it is known that 0 ≤ xj ≤ uj and dj > 0 then we can define a
binary variable yj that indicates when the fixed cost is incurred,
so that
Integer Programming
yj = 1, if xj > 0 Logical constraints
Nonlinear Functions
yj = 0, if xj = 0
Then the contribution to cost due to xj may be written as
fj (xj ) = dj yj + cj xj
with the constraints:
xj ≤ uj yj ,
xj ≥ 0,
y = 0 or 1.
2.19
Integer Programming
Fixed costs (con’t) Formulations
In a typical production planning problem involving N products,
the production cost for product j may consist of a fixed cost dj
independent of the amount produced and a variable cost cj per
unit. Thus if xj is the production level of product j, its production Integer Programming
cost function may be written as Logical constraints
Nonlinear Functions
dj + cj xj xj > 0
fj (xj ) =
0 xj = 0
This is nonlinear in xj because of the discontinuity of fj (xj ) at
the origin. Consequently, the following minimum cost problem
is also nonlinear:
PN
Min z = j=1 (cj xj + dj yj )
s.t. Ax = b
0 ≤ xj ≤ uj yj , j = 1, 2, . . . , N
yj ∈ {0, 1}, j = 1, 2, . . . , N
2.20
Integer Programming
Piecewise linear representation Formulations
Integer Programming
Logical constraints
Nonlinear Functions
Define integral variables δ1 , δ2 and δ3 so that:
δ1 corresponds to the amount by which x exceeds 0, but is
less than or equal to 4;
δ2 is the amount by which x exceeds 4, but is less than or
equal to 10; and
δ3 is the amount by which x exceeds 10, but is less than or
equal to 15. 2.21
Integer Programming
Piecewise linear representation Formulations
Integer Programming
Logical constraints
Nonlinear Functions
Hence,
x = δ1 + δ2 + δ3 ,
where
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5, (1)
and the total variable cost is given by:
Cost = 5δ1 + δ2 + 3δ3 .
2.22
Integer Programming
Piecewise linear representation Formulations
However, we should have the
following conditional Integer Programming
constraints: Logical constraints
δ1 = 4, if δ2 > 0 Nonlinear Functions
δ2 = 6, if δ3 > 0
Hence,
x = δ1 + δ2 + δ3 ,
where
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5, (2)
and the total variable cost is given by:
Cost = 5δ1 + δ2 + 3δ3 .
2.23
Integer Programming
Piecewise linear representation (I) Formulations
Logical constraints:
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
Integer Programming
δ1 = 4, if δ2 > 0
Logical constraints
δ2 = 6, if δ3 > 0 Nonlinear Functions
Define
1 if δ1 is at its upper bound
w1 =
0 otherwise
1 if δ2 is at its upper bound
w2 =
0 otherwise
2.24
Integer Programming
Piecewise linear representation (I) (con’t) Formulations
Logical constraints:
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
Integer Programming
δ1 = 4, if δ2 > 0
Logical constraints
δ2 = 6, if δ3 > 0 Nonlinear Functions
Then the constraints above can be replaced by:
4w1 ≤ δ1 ≤ 4,
6w2 ≤ δ2 ≤ 6w1 ,
0 ≤ δ3 ≤ 5w2
w1 and w2 binary.
2.25
Integer Programming
Piecewise linear representation (I) (con’t) Formulations
Logical constraints:
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
δ1 = 4, if δ2 > 0 Integer Programming
Logical constraints
δ2 = 6, if δ3 > 0 Nonlinear Functions
Then the constraints above can be replaced by:
4w1 ≤ δ1 ≤ 4,
6w2 ≤ δ2 ≤ 6w1 ,
0 ≤ δ3 ≤ 5w2
w1 and w2 binary.
There are three feasible combinations for the values of w1 and
w2 :
w1 = 0, w2 = 0 corresponding to 0 ≤ x ≤ 4
w1 = 1, w2 = 0 corresponding to 4 ≤ x ≤ 10
w1 = 1, w2 = 1 corresponding to 10 ≤ x ≤ 15 2.26
Integer Programming
Piecewise linear representation (I) (con’t) Formulations
The same general technique can be applied to piecewise linear
curves with any number of segments.
The general constraint imposed upon the variable δj for the jth Integer Programming
segment will be: Logical constraints
Nonlinear Functions
Lj wj ≤ δj ≤ Lj wj−1
where Lj is the length of the segment.
2.27
Integer Programming
Approximation of Nonlinear Functions Formulations
One of the most useful applications of the piecewise linear
representation is for approximating nonlinear function.
Suppose the expansion cost in our previous example is given Integer Programming
by the heavy curve in the figure below. Logical constraints
Nonlinear Functions
2.28
Integer Programming
Approximation of Nonlinear Functions (con’t) Formulations
Integer Programming
Logical constraints
Nonlinear Functions
If we draw linear segments joining selected points on the
curve, we obtain a piecewise linear approximation, which can
be used of the curve in the model. The piecewise
approximation is represented by introducing integer variables
as indicated before.
By using more points on the curve, we can make the
approximation as close as we desire. 2.29
Integer Programming
Piecewise linear representation (II) Formulations
y= 2x if 0 ≤ x ≤ 3
y= 9−x if 4 ≤ x ≤ 7
Integer Programming
y= −5 + x if 8 ≤ x ≤ 9 Logical constraints
Nonlinear Functions
x is integer valued.
If the variables are defined as above, then
y = 2x1 + (9w2 − x2 ) + (−5w3 + x3 ) 2.30
Integer Programming
Piecewise linear representation (II) (con’t) Formulations
Add constraints
Constraints
Definitions of the variables.
0 ≤ x1 ≤ 3w1 Integer Programming
Logical constraints
w1 ∈ {0, 1} Nonlinear Functions
4w2 ≤ x2 ≤ 7w2
w2 ∈ {0, 1}
8w3 ≤ x3 ≤ 9w3
w3 ∈ {0, 1}
w1 + w2 + w3 = 1
x = x1 + x2 + x3
xi integer∀i
Suppose that 0 ≤ x ≤ 9, x integer.
If (x, w) satisfies the definitions, then it also satisfies the
constraints.
If (x, w) satisfies the constraints, then it also satisfies the
definitions. 2.31
Integer Programming
Exercise Formulations
Construct integer programming formulations to represent the
following piecewise linear function.
Integer Programming
0 if x = 0
Logical constraints
f (x) = 1 if 1 ≤ x ≤ 2 Nonlinear Functions
2 if 3 ≤ x ≤ 4.
2.32
Integer Programming
Summary Formulations
IPs can model almost any combinatorial optimization
problem.
lots of transformation techniques.
Integer Programming
Next lecture: how to solve integer programs. Logical constraints
Nonlinear Functions
2.33
