2-504-09 Lecture Notes - Lecture 4: Spreadsheet, Piecewise Linear Function, Cengage Learning
1"
"
Integer programming (2/2)
4.3 Activate/deactivate a constraint
Sometimes, a constraint can be eliminated under certain conditions. For
example, a working day may not exceed eight hours unless you pay a
premium. Or, in a set of constraints, some could be eliminated depending on
what is most interesting from the point of view of the objective.
To illustrate this, consider the following situation. In the furniture industry, it
happens that one must cut out rectangular pieces of wood in large rectangular
boards. The objective is to minimize the loss due to falling timber. One
obvious constraint is that two different pieces cannot be cut from the same
place on a board. Suppose then that we have a plank of 48 inches wide and 96
inches long. One must cut out pieces with a width of 18 inches and a length
of 36 inches, and pieces with a width of 15 inches and a length of 50 inches.
Let x1 and y1 by the position of the lower left corner of the first piece on the
board (0 ≤ x1 ≤60 and 0≤ y1 ≤ 30), and x2 and y2 the position of the second
piece (0 ≤ x2 ≤ 46 and 0≤ y2 ≤ 33). We must ensure that the two pieces do not
overlap on our board. One possibility would be to require that the second piece
is positioned to the right of the first. This option can be imposed by adding
the constraint x2 ≥ x1 + 36. Another possibility would be to put it on the left
and then add the constraint x2 + 50 ≤ x1. You can also place it on top by adding
the constraint y2 ≥ y1 + 18 or below with constraint y2 + 15 ≤ y1. Of course we
cannot meet these four requirements simultaneously. We will have to respect
at least one of those four constraints to eliminate any overlap possibility.
It is possible to indicate whether a constraint can be disabled by introducing a
binary variable. Consider a linear constraint:
!"# $"% !&# $&% ' % !(# $() *
To do this, we will need a very large number, denoted by M. This number will
be larger than any possible value of !"# $"% !&# $&% ' % !(# $( in the
context in which it is applied. Let z be our binary variable that takes the value
1 if the constraint cannot be met and 0 if it is respected. We impose the
constraint by adding M·z on the right-hand side for a constraint of type ≤ and
on the left-hand side for a constraint of type ≥. We may, thereafter, impose
consequences in our model when z = 0 or 1.
find more resources at oneclass.com
find more resources at oneclass.com
2"
"
In our wood-cutting example, we have four constraints and at least one must
be respected. We add four binary variables to the model that we will place in
the constraints as follows:
+,-"% $&. $"%/,
$&%01 ) $"%+,-&
23-4% 5&. 5"%63
5&%60 ) 5"%23-7
Whenever a binary variable is set to 1, the constraint associated with that
binary variable will be respected regardless of the position of the pieces on
the big board. For example, if z1 is set to 1, the first constraint says that x1 ≤
60, which was already planned. So that the two pieces do not overlap, it is
necessary that at least one of the four binary variables take the value 0. We
can impose this with: -"% -&% -4% -7) /.
In summary, if we have m constraints of type:
!""$"% !"&$&% ' % !"($() *"
!&"$"% !&&$&% ' % !&($() *&
8 8
!9"$"% !9&$&% ' % !9($() *9
And we want to respect at least k of these constraints, then we will introduce
m binary variables:
-:;6<=>?@ABCDEFAC>G>FB>A@C>DHBIH?CHJ
1KCLHDMFBH
And we introduce the following constraints:
!""$"% !"&$&% ' % !"($() *"% N-"
!&"$"% !&&$&% ' % !&($() *&% N-&
8>>>>>>>>>>>>>>>>>>>>>>> >>>>>>8
!9"$"% !9&$&% ' % !9($() *9% N-9
-"% -&% ' % -9) O P Q
Logical conditions with integer variables
In the previous section, we have examined conditions on the value of binary
variables. Sometimes, we have logical conditions involving integer variables.
In that case, we need to add binary variables to indicate if the conditions are
met and incorporate these binary variables in linear constraints as done earlier.
find more resources at oneclass.com
find more resources at oneclass.com
3"
"
Consider the following example. Here, the variables x1, x2, x3, and x4 are
integer variables.
If 2x1+ 3x2 is greater than 10, then x3 -x4 must be less than or equal to 5.
Here we consider two constraints 2x1+ 3x2 ≤ 10 and x3 - x4 ≤ 5. If the first
constraint is not respected, the second must be.
We add a dummy variable for each constraint:
-:;6<=>?@ABCDEFAC>G>FB>A@C>DHBIH?CHJ
1KCLHDMFBH
Then, we allow each of these two constraints to be respected or not:
R$"% /$&)61 % N # -"
$4P $7) 0 % N # -&
The logical condition can now be written with the help of two binary
variables: if z1=1 then z2=0. Thus, we must add the linear constraint z1+z2 ≤ 1.
4.4 Disconnected intervals
When a variable can take all integer values within a range, we can simply add
the integrality constraint for that variable to the constraints that specify the
limits of the interval. But what if only a few values of the range are possible
but not others. For example, how could we impose using linear constraint(s)
that a variable x can only take the values 0, 2, 5, 9, or 14?
The answer is simple, just add a binary variable for each of the values 2, 5, 9,
and 14:
5";6<=>$ ; R
1KCLHDMFBH
5&;6<=>$ ; 0
1KCLHDMFBH
54;6<=>$ ; +
1KCLHDMFBH
57;6<=>$ ; 62
1KCLHDMFBH
Then, we have a constraint binding the value of x to the binary variables:
$ ; R5"% 05&% +54%6257
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Sometimes, a constraint can be eliminated under certain conditions. For example, a working day may not exceed eight hours unless you pay a premium. Or, in a set of constraints, some could be eliminated depending on what is most interesting from the point of view of the objective. In the furniture industry, it happens that one must cut out rectangular pieces of wood in large rectangular boards. The objective is to minimize the loss due to falling timber. One obvious constraint is that two different pieces cannot be cut from the same place on a board. Suppose then that we have a plank of 48 inches wide and 96 inches long. One must cut out pieces with a width of 18 inches and a length of 36 inches, and pieces with a width of 15 inches and a length of 50 inches. We must ensure that the two pieces do not overlap on our board.
