MIP 2: Modeling Constructs for Internal Decisions

Packages Used: No new packages are used in this notebook.

In an LP, no decision variable can be restricted to being integer-valued, and no decisions can be made (internally) as part of the solution procedure. In practice, what usually necessitates representing a problem as a MILP is that that one or more discrete decisions need to be made as part of the solution procedure.

1. Logical Conditions

Binary decision variables take the value of 1 or 0. These remain integers with respect to the mathematical and logical operations performed, but model discrete binary decisions:

• true/false
• yes/no
• on/off
• do/don't do

Single binary variable

T = [0; 1]
TT(f) = [T [f(row...) for row in eachrow(T)]];

TT((x) -> 1 - x )    # Not X

2×2 Matrix{Int64}:
 0  1
 1  0

Two binary vaiables

T = [0 0; 0 1; 1 0; 1 1]
TT(f) = [T [f(row...) for row in eachrow(T)]];

TT((x,y) -> x + y == 2 )   # X and Y (AND)

4×3 Matrix{Int64}:
 0  0  0
 0  1  0
 1  0  0
 1  1  1

TT((x,y) -> x + y >= 1 )   # X or Y (inclusive OR)

4×3 Matrix{Int64}:
 0  0  0
 0  1  1
 1  0  1
 1  1  1

TT((x,y) -> x + y == 1 )   # X or Y but not both (exclusive OR)

4×3 Matrix{Int64}:
 0  0  0
 0  1  1
 1  0  1
 1  1  0

TT((x,y) -> x <= y )   # If X then Y (implication)

4×3 Matrix{Int64}:
 0  0  1
 0  1  1
 1  0  0
 1  1  1

TT((x,y) -> x + y <= 1 )   # If X then not Y

4×3 Matrix{Int64}:
 0  0  1
 0  1  1
 1  0  1
 1  1  0

TT((x,y) -> x == y )   # X if and only if Y (If X then Y, and if Y then X)

4×3 Matrix{Int64}:
 0  0  1
 0  1  0
 1  0  0
 1  1  1

Three binary vaiables

T = [0 0 0; 0 1 0; 1 0 0; 1 1 0; 0 0 1; 0 1 1; 1 0 1; 1 1 1]
TT(f) = [T [f(row...) for row in eachrow(T)]];

TT((x,y,z) -> x + y + z <= 1)   # Select at most one (packing constraint)

8×4 Matrix{Int64}:
 0  0  0  1
 0  1  0  1
 1  0  0  1
 1  1  0  0
 0  0  1  1
 0  1  1  0
 1  0  1  0
 1  1  1  0

TT((x,y,z) -> x + y + z == 1)   # Select exactly one (partition constraint)

8×4 Matrix{Int64}:
 0  0  0  0
 0  1  0  1
 1  0  0  1
 1  1  0  0
 0  0  1  1
 0  1  1  0
 1  0  1  0
 1  1  1  0

TT((x,y,z) -> x + y + z >= 1)   # Select at least one (covering constraint)

8×4 Matrix{Int64}:
 0  0  0  0
 0  1  0  1
 1  0  0  1
 1  1  0  1
 0  0  1  1
 0  1  1  1
 1  0  1  1
 1  1  1  1

TT((x,y,z) -> x <= y && x <= z )   # If X then Y and Z

8×4 Matrix{Int64}:
 0  0  0  1
 0  1  0  1
 1  0  0  0
 1  1  0  0
 0  0  1  1
 0  1  1  1
 1  0  1  0
 1  1  1  1

TT((x,y,z) -> x <= y + z )   # If X then Y or Z

8×4 Matrix{Int64}:
 0  0  0  1
 0  1  0  1
 1  0  0  0
 1  1  0  1
 0  0  1  1
 0  1  1  1
 1  0  1  1
 1  1  1  1

TT((x,y,z) -> x >= y + z - 1 )   # If Y and Z then X

8×4 Matrix{Int64}:
 0  0  0  1
 0  1  0  1
 1  0  0  1
 1  1  0  1
 0  0  1  1
 0  1  1  0
 1  0  1  1
 1  1  1  1

