2.3 Mixed-Integer Linear Optimization Approach
11
We now linearize (2.8) as follows:
x i − x j + Mα ij ≥
1
2 (( i + j )
(2.11)
x j − x i + M(1 − α ij ) ≥
1
2 (( i + j ),
(2.12)
where M is a sufficiently large number (see the next subsection for a discussion of
how to choose M). These constraints work as follows:
• If α ij = 0, then |x i − x j | = x i − x j . In this case, constraint (2.11) becomes
x i − x j ≥
1
2
(( i + j ), and hence |x i − x j | ≥
1
2
(( i + j ), as desired.
At the same time, constraint (2.12) has a large value M added to the left-hand
side, which means that it will hold regardless of the values of x i and x j .
• Similarly, if α ij = 1, then |x i − x j | = x j − x i , and constraint (2.12) becomes
x j − x i ≥
1
2
(( i + j ), and hence |x i − x j | ≥
1
2
(( i + j ), as desired.
Simultaneously, constraint (2.11) has M added to the left-hand side and in effect
imposes no restriction on x i and x j .
2.3.3 Choosing M
The so-called big-M method is a modelling technique that uses binary variables to
turn otherwise linear constraints on or off. In the previous section, we want to turn
one of the nonoverlap constraints on, and the other one off, so that the term |x i − x j |
is always linearized correctly.
Although the idea is simple, choosing a value for M can be tricky. This is because
setting M too small can cause the optimal solution to become infeasible, i.e., it no
longer satisfies the constraints. On the other hand, setting M too large can impact the
performance of the optimization solver. First, numerical instability can arise when
one coefficient (M) is much larger than the others. Second, optimization problems
with integer variables are typically solved by combining a branching algorithm
(such as branch-and-bound or branch-and-cut) with relaxations where the integer
variables are allowed to be continuous. The large value of M almost always makes
these relaxations weaker, and weak relaxations can dramatically slow down the
solution process.
In general, M should be as small as possible, and whenever possible, knowledge
of the application should be used in determining an appropriate value. For constraints (2.11) and (2.12), we can determine the smallest possible (negative) value
of the difference between x i and x j and choose M accordingly.
11
We now linearize (2.8) as follows:
x i − x j + Mα ij ≥
1
2 (( i + j )
(2.11)
x j − x i + M(1 − α ij ) ≥
1
2 (( i + j ),
(2.12)
where M is a sufficiently large number (see the next subsection for a discussion of
how to choose M). These constraints work as follows:
• If α ij = 0, then |x i − x j | = x i − x j . In this case, constraint (2.11) becomes
x i − x j ≥
1
2
(( i + j ), and hence |x i − x j | ≥
1
2
(( i + j ), as desired.
At the same time, constraint (2.12) has a large value M added to the left-hand
side, which means that it will hold regardless of the values of x i and x j .
• Similarly, if α ij = 1, then |x i − x j | = x j − x i , and constraint (2.12) becomes
x j − x i ≥
1
2
(( i + j ), and hence |x i − x j | ≥
1
2
(( i + j ), as desired.
Simultaneously, constraint (2.11) has M added to the left-hand side and in effect
imposes no restriction on x i and x j .
2.3.3 Choosing M
The so-called big-M method is a modelling technique that uses binary variables to
turn otherwise linear constraints on or off. In the previous section, we want to turn
one of the nonoverlap constraints on, and the other one off, so that the term |x i − x j |
is always linearized correctly.
Although the idea is simple, choosing a value for M can be tricky. This is because
setting M too small can cause the optimal solution to become infeasible, i.e., it no
longer satisfies the constraints. On the other hand, setting M too large can impact the
performance of the optimization solver. First, numerical instability can arise when
one coefficient (M) is much larger than the others. Second, optimization problems
with integer variables are typically solved by combining a branching algorithm
(such as branch-and-bound or branch-and-cut) with relaxations where the integer
variables are allowed to be continuous. The large value of M almost always makes
these relaxations weaker, and weak relaxations can dramatically slow down the
solution process.
In general, M should be as small as possible, and whenever possible, knowledge
of the application should be used in determining an appropriate value. For constraints (2.11) and (2.12), we can determine the smallest possible (negative) value
of the difference between x i and x j and choose M accordingly.