# 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
)  # 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.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.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.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