TT((x,y,z) -> x >= y && x >= z )   # If Y or Z then X

8×4 Matrix{Int64}:
 0  0  0  1
 0  1  0  0
 1  0  0  1
 1  1  0  1
 0  0  1  0
 0  1  1  0
 1  0  1  1
 1  1  1  1

Ex 1: Capital Budgeting

Many capital budgeting problems involve investment opportunities and can have additional constraints with respect to their occurrence.

revenue = [9, 12, 7, 5, 2]
cost = [5, 7, 4, 3, 1]
cmax = 14
sum(revenue) - sum(cost)

15

using JuMP, GLPK
model = Model(GLPK.Optimizer)
M = 1:length(revenue)
@variable(model, 0 <= x[1:length(revenue)] <= 1 )
@objective(model, Max, sum((revenue[i] - cost[i])*x[i] for i ∈ M) )
@constraint(model, sum(cost[i]*x[i] for i ∈ M) <= cmax )
optimize!(model)
objective_value(model), value.(x)

(10.857142857142858, [1.0, 0.5714285714285714, 1.0, 0.0, 1.0])

sum((revenue.-cost).*floor.(value.(x)))

8.0

using JuMP, Gurobi
model = Model(GLPK.Optimizer)
M = 1:length(revenue)
@variable(model, x[1:length(revenue)], Bin )
@objective(model, Max, sum((revenue[i] - cost[i])*x[i] for i ∈ M) )
@constraint(model, sum(cost[i]*x[i] for i ∈ M) <= cmax )
print(model)
optimize!(model)
objective_value(model), value.(x)

$$ \begin{aligned} \max\quad & 4 x_{1} + 5 x_{2} + 3 x_{3} + 2 x_{4} + x_{5}\\ \text{Subject to} \quad & 5 x_{1} + 7 x_{2} + 4 x_{3} + 3 x_{4} + x_{5} \leq 14.0\\ & x_{1} \in \{0, 1\}\\ & x_{2} \in \{0, 1\}\\ & x_{3} \in \{0, 1\}\\ & x_{4} \in \{0, 1\}\\ & x_{5} \in \{0, 1\}\\ \end{aligned} $$

(10.0, [1.0, 1.0, 0.0, 0.0, 1.0])

Additional Constraints

# 1. Can only make two investments
@constraint(model, sum(x[i] for i ∈ M) <= 2 )
optimize!(model)
objective_value(model), value.(x)

(9.0, [1.0, 1.0, 0.0, 0.0, 0.0])

# 2. If investment 2 is made, investment 5 must also be made
@constraint(model, x[2] <= x[5] )
optimize!(model)
objective_value(model), value.(x)

(7.0, [1.0, 0.0, 1.0, 0.0, 0.0])

# 3. Both investments 1 and 3 cannot be made
@constraint(model, x[1] + x[3] == 1 )
optimize!(model)
objective_value(model), value.(x)

(6.0, [1.0, 0.0, 0.0, 1.0, 0.0])

# 4. If investment 1 or 4 is made then investment 5 must be made
@constraint(model, x[5] >= x[1] )
@constraint(model, x[5] >= x[4] )
optimize!(model)
objective_value(model), value.(x)

(5.0, [1.0, 0.0, 0.0, 0.0, 1.0])

# 5. At least one of investments 2, 3, or 4 must be made
@constraint(model, x[2] + x[3] + x[4] >= 1 )
optimize!(model)
objective_value(model), value.(x)

(4.0, [0.0, 0.0, 1.0, 0.0, 1.0])

print(model)

