Binary Linear Optimization in Capital Allocation Problems
Instructor: Dr. Le Nhat Tan
1 An Introductory Example
Example 1. A firm is considering funding several proposed independent projects that have financial properties shown in the following table, in terms of dollars.
| Project | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Cost | 300 | 400 | 150 | 100 |
| NPV | 10 | 20 | 10 | 10 |
Assume a maximum capital budget of $600, which projects should we choose to maximize the profit (i.e. the total NPV of selected projects)?
If we represent our decision by a sequence \(\left\{x_i\right\}_{i=1}^4,\) where \[x_i=\left\{\begin{matrix}1 & \textrm{if we choose project }i\\0 & \textrm{otherwise}\end{matrix}\right.,\forall i=\overline{1,4}\] then the given problem can be written in the form
\[\begin{matrix} \textrm{maximize} & 10x_1+20x_2+10x_3+10x_4\\ \textrm{subject to} & 300x_1+400x_2+150x_3+100x_4\leq600\\ & x_i\in\left\{0,1\right\},\forall i=\overline{1,4} \end{matrix}\]
which is an example of what so called a binary linear program (BLP).
2 Brute-Forcing Approach
A simple idea is to consider every cases of the problem.
def binary_strings(n):
if n == 1:
return [[0], [1]] # binary strings of length 1
# append 0 and 1 to binary strings of length n - 1
arr, result = binary_strings(n - 1), []
for i in arr:
for j in [0, 1]:
result.append(i + [j])
return result# Example: binary strings of length 3
for i in binary_strings(3):
print(i, end = ' ... ')## [0, 0, 0] ... [0, 0, 1] ... [0, 1, 0] ... [0, 1, 1] ... [1, 0, 0] ... [1, 0, 1] ... [1, 1, 0] ... [1, 1, 1] ...def product(list1, list2):
return [a * b for a, b in zip(list1, list2)]
product([1, 2, 3], [4, 5, 6])## [4, 10, 18]def capital_brute_force_algorithm(cost, NPV, budget):
if len(cost) != len(NPV) or budget < 0: # input error
return -1, None
# iterates over all possible portfolios
solution, profit = [], []
for i in binary_strings(len(cost)):
if sum(product(i, cost)) <= budget:
solution.append(i)
profit.extend([sum(product(i, NPV))])
# return an optimal solution
optimal = max(profit)
position = profit.index(optimal)
decision = solution[position]
return decision, optimaldef capital_brute_force_result(cost, NPV, budget):
decision, optimal = capital_brute_force_algorithm(cost, NPV, budget)
if decision == -1:
print('Error. Recheck Your Input.')
return 0
print('Optimal Portfolio:', decision)
print('Optimal Profit:', optimal)cost = [300, 400, 200, 150]
NPV = [10, 20, 10, 10]
capital_brute_force_result(cost, NPV, budget = 600)## Optimal Portfolio: [0, 1, 0, 1]
## Optimal Profit: 30The underlying idea is simple, but the efficiency is questionable:
\(N\) projects \(\approx\) \(2^N\) iterations.
Real-time measurements are provided below.
start = time.time() # current time
x = binary_strings(20) # do something
end = time.time() # current time
print('Elapsed Time in Seconds:', end - start)## Elapsed Time in Seconds: 2.761669397354126def capital_brute_force_time(n):
sample_cost = list(np.around(np.random.normal(200, 100, n)))
sample_NPV = list(np.around(np.random.normal(75, 50, n)))
size, elapsed_time = list(range(1, n + 1)), []
for i in size:
cost, NPV, budget = sample_cost[:i], sample_NPV[:i], 400 + 100 * (i - 1)
start = time.time()
decision, optimal = capital_brute_force_algorithm(cost, NPV, budget)
end = time.time()
elapsed_time.extend([end - start])
return elapsed_timesample = capital_brute_force_time(15)plot(1:15, py$sample, col = 'blue', type = 'l',
xlab = 'Project Count', ylab = 'Elapsed Time (s)',
main = 'Brute-Forcing Approach, Sample Elapsed Time')
samples = []
for i in range(1, 21):
samples.append(capital_brute_force_time(15))
df = pd.DataFrame(samples)
df.columns = [str(i) for i in range(1, 16)]df = py$df
df = melt(df)
df$Sample = 1:20
ggplot(df, aes(variable, value, color = Sample)) +
geom_line(aes(group = Sample)) +
labs(x = 'Project Count', y = 'Elapsed Time (s)',
title = 'Brute-Forcing Approach, Elapsed Time Distribution')
The execution time rockets exponentially as the project count increases. Hence, it is natural to rely on a faster, more elegent algorithm.
3 Linear Optimization
3.1 Classifications
A general linear program (LP) is an optimization problem of the form
\[\begin{matrix} \textrm{minimize} & c^Tx\\ \textrm{subject to} & Ax=b\\ & Cx\leq d\\ & x\geq0 \end{matrix}\]
where \(b,c,d,x\) are vectors and \(A,C\) are matrices of reals with appropriate sizes. If we add the intergal constraints
\[\begin{matrix} \textrm{minimize} & c^Tx\\ \textrm{subject to} & Ax=b\\ & Cx\leq d\\ & x_i\in\mathbb{Z},x\geq0 \end{matrix}\]
then we arrive at an integer linear program (ILP), and further restrictions
\[\begin{matrix} \textrm{minimize} & c^Tx\\ \textrm{subject to} & Ax=b\\ & Cx\leq d\\ & x_i\in\left\{0,1\right\} \end{matrix}\]
create a BLP. Note that an ILP can be made into a BLP by adding one constraint:
\[\begin{matrix} \textrm{minimize} & c^Tx\\ \textrm{subject to} & Ax=b\\ & Cx\leq d\\ & x\leq1\\ & x_i\in\mathbb{Z},x\geq0 \end{matrix}\]
3.2 The Simplex Algorithm
A famous, elegent approach for solving a LP is the simplex algorithm by Dantzig [1947]. Students should be familiar with the following terms:
- Convex sets, extreme points (vertexes), hyperplanes;
- Slack & surplus variables;
- Feasible solutions & feasible regions;
- Basic & optimal solutions;
- Simplex tableau, pivoting;
- Entering & leaving variables;
- The Ratio Test.
In words, the simplex algorithm starts at a vertex of the feasible region, then walks around its edges until reaching the optimal solution (vertex).
Example 2. Consider the LP
\[\begin{matrix} \textrm{minimize} & -3x-2y\\ \textrm{subject to} & 2x+3y\leq12\\ & 2x+y\leq8\\ & x,y\geq0 \end{matrix}\]
The feasible region plot is given below.
We convert the given LP into standard form
\[\begin{matrix} \textrm{minimize} & z(x,y)=-3x-2y\\ \textrm{subject to} & 2x+3y+u=12\\ & 2x+y+v=8\\ & x,y,u,v\geq0 \end{matrix}\]
and set up the initial tableau
| x | y | u | v | rhs |
|---|---|---|---|---|
| 2 | 3 | 1 | 0 | 12 |
| 2 | 1 | 0 | 1 | 8 |
| -3 | -2 | 0 | 0 | 0 |
which says that the simplex algorithm starts at the point \((0,0)\) where the objective function attains the value \(0.\)
We pivot on r2c1 and get the new tableau
| x | y | u | v | rhs |
|---|---|---|---|---|
| 0 | 2 | 1 | -1 | 4 |
| 1 | 1/2 | 0 | 1/2 | 4 |
| 0 | -1/2 | 0 | 3/2 | 12 |
which says that the simplex algorithm walks from \((0,0)\) to the new point \((4,0)\) where the objective function attains the value \(-12.\)
We pivot on r1c2 and get the new tableau
| x | y | u | v | rhs |
|---|---|---|---|---|
| 0 | 1 | 1/2 | -1/2 | 2 |
| 1 | 0 | -1/4 | 3/4 | 3 |
| 0 | 0 | 1/4 | 5/4 | 13 |
which says that the simplex algorithm walks from \((4,0)\) to the new point \((3,2)\) where the objective function attains the value \(-13.\)
All coefficients in the last row (i.e. objective row) of the tableau are non-negative, so the simplex algorithm stops with the optimal solution \((x,y)=(3,2)\) and optimal value \(-13.\)
3.3 The Two-Phase Algorithm
Example 3. Consider the LP
\[\begin{matrix} \textrm{minimize} & x_1-2x_2\\ \textrm{subject to} & -x_1-x_2\leq-2\\ & x_1-x_2\leq-1\\ & x_2\leq3\\ & x_1,x_2\geq0 \end{matrix}\]
We convert the given LP into standard form
\[\begin{matrix} \textrm{minimize} & z(x_1,x_2)=x_1-2x_2\\ \textrm{subject to} & x_1+x_2-x_3=2\\ & -x_1+x_2-x_4=1\\ & x_2+x_5=3\\ & x_1,x_2,x_3,x_4,x_5\geq0 \end{matrix}\]
and set up the initial tableau
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | rhs |
|---|---|---|---|---|---|
| 1 | 1 | -1 | 0 | 0 | 2 |
| -1 | 1 | 0 | -1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 3 |
| 1 | -2 | 0 | 0 | 0 | 0 |
but this tableau is not in canonical form, i.e. there is no presence of a starting point for the simplex algorithm. Consider the corresponding artificial LP
\[\begin{matrix} \textrm{minimize} & a_1+a_2\\ \textrm{subject to} & x_1+x_2-x_3+a_1=2\\ & -x_1+x_2-x_4+a_2=1\\ & x_2+x_5=3\\ & x_1,x_2,x_3,x_4,x_5\geq0 \end{matrix}\]
which is equivalent to
\[\begin{matrix} \textrm{minimize} & -2x_2+x_3+x_4+3\\ \textrm{subject to} & x_1+x_2-x_3+a_1=2\\ & -x_1+x_2-x_4+a_2=1\\ & x_2+x_5=3\\ & x_1,x_2,x_3,x_4,x_5\geq0 \end{matrix}\]
Applying the simplex algorithm on the artificial LP yields the following tableaux.
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(a_1\) | \(a_2\) | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 1 | -1 | 0 | 0 | 1 | 0 | 2 |
| -1 | 1 | 0 | -1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 3 |
| 0 | -2 | 1 | 1 | 0 | 0 | 0 | -3 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(a_1\) | \(a_2\) | rhs |
|---|---|---|---|---|---|---|---|
| 2 | 0 | -1 | 1 | 0 | 1 | -1 | 1 |
| -1 | 1 | 0 | -1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | -1 | 2 |
| -2 | 0 | 1 | -1 | 0 | 0 | 2 | -1 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(a_1\) | \(a_2\) | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 0 | -1/2 | 1/2 | 0 | 1/2 | -1/2 | 1/2 |
| 0 | 1 | -1/2 | -1/2 | 0 | 1/2 | 1/2 | 3/2 |
| 0 | 0 | 1/2 | 1/2 | 1 | -1/2 | -1/2 | 3/2 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
All coefficients in the objective row of the tableau are non-negative, so the simplex algorithm stops. Eliminating the artificial columns and objective row derives the table
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | rhs | ||
|---|---|---|---|---|---|---|---|
| 1 | 0 | -1/2 | 1/2 | 0 | 1/2 | ||
| 0 | 1 | -1/2 | -1/2 | 0 | 3/2 | ||
| 0 | 0 | 1/2 | 1/2 | 1 | 3/2 |
which states that the original LP is equivalent to
\[\begin{matrix} \textrm{minimize} & z(x_1,x_2)=x_1-2x_2\\ \textrm{subject to} & x_1-\frac{x_3}{2}+\frac{x_4}{2}=\frac{1}{2}\\ & x_2-\frac{x_3}{2}-\frac{x_4}{2}=\frac{3}{2}\\ & \frac{x_3}{2}+\frac{x_4}{2}+x_5=\frac{3}{2}\\ & x_1,x_2,x_3,x_4,x_5\geq0 \end{matrix}\]
which can be rewritten as
\[\begin{matrix} \textrm{minimize} & -\frac{x_3}{2}-\frac{3x_4}{2}-\frac{5}{2}\\ \textrm{subject to} & x_1-\frac{x_3}{2}+\frac{x_4}{2}=\frac{1}{2}\\ & x_2-\frac{x_3}{2}-\frac{x_4}{2}=\frac{3}{2}\\ & \frac{x_3}{2}+\frac{x_4}{2}+x_5=\frac{3}{2}\\ & x_1,x_2,x_3,x_4,x_5\geq0 \end{matrix}\]
The initial tableau is now
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | rhs | ||
|---|---|---|---|---|---|---|---|
| 1 | 0 | -1/2 | 1/2 | 0 | 1/2 | ||
| 0 | 1 | -1/2 | -1/2 | 0 | 3/2 | ||
| 0 | 0 | 1/2 | 1/2 | 1 | 3/2 | ||
| 0 | 0 | -1/2 | -3/2 | 0 | 5/2 |
which says that the simplex algorithm starts at the point \(\left(\frac{1}{2},\frac{3}{2}\right)\) where the objective function attains the value \(-\frac{5}{2}.\)
We now proceed as usual.
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | rhs | ||
|---|---|---|---|---|---|---|---|
| 2 | 0 | -1 | 1 | 0 | 1 | ||
| 1 | 1 | -1 | 0 | 0 | 2 | ||
| -1 | 0 | 1 | 0 | 1 | 1 | ||
| 3 | 0 | -2 | 0 | 0 | 4 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | rhs | ||
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 | 2 | ||
| 0 | 1 | 0 | 0 | 1 | 3 | ||
| -1 | 0 | 1 | 0 | 1 | 1 | ||
| 1 | 0 | 0 | 0 | 2 | 6 |
The simplex algorithm stops with the optimal solution \((x_1,x_2)=(0,3)\) and optimal value \(-6.\)
3.4 Cutting-Plane Algorithm
The last two examples, luckily, have an integer optimal solution, so restricting them to ILPs makes no difference. But what if that is not the case?
Example 4. Consider the ILP
\[\begin{matrix} \textrm{minimize} & x+2y\\ \textrm{subject to} & -2x-y\leq-4\\ & x-3y\leq1\\ & x,y\in\mathbb{Z},x,y\geq0 \end{matrix}\]
with its relaxation LP
\[\begin{matrix} \textrm{minimize} & x+2y\\ \textrm{subject to} & -2x-y\leq-4\\ & x-3y\leq1\\ & x,y\geq0 \end{matrix}\]
We convert the relaxation LP into standard form
\[\begin{matrix} \textrm{minimize} & z(x,y)=x+2y\\ \textrm{subject to} & 2x+y-s_1=4\\ & x-3y+s_2=1\\ & x,y,s_1,s_2\geq0 \end{matrix}\]
and consider the artificial LP
\[\begin{matrix} \textrm{minimize} & a\\ \textrm{subject to} & 2x+y-s_1+a=4\\ & x-3y+s_2=1\\ & x,y,s_1,s_2,a\geq0 \end{matrix}\]
or equivalently,
\[\begin{matrix} \textrm{minimize} & -2x-y+s_1+4\\ \textrm{subject to} & 2x+y-s_1+a=4\\ & x-3y+s_2=1\\ & x,y,s_1,s_2,a\geq0 \end{matrix}\]
The simplex method gives the tableaux
| x | y | \(s_1\) | \(s_2\) | a | rhs |
|---|---|---|---|---|---|
| 2 | 1 | -1 | 0 | 1 | 4 |
| 1 | -3 | 0 | 1 | 0 | 1 |
| -2 | -1 | 1 | 0 | 0 | -4 |
| x | y | \(s_1\) | \(s_2\) | a | rhs |
|---|---|---|---|---|---|
| 0 | 7 | -1 | -2 | 1 | 2 |
| 1 | -3 | 0 | 1 | 0 | 1 |
| 0 | -7 | 1 | 3 | 0 | -2 |
| x | y | \(s_1\) | \(s_2\) | a | rhs |
|---|---|---|---|---|---|
| 0 | 1 | -1/7 | -2/7 | 1/7 | 2/7 |
| 1 | 0 | -3/7 | 1/7 | 3/7 | 13/7 |
| 0 | 0 | 0 | 1 | 1 | 0 |
Eliminating the artificial column and objective row derives the table
| x | y | \(s_1\) | \(s_2\) | rhs |
|---|---|---|---|---|
| 0 | 1 | -1/7 | -2/7 | 2/7 |
| 1 | 0 | -3/7 | 1/7 | 13/7 |
so the initial relaxation LP is equivalent to
\[\begin{matrix} \textrm{minimize} & z(x,y)=x+2y\\ \textrm{subject to} & y-\frac{s_1}{7}-\frac{2s_2}{7}=\frac{2}{7}\\ & x-\frac{3s_1}{7}+\frac{s_2}{7}=\frac{13}{7}\\ & x,y,s_1,s_2\geq0 \end{matrix}\]
which can be rewritten as
\[\begin{matrix} \textrm{minimize} & \frac{5s_1}{7}+\frac{3s_2}{7}+\frac{17}{7}\\ \textrm{subject to} & y-\frac{s_1}{7}-\frac{2s_2}{7}=\frac{2}{7}\\ & x-\frac{3s_1}{7}+\frac{s_2}{7}=\frac{13}{7}\\ & x,y,s_1,s_2\geq0 \end{matrix}\]
yielding the tableau
| x | y | \(s_1\) | \(s_2\) | rhs |
|---|---|---|---|---|
| 0 | 1 | -1/7 | -2/7 | 2/7 |
| 1 | 0 | -3/7 | 1/7 | 13/7 |
| 0 | 0 | 4/7 | 1/7 | -17/7 |
which says that the simplex algorithm starts at the point \(\left(\frac{13}{7},\frac{2}{7}\right)\) and stops immediately with the optimal value \(\frac{17}{7}.\)
However, the optimal solution is not integral, i.e. the simplex algorithm does not yield a feasible solution for the given ILP. Gomorov [1958] proposed an extension of Dantzig’s idea, known as the cutting-plane algorithm, for dealing with such cases.
The second row of the optimal relaxation LP tableau is
\[\frac{13}{7}=x-\frac{3s_1}{7}+\frac{s_2}{7}\] \[\Leftrightarrow 1-x+s_1=\frac{4s_1}{7}+\frac{s_2}{7}-\frac{6}{7}\geq-\frac{6}{7}\] since \(s_1,s_2\geq0.\) For the ILP, \(x\in\mathbb{Z}\) and \(s_1=2x+y-4\in\mathbb{Z}\) hence \(1-x+s_1\geq0\) and we add a new constraint
\[\frac{4s_1}{7}+\frac{s_2}{7}-\frac{6}{7}\geq0\Leftrightarrow-\frac{4s_1}{7}-\frac{s_2}{7}\leq-\frac{6}{7}\]
called a cut to the relaxation LP, which then becomes
\[\begin{matrix} \textrm{minimize} & \frac{5s_1}{7}+\frac{3s_2}{7}+\frac{17}{7}\\ \textrm{subject to} & y-\frac{s_1}{7}-\frac{2s_2}{7}=\frac{2}{7}\\ & x-\frac{3s_1}{7}+\frac{s_2}{7}=\frac{13}{7}\\ & \frac{4s_1}{7}+\frac{s_2}{7}-s_3=\frac{6}{7}\\ & x,y,s_1,s_2,s_3\geq0 \end{matrix}\]
We can rewrite the cut constraint above as
\[x-1\leq s_1=2x+y-4\Leftrightarrow x+y\geq3\]
and plot it on the original feasible region for better visualization.
The corresponding artificial LP of the updated relaxation LP is
\[\begin{matrix} \textrm{minimize} & a\\ \textrm{subject to} & y-\frac{s_1}{7}-\frac{2s_2}{7}=\frac{2}{7}\\ & x-\frac{3s_1}{7}+\frac{s_2}{7}=\frac{13}{7}\\ & \frac{4s_1}{7}+\frac{s_2}{7}-s_3+a=\frac{6}{7}\\ & x,y,s_1,s_2,s_3,a\geq0 \end{matrix}\]
or equivalently
\[\begin{matrix} \textrm{minimize} & -\frac{4s_1}{7}-\frac{s_2}{7}+s_3+\frac{6}{7}\\ \textrm{subject to} & y-\frac{s_1}{7}-\frac{2s_2}{7}=\frac{2}{7}\\ & x-\frac{3s_1}{7}+\frac{s_2}{7}=\frac{13}{7}\\ & \frac{4s_1}{7}+\frac{s_2}{7}-s_3+a=\frac{6}{7}\\ & x,y,s_1,s_2,s_3,a\geq0 \end{matrix}\]
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | a | rhs |
|---|---|---|---|---|---|---|
| 0 | 1 | -1/7 | -2/7 | 0 | 0 | 2/7 |
| 1 | 0 | -3/7 | 1/7 | 0 | 0 | 13/7 |
| 0 | 0 | 4/7 | 1/7 | -1 | 1 | 6/7 |
| 0 | 0 | -4/7 | -1/7 | 1 | 0 | -6/7 |
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | a | rhs |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | -1/4 | -1/4 | 1/4 | 1/2 |
| 1 | 0 | 0 | 1/4 | -3/4 | 3/4 | 5/2 |
| 0 | 0 | 1 | 1/4 | -7/4 | 7/4 | 3/2 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | rhs |
|---|---|---|---|---|---|
| 0 | 1 | 0 | -1/4 | -1/4 | 1/2 |
| 1 | 0 | 0 | 1/4 | -3/4 | 5/2 |
| 0 | 0 | 1 | 1/4 | -7/4 | 3/2 |
so the \(1^{\textrm{st}}\)-cut relaxation LP can be rewritten as
\[\begin{matrix} \textrm{minimize} & \frac{5s_1}{7}+\frac{3s_2}{7}+\frac{17}{7}\\ \textrm{subject to} & y-\frac{s_2}{4}-\frac{s_3}{4}=\frac{1}{2}\\ & x+\frac{s_2}{4}-\frac{3s_3}{4}=\frac{5}{2}\\ & s_1+\frac{s_2}{4}-\frac{7s_3}{4}=\frac{3}{2}\\ & x,y,s_1,s_2,s_3\geq0 \end{matrix}\]
or equivalently
\[\begin{matrix} \textrm{minimize} & \frac{s_2}{4}+\frac{5s_3}{4}+\frac{7}{2}\\ \textrm{subject to} & y-\frac{s_2}{4}-\frac{s_3}{4}=\frac{1}{2}\\ & x+\frac{s_2}{4}-\frac{3s_3}{4}=\frac{5}{2}\\ & s_1+\frac{s_2}{4}-\frac{7s_3}{4}=\frac{3}{2}\\ & x,y,s_1,s_2,s_3\geq0 \end{matrix}\]
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | rhs |
|---|---|---|---|---|---|
| 0 | 1 | 0 | -1/4 | -1/4 | 1/2 |
| 1 | 0 | 0 | 1/4 | -3/4 | 5/2 |
| 0 | 0 | 1 | 1/4 | -7/4 | 3/2 |
| 0 | 0 | 0 | 1/4 | 5/4 | -7/2 |
The simplex algorithm starts at the point \(\left(\frac{5}{2},\frac{1}{2}\right)\) and stops immediately with the optimal value \(\frac{7}{2}.\)
Again, this optimal solution is not integral, so we look at the first row of the optimal tableau
\[y=\frac{s_2}{4}+\frac{s_3}{4}+\frac{1}{2}\geq\frac{1}{2}\]
since \(s_2,s_3\geq0,\) and \(y\in\mathbb{Z}\) so \(y\geq1\) and we add the \(2^{\textrm{nd}}\) cut
\[\frac{s_2}{4}+\frac{s_3}{4}+\frac{1}{2}\geq1\Leftrightarrow-\frac{s_2}{4}-\frac{s_3}{4}\leq-\frac{1}{2}\]
to the \(1^{\textrm{st}}\)-cut relaxation LP as
\[\begin{matrix} \textrm{minimize} & \frac{s_2}{4}+\frac{5s_3}{4}+\frac{7}{2}\\ \textrm{subject to} & y-\frac{s_2}{4}-\frac{s_3}{4}=\frac{1}{2}\\ & x+\frac{s_2}{4}-\frac{3s_3}{4}=\frac{5}{2}\\ & s_1+\frac{s_2}{4}-\frac{7s_3}{4}=\frac{3}{2}\\ & \frac{s_2}{4}+\frac{s_3}{4}-s_4=\frac{1}{2}\\ & x,y,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
The corresponding artificial LP is now
\[\begin{matrix} \textrm{minimize} & a\\ \textrm{subject to} & y-\frac{s_2}{4}-\frac{s_3}{4}=\frac{1}{2}\\ & x+\frac{s_2}{4}-\frac{3s_3}{4}=\frac{5}{2}\\ & s_1+\frac{s_2}{4}-\frac{7s_3}{4}=\frac{3}{2}\\ & \frac{s_2}{4}+\frac{s_3}{4}-s_4+a=\frac{1}{2}\\ & x,y,s_1,s_2,s_3,s_4,a\geq0 \end{matrix}\]
or equivalently
\[\begin{matrix} \textrm{minimize} & -\frac{s_2}{4}-\frac{s_3}{4}+s_4+\frac{1}{2}\\ \textrm{subject to} & y-\frac{s_2}{4}-\frac{s_3}{4}=\frac{1}{2}\\ & x+\frac{s_2}{4}-\frac{3s_3}{4}=\frac{5}{2}\\ & s_1+\frac{s_2}{4}-\frac{7s_3}{4}=\frac{3}{2}\\ & \frac{s_2}{4}+\frac{s_3}{4}-s_4+a=\frac{1}{2}\\ & x,y,s_1,s_2,s_3,s_4,a\geq0 \end{matrix}\]
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | a | rhs |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | -1/4 | -1/4 | 0 | 0 | 1/2 |
| 1 | 0 | 0 | 1/4 | -3/4 | 0 | 0 | 5/2 |
| 0 | 0 | 1 | 1/4 | -7/4 | 0 | 0 | 3/2 |
| 0 | 0 | 0 | 1/4 | 1/4 | -1 | 1 | 1/2 |
| 0 | 0 | 0 | -1/4 | -1/4 | 1 | 0 | -1/2 |
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | a | rhs |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | -1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | -3 | 3 | 4 |
| 0 | 0 | 1 | 2 | 0 | -7 | 7 | 5 |
| 0 | 0 | 0 | 1 | 1 | -4 | 4 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | -1 | 1 | |
| 1 | 0 | 0 | 1 | 0 | -3 | 4 | |
| 0 | 0 | 1 | 2 | 0 | -7 | 5 | |
| 0 | 0 | 0 | 1 | 1 | -4 | 2 |
so the \(2^{\textrm{nd}}\)-cut relaxation LP can be rewritten as
\[\begin{matrix} \textrm{minimize} & \frac{s_2}{4}+\frac{5s_3}{4}+\frac{7}{2}\\ \textrm{subject to} & y-s_4=1\\ & x+s_2-3s_4=4\\ & s_1+2s_2-7s_4=5\\ & s_2+s_3-4s_4=2\\ & x,y,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
or equivalently
\[\begin{matrix} \textrm{minimize} & 6-s_2+5s_4\\ \textrm{subject to} & y-s_4=1\\ & x+s_2-3s_4=4\\ & s_1+2s_2-7s_4=5\\ & s_2+s_3-4s_4=2\\ & x,y,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
We now proceed as usual.
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | -1 | 1 | |
| 1 | 0 | 0 | 1 | 0 | -3 | 4 | |
| 0 | 0 | 1 | 2 | 0 | -7 | 5 | |
| 0 | 0 | 0 | 1 | 1 | -4 | 2 | |
| 0 | 0 | 0 | -1 | 0 | 5 | -6 |
| x | y | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | -1 | 1 | |
| 1 | 0 | 0 | 0 | -1 | 1 | 2 | |
| 0 | 0 | 1 | 0 | -2 | 1 | 1 | |
| 0 | 0 | 0 | 1 | 1 | -4 | 2 | |
| 0 | 0 | 0 | 0 | 1 | 1 | -4 |
The simplex algorithm stops at the optimal solution \((2,1)\) with the optimal value \(4.\) This is also the optimal solution to the initial ILP.
In words, the cutting-plane algorithm continuously updates the feasible region of the relaxation LP by dropping portions of it until an integer optimal solution is found. During the procedure, it creates a sequence of LPs whose optimal solutions converge to the original ILP optimal solution.
4 CPA Approach for BLP
4.1 Two Projects
We consider a sub-case of Example 1, where projects 3 & 4 are suspended by the government due to unknown issues.
| Project | 1 | 2 |
|---|---|---|
| Cost | 300 | 400 |
| NPV | 10 | 20 |
The BLP is now
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2\\ \textrm{subject to} & 300x_1+400x_2\leq600\\ & x_1,x_2\in\left\{0,1\right\} \end{matrix}\]
and the equivalent ILP is
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2\\ \textrm{subject to} & 3x_1+4x_2\leq6\\ & x_1\leq1\\ & x_2\leq1\\ & x\in\mathbb{Z}^2,x\geq0 \end{matrix}\]
with its corresponding relaxation LP
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2\\ \textrm{subject to} & 3x_1+4x_2\leq6\\ & x_1\leq1\\ & x_2\leq1\\ & x_1,x_2\geq0 \end{matrix}\]
Its standard form is
\[\begin{matrix} \textrm{minimize} & z(x_1,x_2)=-10x_1-20x_2\\ \textrm{subject to} & 3x_1+4x_2+s_1=6\\ & x_1+s_2=1\\ & x_2+s_3=1\\ & x_1,x_2,s_1,s_2,s_3\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs |
|---|---|---|---|---|---|
| 3 | 4 | 1 | 0 | 0 | 6 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| -10 | -20 | 0 | 0 | 0 | 0 |
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs |
|---|---|---|---|---|---|
| 3 | 0 | 1 | 0 | -4 | 2 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| -10 | 0 | 0 | 0 | 20 | 20 |
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs |
|---|---|---|---|---|---|
| 1 | 0 | 1/3 | 0 | -4/3 | 2/3 |
| 0 | 0 | -1/3 | 1 | 4/3 | 1/3 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 10/3 | 0 | 20/3 | 80/3 |
The current optimal solution is not integral. From the second row of the tableau
\[-\frac{s_1}{3}+s_2+\frac{4s_3}{3}=\frac{1}{3}\Leftrightarrow s_2+2s_3=\frac{1}{3}+\frac{s_1}{3}+\frac{2s_3}{3}\geq\frac{1}{3}\]
so we add the cut
\[\frac{1}{3}+\frac{s_1}{3}+\frac{2s_3}{3}\geq1\Leftrightarrow\frac{s_1}{3}+\frac{2s_3}{3}\geq\frac{2}{3}\]
to the relaxation LP
\[\begin{matrix} \textrm{minimize} & \frac{10s_1}{3}+\frac{20s_3}{3}-\frac{80}{3}\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}=\frac{2}{3}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}=\frac{1}{3}\\ & x_2+s_3=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}-s_4=\frac{2}{3}\\ & x_1,x_2,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
The cut can be rewritten as
\[1\leq s_2+2s_3=3-x_1-2x_2\Leftrightarrow x_1+2x_2\leq2.\]
The artificial LP is
\[\begin{matrix} \textrm{minimize} & a\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}=\frac{2}{3}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}=\frac{1}{3}\\ & x_2+s_3=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}-s_4+a=\frac{2}{3}\\ & x_1,x_2,s_1,s_2,s_3,s_4,a\geq0 \end{matrix}\]
or
\[\begin{matrix} \textrm{minimize} & -\frac{s_1}{3}-\frac{2s_3}{3}+s_4+\frac{2}{3}\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}=\frac{2}{3}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}=\frac{1}{3}\\ & x_2+s_3=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}-s_4+a=\frac{2}{3}\\ & x_1,x_2,s_1,s_2,s_3,s_4,a\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | a | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1/3 | 0 | -4/3 | 0 | 0 | 2/3 |
| 0 | 0 | -1/3 | 1 | 4/3 | 0 | 0 | 1/3 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1/3 | 0 | 2/3 | -1 | 1 | 2/3 |
| 0 | 0 | -1/3 | 0 | -2/3 | 1 | 0 | -2/3 |
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | a | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | -2 | 1 | -1 | 0 |
| 0 | 0 | 0 | 1 | 2 | -1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 2 | -3 | 3 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | -2 | 1 | 0 |
| 0 | 0 | 0 | 1 | 2 | -1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 2 | -3 | 2 |
Hence the updated relaxation LP can be rewritten as
\[\begin{matrix} \textrm{minimize} & \frac{10s_1}{3}+\frac{20s_3}{3}-\frac{80}{3}\\ \textrm{subject to} & x_1-2s_3+s_4=0\\ & s_2+2s_3-s_4=1\\ & x_2+s_3=1\\ & s_1+2s_3-3s_4=2\\ & x_1,x_2,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
or
\[\begin{matrix} \textrm{minimize} & 10s_4-20\\ \textrm{subject to} & x_1-2s_3+s_4=0\\ & s_2+2s_3-s_4=1\\ & x_2+s_3=1\\ & s_1+2s_3-3s_4=2\\ & x_1,x_2,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | -2 | 1 | 0 |
| 0 | 0 | 0 | 1 | 2 | -1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 2 | -3 | 2 |
| 0 | 0 | 0 | 0 | 0 | 10 | 20 |
The optimal solution to the initial BLP is \((0,1)\) with the optimal value of \(-20,\) i.e. the maximum attainable profit is $20.
4.2 Three Projects
If only project 4 is suspended
| Project | 1 | 2 | 3 | |
|---|---|---|---|---|
| Cost | 300 | 400 | 150 | |
| NPV | 10 | 20 | 10 |
the BLP is now
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2-10x_3\\ \textrm{subject to} & 300x_1+400x_2+150x_3\leq600\\ & x_1,x_2,x_3\in\left\{0,1\right\} \end{matrix}\]
and the equivalent ILP is
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2-10x_3\\ \textrm{subject to} & 3x_1+4x_2+\frac{3x_3}{2}\leq6\\ & x_1\leq1\\ & x_2\leq1\\ & x_3\leq1\\ & x\in\mathbb{Z}^2,x\geq0 \end{matrix}\]
with its corresponding relaxation LP
\[\begin{matrix} \textrm{minimize} & -10x_1-20x_2-10x_3\\ \textrm{subject to} & 3x_1+4x_2+\frac{3x_3}{2}\leq6\\ & x_1\leq1\\ & x_2\leq1\\ & x_3\leq1\\ & x_1,x_2,x_3\geq0 \end{matrix}\]
Its standard form is
\[\begin{matrix} \textrm{minimize} & z(x_1,x_2,x_3)=-10x_1-20x_2-10x_3\\ \textrm{subject to} & 3x_1+4x_2+\frac{3x_3}{2}+s_1=6\\ & x_1+s_2=1\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|---|
| 3 | 4 | 3/2 | 1 | 0 | 0 | 0 | 6 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| -10 | -20 | -10 | 0 | 0 | 0 | 0 | 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|---|
| 3 | 0 | 3/2 | 1 | 0 | -4 | 0 | 2 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| -10 | 0 | -10 | 0 | 0 | 20 | 0 | 20 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1/2 | 1/3 | 0 | -4/3 | 0 | 2/3 |
| 0 | 0 | -1/2 | -1/3 | 1 | 4/3 | 0 | 1/3 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | -5 | 10/3 | 0 | 20/3 | 0 | 80/3 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | rhs |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1/3 | 0 | -4/3 | -1/2 | 1/6 |
| 0 | 0 | 0 | -1/3 | 1 | 4/3 | 1/2 | 5/6 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 10/3 | 0 | 20/3 | 5 | 95/3 |
The current optimal solution is not integral. From the first row of the tableau
\[x_1+\frac{s_1}{3}-\frac{4s_3}{3}-\frac{s_4}{2}=\frac{1}{6}\Leftrightarrow-x_1+2s_3+s_4=\frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}-\frac{1}{6}\geq-\frac{1}{6}\]
so we add the cut
\[\frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}-\frac{1}{6}\geq0\Leftrightarrow\frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}\geq\frac{1}{6}\]
to the relaxation LP
\[\begin{matrix} \textrm{minimize} & \frac{10s_1}{3}+\frac{20s_3}{3}+5s_4-\frac{95}{3}\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}-\frac{s_4}{2}=\frac{1}{6}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}+\frac{s_4}{2}=\frac{5}{6}\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}-s_5=\frac{1}{6}\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5\geq0 \end{matrix}\]
The cut can be rewritten as
\[0\leq-x_1+2s_3+s_4=3-x_1-2x_2-x_3\Leftrightarrow x_1+2x_2+x_3\leq3.\]
The artificial LP is
\[\begin{matrix} \textrm{minimize} & a\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}-\frac{s_4}{2}=\frac{1}{6}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}+\frac{s_4}{2}=\frac{5}{6}\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}-s_5+a=\frac{1}{6}\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5,a\geq0 \end{matrix}\]
or
\[\begin{matrix} \textrm{minimize} & -\frac{s_1}{3}-\frac{2s_3}{3}-\frac{s_4}{2}+s_5+\frac{1}{6}\\ \textrm{subject to} & x_1+\frac{s_1}{3}-\frac{4s_3}{3}-\frac{s_4}{2}=\frac{1}{6}\\ & -\frac{s_1}{3}+s_2+\frac{4s_3}{3}+\frac{s_4}{2}=\frac{5}{6}\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & \frac{s_1}{3}+\frac{2s_3}{3}+\frac{s_4}{2}-s_5+a=\frac{1}{6}\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5,a\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) | a | rhs |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1/3 | 0 | -4/3 | -1/2 | 0 | 0 | 1/6 |
| 0 | 0 | 0 | -1/3 | 1 | 4/3 | 1/2 | 0 | 0 | 5/6 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1/3 | 0 | 2/3 | 1/2 | -1 | 1 | 1/6 |
| 0 | 0 | 0 | -1/3 | 0 | -2/3 | -1/2 | 1 | 0 | -1/6 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) | a | rhs |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | -2 | -1 | 1 | -1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 2 | 1 | -1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 2 | 3/2 | -3 | 3 | 1/2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) | rhs |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | -2 | -1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 2 | 1 | -1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 2 | 3/2 | -3 | 1/2 |
Hence the updated relaxation LP can be rewritten as
\[\begin{matrix} \textrm{minimize} & \frac{10s_1}{3}+\frac{20s_3}{3}+5s_4-\frac{95}{3}\\ \textrm{subject to} & x_1-2s_3-s_4+s_5=0\\ & s_2+2s_3+s_4-s_5=1\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & s_1+2s_3+\frac{3s_4}{2}-3s_5=\frac{1}{2}\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5\geq0 \end{matrix}\]
or
\[\begin{matrix} \textrm{minimize} & 10s_4+10s_5-30\\ \textrm{subject to} & x_1-2s_3-s_4+s_5=0\\ & s_2+2s_3+s_4-s_5=1\\ & x_2+s_3=1\\ & x_3+s_4=1\\ & s_1+2s_3+\frac{3s_4}{2}-3s_5=\frac{1}{2}\\ & x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5\geq0 \end{matrix}\]
| \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) | rhs |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | -2 | -1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 2 | 1 | -1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 2 | 3/2 | -3 | 1/2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 30 |
The optimal solution to the initial BLP is \((0,1,1)\) with the optimal value of \(-30,\) i.e. the maximum attainable profit is $30.
4.3 Four Projects
We reconsider our original introductory example.
\[\begin{matrix} \textrm{maximize} & 10x_1+20x_2+10x_3+10x_4\\ \textrm{subject to} & 6x_1+8x_2+3x_3+2x_4\leq12\\ & x_i\in\left\{0,1\right\},\forall i=\overline{1,4} \end{matrix}\]
This problem is of 4-dimensional, so visualization is rather complicated and hence, we left it as an exercise to the reader. The solution should proceed as follows:
- Change the problem to minimization and add the slack variables \(s_1,s_2,s_3,s_4,s_5;\)
- The simplex algorithm yields the optimal solution \(\left(0,\frac{7}{8},1,1\right)\) and optimal value \(-\frac{75}{2}.\)
- Observe the second row of the tableau and add the cut \[\frac{3x_1}{4}+\frac{s_1}{8}+\frac{5s_4}{8}+\frac{3s_5}{4}\geq\frac{7}{8}\Leftrightarrow x_2+x_3+x_4\leq2\] to the relaxation LP. Add the slack variable \(s_6.\)
- The simplex algorithm yields the optimal solution \(\left(\frac{1}{3},1,0,1\right)\) and optimal value \(-\frac{100}{3}.\)
- Observe the first row of the tableau and add the cut \[\frac{x_3}{6}+\frac{s_1}{6}+\frac{2s_6}{6}\geq\frac{1}{3}\Leftrightarrow x_1+2x_2+x_3+x_4\leq3\] to the relaxation LP. Note that \(s_6\in\mathbb{Z}\) due to the third row.
- The simplex algorithm yields the optimal solution \((1,0,1,1)\) and optimal value \(-30,\) i.e. the optimal profit is $30.
5 Remarks
- For the cutting-plane algorithm, complexity increases by a polynomial of the project count comparing to the exponential increment of the brute-force algorithm.
- Another approach for ILP & BLP is the branch and bound algorithm which attempt to divide the feasible region of the relaxation LP into smaller sub-regions. This algorithm is more complicated, but it converges faster than the cutting-plane algorithm.
- Most current solvers implement the branch and cut algorithm, the combination of these two algorithms.
6 References
F. S. Hillier, G. J. Lieberman, Introduction to Operations Research, 7th ed. McGraw-Hill, 2001.