Production model using disjunctions

Production model using disjunctions#

# install dependencies and select solver
%pip install -q amplpy

SOLVER = "highs"

from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Disjunctions#

Disjunctions appear in applications where there is choice among discrete alternatives. Given two logical propositions \(\alpha\) and \(\beta\), the “or” disjunction is denoted by \(\vee\) and defined by the truth table

\(\alpha\)	\(\beta\)	\(\alpha \vee \beta\)
False	False	False
True	False	True
False	True	True
True	True	True

The “exclusive or” is denoted by \(\veebar\) and defined by the truth table

\(\alpha\)	\(\beta\)	\(\alpha \veebar \beta\)
False	False	False
True	False	True
False	True	True
True	True	False

This notebook shows how to express disjunctions in AMPL models using the Generalized Disjunctive Programming syntax for a simple production model.

Multi-product factory optimization#

A small production facility produces two products, \(X\) and \(Y\). With current technology \(\alpha\), the facility is subject to the following conditions and constraints:

Product \(X\) requires 1 hour of labor A, 2 hours of labor B, and 100€ of raw material. Product \(X\) sells for 270€ per unit. The daily demand is limited to 40 units.
Product \(Y\) requires 1 hour of labor A, 1 hour of labor B, and 90€ of raw material. Product \(Y\) sells for 210€ per unit with unlimited demand.
There are 80 hours per day of labor A available at a cost of 50€/hour.
There are 100 hours per day of labor B available at a cost of 40€/hour.

Using the given data we see that the net profit for each unit of \(X\) and \(Y\) is 40€ and 30€, respectively. The optimal product strategy is the solution to a linear optimization

\[\begin{split} \begin{align*} \max_{x, y \geq 0} \quad & \text{profit}\\ \text{s.t.} \quad & \text{profit} = 40 x + 30 y\\ & x \leq 40 & \text{(demand)}\\ & x + y \leq 80 & \text{(labor A)} \\ & 2 x + y \leq 100 & \text{(labor B)} \end{align*} \end{split}\]

%%writefile multi_product_factory.mod

# decision variables
var profit;
var production_x >= 0;
var production_y >= 0;

# profit objective
maximize maximize_profit: profit;
    
# constraints
s.t. profit_expr: profit == 40 * production_x + 30 * production_y;
s.t. demand: production_x <= 40;
s.t. laborA: production_x + production_y <= 80;
s.t. laborB: 2 * production_x + production_y <= 100;

Overwriting multi_product_factory.mod

m = AMPL()
m.read("multi_product_factory.mod")
m.option["solver"] = SOLVER
m.solve()

print(f"Profit = {m.var['profit'].value():.2f} €")
print(f"Production X = {m.var['production_x'].value()}")
print(f"Production Y = {m.var['production_y'].value()}")

HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 2600
2 simplex iterations
0 barrier iterations
Profit = 2600.00 €
Production X = 20.0
Production Y = 60.0

Now suppose a new technology \(\beta\) is available that affects that lowers the cost of product \(X\). With the new technology, only 1.5 hours of labor B is required per unit of \(X\).

The net profit for unit of product \(X\) with technology \(\alpha\) is equal to \(270 - 100 - 50 - 2 \cdot 40 = 40\)€

The net profit for unit of product \(X\) with technology \(\beta\) is equal to \(270 - 100 - 50 - 1.5 \cdot 40 = 60\)€

The decision here is whether to use technology \(\alpha\) or \(\beta\). There are several commonly used techniques for embedding disjunctions into mixed-integer linear optimization problems. The “big-M” technique introduces a binary decision variable for every exclusive-or disjunction between two constraints.

MILO implementation#

We can formulate this problem as the following mixed-integer linear optimization (MILO) problem:

\[\begin{split} \begin{align*} \max_{x, y \geq 0, z \in \mathbb{B}} \quad & \text{profit}\\ \text{s.t.} \quad & x \leq 40 & \text{(demand)}\\ & x + y \leq 80 & \text{(labor A)} \\ & \text{profit} \leq 40x + 30y + M z \\ & \text{profit} \leq 60x + 30y + M (1 - z) \\ & 2 x + y \leq 100 + M z \\ & 1.5 x + y \leq 100 + M (1 - z). \end{align*} \end{split}\]

where the variable \(z \in \{ 0, 1\}\) “activates” the constraints related to the old or new technology, respectively, and \(M\) is a big enough number. The corresponding AMPL implementation is given by:

%%writefile multi_product_factory_milo.mod

# decision variables
var profit;
var production_x >= 0;
var production_y >= 0;
var z binary;
param M = 10000;

# profit objective
maximize maximize_profit: profit;

# constraints
s.t. profit_constr_1: profit <= 40 * production_x + 30 * production_y + M * z;
s.t. profit_constr_2: profit <= 60 * production_x + 30 * production_y + M * (1 - z);
s.t. demand: production_x <= 40;
s.t. laborA: production_x + production_y <= 80;
s.t. laborB_1: 2 * production_x + production_y <= 100 + M * z;
s.t. laborB_2: 1.5 * production_x + production_y <= 100 + M * (1 - z);

Overwriting multi_product_factory_milo.mod

m = AMPL()
m.read("multi_product_factory_milo.mod")
m.option["solver"] = SOLVER
m.solve()

print(f"Profit = {m.var['profit'].value():.2f} €")
print(f"Production X = {m.var['production_x'].value()}")
print(f"Production Y = {m.var['production_y'].value()}")

HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 3600
8 simplex iterations
1 branching nodes
Profit = 3600.00 €
Production X = 40.0
Production Y = 40.0

Disjunctive programming implementation#

Alternatively, we can formulate our problem using a disjunction, preserving the logical structure, as follows:

\[\begin{split} \begin{align*} \max_{x, y \geq 0} \quad & \text{profit}\\ \text{s.t.} \quad & x \leq 40 & \text{(demand)}\\ & x + y \leq 80 & \text{(labor A)} \\ & \begin{bmatrix} \text{profit} = 40x + 30y\\ 2 x + y \leq 100 \end{bmatrix} \veebar \begin{bmatrix} \text{profit} = 60x + 30y\\ 1.5 x + y \leq 100 \end{bmatrix} \end{align*} \end{split}\]

This formulation, if allowed by the software at hand, has the benefit that the software can smartly divide the solution of this problem into sub-possibilities depending on the disjunction. AMPL supports disjunctions, as illustrated in the following implementation:

%%writefile multi_product_factory_milo_disjunctive.mod

var profit >= -1000, <= 10000;
var x >= 0, <= 1000;
var y >= 0, <= 1000;

maximize maximize_profit: profit;

s.t. demand: x <= 40;
s.t. laborA: x + y <= 80;
s.t. technologies:
    ((profit == 40 * x + 30 * y and 2 * x + y <= 100)
    or
    (profit == 60 * x + 30 * y and 1.5 * x + y <= 100))
    and not
    ((profit == 40 * x + 30 * y and 2 * x + y <= 100)
    and
    (profit == 60 * x + 30 * y and 1.5 * x + y <= 100))
    ;

Overwriting multi_product_factory_milo_disjunctive.mod

m = AMPL()
m.read("multi_product_factory_milo_disjunctive.mod")
m.option["solver"] = SOLVER
m.solve()

print(f"Profit = {m.var['profit'].value():.2f} €")
print(f"x = {m.var['x'].value()}")
print(f"y = {m.var['y'].value()}")

HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 3600
12 simplex iterations
1 branching nodes
Profit = 3600.00 €
x = 40.0
y = 40.0