$$ \begin{aligned} \max\quad & 4 x_{1} + 5 x_{2} + 3 x_{3} + 2 x_{4} + x_{5}\\ \text{Subject to} \quad & x_{1} + x_{3} = 1.0\\ & -x_{1} + x_{5} \geq 0.0\\ & -x_{4} + x_{5} \geq 0.0\\ & x_{2} + x_{3} + x_{4} \geq 1.0\\ & 5 x_{1} + 7 x_{2} + 4 x_{3} + 3 x_{4} + x_{5} \leq 14.0\\ & x_{1} + x_{2} + x_{3} + x_{4} + x_{5} \leq 2.0\\ & x_{2} - x_{5} \leq 0.0\\ & x_{1} \in \{0, 1\}\\ & x_{2} \in \{0, 1\}\\ & x_{3} \in \{0, 1\}\\ & x_{4} \in \{0, 1\}\\ & x_{5} \in \{0, 1\}\\ \end{aligned} $$

2. Semi-Continuous Variables

In practice, what can necessitate representing a problem as a MILP is that an (otherwise continuous) decision variable $x$ has a non-zero lower bound $l$ only if it is used in a solution; otherwise, it can remain at zero. This type of discontinuous variable is termed semi-continuous: $ x = \{ 0 \} \cup \left[ l, u \right] $.

For example, if there were minimum order quantity (MOQ) restrictions on the purchase of an item, then it would be incorrect to just add these quantities as lower bounds to the quantity purchased of each item because it might be better as a result of the minimum purchase quantity, to not purchase one of the items. This would violate a lower-bound constraint, but if a binary decision variable could be used to represent whether or not an item is purchased, and then the minimum purchase quantity would be enforced only when the item is purchased. Adding binary decision variables turns an LP into a MILP.

Ex 2: Arbitrage Opportunity with MOQ Restrictions

Continuing with Ex 1 from LP 2, where the optimal solution was to purchase 15 pounds of coffee or peppers for a profit of \$195. If there were minimum order quantities (MOQ) for the coffee or peppers, then it would be incorrect to just add these quantities as lower bounds to the quantity purchased of each item. Assume that there is a MOQ of 20 pounds for coffee and no MOQ for peppers. Just adding the MOQ as a constraint to the LP gives the following:

model = Model(GLPK.Optimizer)
@variable(model, 20 <= x₁ )                 # MOQ LB of 20
@variable(model,  0 <= x₂ )
@objective(model, Max, 4x₁ + 9x₂ )
@constraint(model, 2x₁ + 6x₂ <= 120 )       # $120 budget constraint
@constraint(model, x₁ + x₂ <= 30 )          # 30 pound weight constraint
print(model)
optimize!(model)
objective_value(model), value(x₁), value(x₂)

$$ \begin{aligned} \max\quad & 4 x₁ + 9 x₂\\ \text{Subject to} \quad & 2 x₁ + 6 x₂ \leq 120.0\\ & x₁ + x₂ \leq 30.0\\ & x₁ \geq 20.0\\ & x₂ \geq 0.0\\ \end{aligned} $$

(170.0, 20.0, 10.0)

In order to correctly account for the 20-pound coffee MOQ, a binary decision variable $y_1 \in \{ 0, 1 \}$ can be added to the model that is used to "switch on" (by taking a value of 1) the 20-pound coffee LB only when any $x_1 \ge 0$ coffee is purchased, making the model a MILP. Internal to the model, $y_1$ decides not to purchase coffee (by taking a value of 0), increasing the total profit to from \$170 for the LP to \\$180 for the MILP:

model = Model(GLPK.Optimizer)
@variable(model, 0 <= x₁ )
@variable(model, 0 <= x₂ )
@variable(model, y₁, Bin )              # Add binary decision variable 
@objective(model, Max, 4x₁ + 9x₂ )
@constraint(model, 2x₁ + 6x₂ <= 120 )
@constraint(model, x₁ + x₂ <= 30 )
@constraint(model, x₁ >= 20y₁)          # Switch on MOQ LB only if y₁ = 1
@constraint(model, x₁ <= 30y₁)          # Force y₁ = 1 if x₁ ≥ 0 (where 30 is max x₁ UB) 
print(model)
optimize!(model)
objective_value(model), value(x₁), value(x₂)

$$ \begin{aligned} \max\quad & 4 x₁ + 9 x₂\\ \text{Subject to} \quad & x₁ - 20 y₁ \geq 0.0\\ & 2 x₁ + 6 x₂ \leq 120.0\\ & x₁ + x₂ \leq 30.0\\ & x₁ - 30 y₁ \leq 0.0\\ & x₁ \geq 0.0\\ & x₂ \geq 0.0\\ & y₁ \in \{0, 1\}\\ \end{aligned} $$

(180.0, 0.0, 20.0)

3. Maximum Values

Let $ y = \operatorname{max} \bigl\{ x_1, x_2, \dots, x_n \bigr\} $ for continuous variables $x_i$ with $0 \le x_i \le u$. MIP formulation:

$ \begin{eqnarray*} \quad y &\ge& x_i \\ \quad y &\le& x_i + u(1 - z_i) \\ \quad \sum_{i=1}^n z_i &=& 1 \end{eqnarray*} $

In practive, $x_i$ are continuous decision variables inside of the model. To better illustrate the MIP formulation to determine the maximum $x_i$ value, they are defined outside the model (along with an upper bound $u$ that is assumed to be 100):

x = [7, 4.5, 3, 9, 0, 5]
u = 100

using JuMP, GLPK
model = Model(GLPK.Optimizer)
N = 1:length(x)
@variable(model, y )
@variable(model, z[1:length(N)], Bin )
@objective(model, Max, y )
@constraint(model, [i ∈ N], y >= x[i] )
@constraint(model, [i ∈ N], y <= x[i] + u*(1 - z[i]))
@constraint(model, sum(z[i] for i ∈ N) == 1)
optimize!(model)
objective_value(model), value(y), value.(z)

(9.0, 9.0, [0.0, 0.0, 0.0, 1.0, 0.0, 0.0])

Ex 3: Arbitrage Opportunity with Import Duty

Continuing with Ex 2 from LP 3, assume that there is an import duty of \$2 per pound that is only imposed on the single item that is imported in the largest quantity. This is done to try to reduce hoarding and/or speculation (i.e., arbitrage). The following solution was found without the import duty:

using DataFrames
df = DataFrame(Item = ["Coffee", "Peppers", "Ginger", "Tea", "Candy"], 
    Max_Order = [40, 10, 2, 5, 15], Sale_Price = [6, 15, 8, 25, 4], 
    Purchase_Price = [2, 6, 1, 5, 2])

using JuMP, GLPK
u,p,c = df.Max_Order, df.Sale_Price, df.Purchase_Price
N = 1:length(p)
model = Model(GLPK.Optimizer)
@variable(model, 0 <= x[i = N] <= u[i] )
@objective(model, Max, sum((p[i] - c[i])*x[i] for i ∈ N) )
@constraint(model, sum(c[i]*x[i] for i ∈ N) <= 120 )
@constraint(model, sum(x[i] for i ∈ N) <= 30 )
optimize!(model)
df.Purchase_Quantity = value.(x)                       # Add output to DataFrame
println(" \nTotal Profit: ", objective_value(model))   # Format output
df

 
Total Profit: 256.0

5 rows × 5 columns

	Item	Max_Order	Sale_Price	Purchase_Price	Purchase_Quantity
	String	Int64	Int64	Int64	Float64
1	Coffee	40	6	2	13.0
2	Peppers	10	15	6	10.0
3	Ginger	2	8	1	2.0
4	Tea	5	25	5	5.0
5	Candy	15	4	2	0.0

Including the duty on the maximum purchase quantity results in the following:

using JuMP, GLPK
u,p,c = df.Max_Order, df.Sale_Price, df.Purchase_Price
N = 1:length(p)
U = maximum(u)                                           # Maximum weight of any item
duty = 2                                                 # Import duty
model = Model(GLPK.Optimizer)
@variable(model, 0 <= x[i = N] <= u[i] )
@variable(model, y )
@variable(model, z[i = N], Bin )
@objective(model, Max, sum((p[i] - c[i])*x[i] for i ∈ N) - duty*y )   # Subtract duty
@constraint(model, sum(c[i]*x[i] for i ∈ N) + duty*y <= 120 )         # Add duty
@constraint(model, sum(x[i] for i ∈ N) <= 30 )
@constraint(model, [i ∈ N], y >= x[i] )                  # Max value constraint
@constraint(model, [i ∈ N], y <= x[i] + U*(1 - z[i]))    # Max value constraint
@constraint(model, sum(z[i] for i ∈ N) == 1)             # Max value constraint
optimize!(model)
df.Purchase_Quantity = value.(x)
println(" \nTotal Profit: ", objective_value(model), ", Max Quantity: ", value(y),
", Purchase Cost: ", sum(value.(x).*c), ", Import Duty: ", duty*value(y))
df

 
Total Profit: 216.29999999999995, Max Quantity: 9.300000000000004, Purchase Cost: 101.4, Import Duty: 18.60000000000001

5 rows × 5 columns

	Item	Max_Order	Sale_Price	Purchase_Price	Purchase_Quantity
	String	Int64	Int64	Int64	Float64
1	Coffee	40	6	2	9.3
2	Peppers	10	15	6	9.3
3	Ginger	2	8	1	2.0
4	Tea	5	25	5	5.0
5	Candy	15	4	2	0.0

4. Fixed Costs

Instead of a single unit cost, often, the cost $C(x)$ to purchase $x$ units of an item is split between a cost per unit $c$ and a single fixed cost $k$ that is only incurred if the item is purchased:

$\quad C(x) = \begin{cases} 0, & x = 0 \\ k + cx, & x > 0 \end{cases} $.

In the MIP formulation, a binary variable $y_i$ is included in the objective function to account for the fixed cost, $k_i y_i + c_i x_i$, and is used in a constraint to switch $x_i$ between 0 and its upper bound $u_i$:

$\quad x_i \le u_i y_i $

Ex 4: Arbitrage Opportunity with Fixed Costs

Continuing with Ex 2 from LP 3, assume that there is an addition fixed price associtated with the purchase of each item:

using DataFrames
df = DataFrame(Item = ["Coffee", "Peppers", "Ginger", "Tea", "Candy"], 
    Max_Order = [40, 10, 2, 5, 15], Sale_Price = [6, 15, 8, 25, 4], 
    Unit_Price = [2, 6, 1, 5, 2], Fixed_Price = [15, 6, 4, 10, 1])

5 rows × 5 columns

	Item	Max_Order	Sale_Price	Unit_Price	Fixed_Price
	String	Int64	Int64	Int64	Int64
1	Coffee	40	6	2	15
2	Peppers	10	15	6	6
3	Ginger	2	8	1	4
4	Tea	5	25	5	10
5	Candy	15	4	2	1

using JuMP, GLPK
u,p,c,k = df.Max_Order, df.Sale_Price, df.Unit_Price, df.Fixed_Price
N = 1:length(p)
model = Model(GLPK.Optimizer)
@variable(model, 0 <= x[i = N] <= u[i] )
@variable(model, y[i = N], Bin)
@objective(model, Max, sum((p[i] - c[i])*x[i] - k[i]*y[i] for i ∈ N) )   # Fixed price subtracted
@constraint(model, sum(c[i]*x[i] + k[i]*y[i] for i ∈ N) <= 120 )         # Fixed price added
@constraint(model, sum(x[i] for i ∈ N) <= 30 )
@constraint(model, [i ∈ N], x[i] <= u[i]*y[i])                           # Switch UB on/off
optimize!(model)
df.Purchase_Quantity = value.(x)
println(" \nTotal Profit: ", objective_value(model), ", Total Unit Price: ", 
    sum(value.(x).*c), ", Total Fixed Price: ", sum(k.*value.(y)))
df

 
Total Profit: 195.0, Total Unit Price: 99.0, Total Fixed Price: 21.0

5 rows × 6 columns

	Item	Max_Order	Sale_Price	Unit_Price	Fixed_Price	Purchase_Quantity
	String	Int64	Int64	Int64	Int64	Float64
1	Coffee	40	6	2	15	0.0
2	Peppers	10	15	6	6	10.0
3	Ginger	2	8	1	4	2.0
4	Tea	5	25	5	10	5.0
5	Candy	15	4	2	1	6.0