Integer Programming

291. Integer Programming

291.1. IP (Integer Programming)

291.2. Selection and Logical Relations on Binary Variables $𝑥_{𝑖} \in {0, 1}$

291.2.1. Cardinality Constraints

Given a subset $𝑆 \subseteq {1, \dots, 𝑛}$ :

At least $𝑘$ of the items in $𝑆$

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 𝑘

Example

We want to select at least 2 of items 1, 2, 3

𝑥_{1} + 𝑥_{2} + 𝑥_{3} \geq 2

At most $𝑘$ of the items in $𝑆$

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \leq 𝑘

Example

We want to select at most 2 of items 1, 2, 3

𝑥_{1} + 𝑥_{2} + 𝑥_{3} \leq 2

Exactly $𝑘$ of the items in $𝑆$

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} = 𝑘

Example

We want to select exactly 2 of items 1, 2, 3

𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 2

291.2.2. Logical OR

Given a subset $𝑆 \subseteq {1, \dots, 𝑛}$ :

At least 1 item in $𝑆$

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 1

Example

Select item 1 or item 2, or both

𝑥_{1} + 𝑥_{2} \geq 1

291.2.3. Conditional Selection: “If X, then Y”

(Implication Constraints)

If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} = 1$

𝑥_{𝑎} \leq 𝑥_{𝑏}

Example

If item 1 is selected, then item 2 must also be selected

𝑥_{1} \leq 𝑥_{2}

$𝑥_{𝑎}$	$𝑥_{𝑏}$	Valid?
0	0	✅
0	1	✅
1	0	✅
1	1	❌

If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} = 0$

𝑥_{𝑎} + 𝑥_{𝑏} \leq 1

Example

If you choose project A, then you cannot choose project B (mutually exclusive).

$𝑥_{𝑎}$	$𝑥_{𝑏}$	Valid?
0	0	✅
0	1	✅
1	0	✅
1	1	❌

If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} + 𝑥_{𝑐} \leq 0$ (generalized)

𝑥_{𝑏} + 𝑥_{𝑐} \leq 𝑀 (1 - 𝑥_{𝑎})

Example

For binary variables $𝑀 = 2$ works

If you choose project A, then you must not choose either project B or C.

$𝑥_{𝑎}$	$𝑥_{𝑏}$	$𝑥_{𝑐}$	Valid?
1	0	0	✅
1	1	0	❌
1	1	1	❌
0	1	1	✅
0	0	1	✅

291.2.4. Conditional OR: “If not X, then select Y and Z”

If $𝑥_{𝑗} = 0$ , then at least $𝑘$ items in $𝑆$ must be selected (generalized)

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 𝑘 (1 - 𝑥_{𝑗})

Example

If you do not choose item 1, then you must choose both item 2 and item

If $𝑥_{1} = 0$ , then $𝑥_{2} = 𝑥_{3} = 1$

𝑥_{2} + 𝑥_{3} \geq 2 (1 - 𝑥_{1})

$𝑥_{1}$	$𝑥_{2}$	$𝑥_{3}$	LHS	RHS	Valid?
0	1	1	2	2	✅
0	1	0	1	2	❌
0	0	0	0	2	❌
1	0	0	0	0	✅
1	1	0	1	0	✅
1	1	1	2	0	✅

291.2.5. XOR / Exclusive Conditions

Exactly one item in a set $𝑆$

\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} = 1

Select one or the other but not both (i.e., $𝑥_{𝑖} \oplus 𝑥_{𝑘}$ )

𝑥_{𝑎} + 𝑥_{𝑏} = 1

Example

You can select item 1 or item 2, but not both

$𝑥_{1}$	$𝑥_{2}$	Sum	Valid?
0	1	1	✅
1	0	1	✅
1	1	2	❌
0	0	0	❌

291.3. Constraint Activation and Relaxation via Binary Indicators $𝑧_{𝑖} \in {1, 0}$

291.3.1. Base Case: At Least One of Two Constraints Satisfied

You are given 2 constraints

\begin{matrix} 𝑔_{1} (𝑥) \leq 𝑏_{1} \\ 𝑔_{2} (𝑥) \leq 𝑏_{2} \end{matrix}

We want at least one of these two constraints to be satisfied.

Binary Indicator Variables

Define:

𝑧_{𝑖} = {\begin{cases} 1 if 𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖} is enforced \\ 0 if 𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖} may be violated \end{cases} for 𝑖 = 1, 2

Let $𝑀_{1}$ and $𝑀_{2}$ be upper bounds on how much each constraint’s LHS $𝑔_{𝑖 (𝑥)}$ can exceed $𝑏_{𝑖}$ :

𝑀_{𝑖} \geq max_{𝑥} (𝑔_{𝑖 (𝑥)} - 𝑏_{𝑖})

Big-M Reformulation

We relax each constraint as follows:

\begin{matrix} 𝑔_{1} (𝑥) - 𝑏_{1} \leq 𝑀_{1} (1 - 𝑧_{1}) \\ 𝑔_{2} (𝑥) - 𝑏_{2} \leq 𝑀_{2} (1 - 𝑧_{2}) \end{matrix}

When $𝑧_{𝑖} = 1$ , the original constraint is enforced

When $𝑧_{𝑖} = 0$ , the original constraint can be violated by up to $𝑀_{𝑖}$

At Least One Constraint Enforced

We require:

𝑧_{1} + 𝑧_{2} \geq 1

291.3.2. General Formulation for $𝑚$ Constraints with At Least $𝑘$ Satisfied

Introduce a binary variable $𝑧_{𝑖} \in {0, 1}$ for each constraint $𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖}$ , where:

$𝑧_{𝑖} = 1$ : the constraint is enforced (i.e., $𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖}$ )
$𝑧_{𝑖} = 0$ : the constraint may be violated

Use “big-M” constraint to relax $𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖}$ when $𝑧_{𝑖} = 0$ , like:

𝑔_{𝑖 (𝑥)} - 𝑏_{𝑖} \leq 𝑀_{𝑖} (1 - 𝑧_{𝑖}), \forall 𝑖 = 1, \dots, 𝑚

Where $𝑀_{𝑖} \geq {max}_{𝑥} (𝑔_{𝑖 (𝑥)} - 𝑏_{𝑖})$

Impose a condition that at least $𝑘$ of the $𝑚$ constraints must be satisfied:

\sum_{𝑖 = 1}^{𝑚} 𝑧_{𝑖} \geq 𝑘

291.4. Fixed Charge Constraints (Setup Costs)

$𝑛$ : Number of factories
$𝐾_{𝑖}$ : Capacity of factory $𝑖$
$𝐶_{𝑖}$ : Unit production cost at factory $𝑖$
$𝑆_{𝑖}$ : Fixed setup cost for factory $𝑖$
$𝐷$ : Total Demand

Decision Variables

$𝑥_{𝑖}$ : production quantity at factory $𝑖$ , $𝑖 = 1, \dots, 𝑛$
$𝑦_{𝑖}$ : Binary variable indicating whether factory $𝑖$ is used

𝑦_{𝑖} = {\begin{cases} 1 if factory 𝑖 is used (i.e., 𝑥_{𝑖} > 0) \\ 0 if factory 𝑖 is not used (i.e, 𝑥_{𝑖} = 0) \end{cases}

Objective Function

min \underset{Production Cost}{\underset{⏟}{\sum_{𝑖 = 1}^{𝑛} 𝐶_{𝑖} 𝑥_{𝑖}}} + \underset{Setup Cost}{\underset{⏟}{\sum_{𝑖 = 1}^{𝑛} 𝑆_{𝑖} 𝑦_{𝑖}}}

Capacity Constraints

𝑥_{𝑖} \leq 𝐾_{𝑖} \forall 𝑖 = 1, \dots, 𝑛

Demand Fullfilment

\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} \geq 𝐷

Logical Linking of $𝑥_{𝑖}$ and $𝑦_{𝑖}$

To ensure $𝑦_{𝑖} = 1$ if any production occurs at factory $𝑖$ :

𝑥_{𝑖} \leq 𝐾_{𝑖} 𝑦_{𝑖} \forall 𝑖 = 1, \dots, 𝑛

If $𝑥_{𝑖} > 0$ , this forces $𝑦_{𝑖} = 1$
If $𝑥_{𝑖} = 0$ , $𝑦_{𝑖}$ can be 0 or 1 (but to minimize cost, $𝑦_{𝑖}$ will be 0)

Binary & Non-negative Constraints

𝑦_{𝑖} \in {0, 1}, 𝑥_{𝑖} \geq 0 \forall 𝑖 = 1, \dots, 𝑛

General Form (Big-M Formulation)

𝑥 \leq 𝑀 𝑦

Where $𝑀$ must be set to the upper bound of $𝑥$

291.5. Facility Location

Problem	Definition
Set Covering	Select the minimum number of facilities such that every demand point is within a specified coverage distance of at least one facility
Maximum Covering	Select a fixed number of facilities to maximize the number of demand points covered within a specified distance
Fixed Charge Location	Determine which facilities to open and how to assign demand to them to minimize the total cost

291.5.1. Set Covering Problem

Question: How to allocate as few facilities as possible to cover all demand nodes?

$𝐼$ : Set of demand nodes
$𝐽$ : Set of location nodes
$𝑑_{𝑖 𝑗} > 0$ : Distance between demand node $𝑖 \in 𝐼$ and location node $𝑗 \in 𝐽$
$𝑠$ : Maximum allowable distance (a facility at $𝑗$ can cover demand node $𝑖$ if $𝑑_{𝑖 𝑗} < 𝑠$ )
Demand $𝑖$ is “covered” by location $𝑗$ if $𝑑_{𝑖 𝑗} < 𝑠$
$𝑤_{𝑗} > 0$ : Cost of building facility at location $𝑗$ (usually set to $𝑤_{𝑗} = 1$ for minimizing number of facilities, but can reflect other costs)
$𝑎_{𝑖 𝑗} = {\begin{cases} 1 if 𝑑_{𝑖 𝑗} < 𝑠 \\ 0 otherwise \end{cases}$ : Indicator of whether location $𝑗$ can cover demand $𝑖$
$𝑥_{𝑗} = {\begin{cases} 1 if facility is built at location 𝑗 \\ 0 otherwise \end{cases}$

Complete Formulation

\begin{aligned} min & \sum_{𝑗 \in 𝐽} 𝑤_{𝑗} 𝑥_{𝑗} \\ 𝑠 . 𝑡 . & \sum_{𝑗 \in 𝐽} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} \geq 1 & \forall 𝑖 \in 𝐼 \\ 𝑥_{𝑗} \in {0, 1} & \forall 𝑗 \in 𝐽 \end{aligned}

291.5.2. Maximum Covering Problem

Question: How to allocate at most $𝑝$ facilities to cover as many demand nodes as possible?

$𝐼$ : Set of demand nodes
$𝐽$ : Set of location nodes
$𝑑_{𝑖 𝑗} > 0$ : Distance between demand node $𝑖 \in 𝐼$ and location node $𝑗 \in 𝐽$
$𝑝 \in ℕ$ : maximum number of facilities
$𝑤_{𝑗} > 0$ : Cost of building facility at location $𝑗$ (usually set to $𝑤_{𝑗} = 1$ for minimizing number of facilities, but can reflect other costs)
$𝑥_{𝑗} = {\begin{cases} 1 if facility is built at location 𝑗 \\ 0 otherwise \end{cases}$
$𝑎_{𝑖 𝑗} = {\begin{cases} 1 if 𝑑_{𝑖 𝑗} < 𝑠 \\ 0 otherwise \end{cases}$ : Indicator of whether location $𝑗$ can cover demand $𝑖$
$𝑦_{𝑖} = {\begin{cases} 1 if demand 𝑖 \in 𝐼 is covered by any facility \\ 0 otherwise \end{cases}$

Complete Formulation

\begin{aligned} min & \sum_{𝑖 \in 𝐼} 𝑤_{𝑖} 𝑦_{𝑖} \\ 𝑠 . 𝑡 . & \sum_{𝑗 \in 𝐽} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} \geq 𝑦_{𝑖} & \forall 𝑖 \in 𝐼 \\ \sum_{𝑗 \in 𝐽} 𝑥_{𝑗} \leq 𝑝 & \forall 𝑗 \in 𝐽 \\ 𝑥_{𝑗} \in {0, 1} & \forall 𝑗 \in 𝐽 \\ 𝑦_{𝑖} \in {0, 1} & \forall 𝑖 \in 𝐼 \end{aligned}

Fixed Charge Location Problems

Question: How to allocate some facilities to minimize the total shipping and construction costs?

Uncapacitated Facility Location Problem (UFL)

$𝐼$ : Set of demand nodes
$𝐽$ : Set of location nodes
$ℎ_{𝑖} > 0$ : Demand size at demand node $𝑖$
$𝑑_{𝑖 𝑗}$ : Unit shipping cost from location node $𝑗$ to demand node $𝑖$
$𝑓_{𝑗} > 0$ : Fixed construction cost at location $𝑗$
$𝑥_{𝑗} = {\begin{cases} 1 if facility is built at location 𝑗 \\ 0 otherwise \end{cases}$
$𝑦_{𝑖 𝑗} = {\begin{cases} 1 if demand 𝑖 \in 𝐼 is served by facility at location 𝑗 \in 𝐽 \\ 0 otherwise \end{cases}$

Complete Formulation

\begin{aligned} min & \underset{Shipping Costs}{\underset{⏟}{\sum_{𝑖 \in 𝐼} \sum_{𝑗 \in 𝐽} ℎ_{𝑖} 𝑑_{𝑖 𝑗} 𝑦_{𝑖 𝑗}}} + \underset{Fixed Costs}{\underset{⏟}{\sum_{𝑗 \in 𝐽} 𝑓_{𝑗} 𝑥_{𝑗}}} \\ 𝑠 . 𝑡 . & 𝑦_{𝑖 𝑗} \leq 𝑥_{𝑗} \forall 𝑖 \in 𝐼, 𝑗 \in 𝐽 \\ \sum_{𝑗 \in 𝐽} 𝑦_{𝑖 𝑗} = 1 \forall 𝑖 \in 𝐼 \\ 𝑥_{𝑗} \in {0, 1} \forall 𝑗 \in 𝐽 \\ 𝑦_{𝑖 𝑗} \in {0, 1} \forall 𝑖 \in 𝐼 \end{aligned}

Capacitated Facility Location Problem (CFL)

If locations have a capacity, we may add constraint

\sum_{𝑖 \in 𝐼} ℎ_{𝑖} 𝑦_{𝑖 𝑗} \leq 𝐾_{𝑗} \forall 𝑗 \in 𝐽

Where:

$𝐾_{𝑗} > 0$ : Capacity of location $𝑗$

Example

\begin{aligned} min & \underset{Fixed Costs}{\underset{⏟}{\sum_{𝑗 = 1}^{5} 𝑓_{𝑗} 𝑥_{𝑗}}} + \underset{Shipping Costs}{\underset{⏟}{\sum_{𝑖 = 1}^{5} \sum_{𝑗 = 1}^{5} 𝑐_{𝑖 𝑗} 𝑦_{𝑖 𝑗}}} \\ 𝑠 . 𝑡 . & \sum_{𝑖 = 1}^{5} 𝑦_{𝑖 𝑗} \leq 𝐾_{𝑗} 𝑥_{𝑗} & \forall & 𝑗 = 1, \dots, 5 & (Capacity Constraint) \\ \sum_{𝑗 = 1}^{5} 𝑦_{𝑖 𝑗} \geq 𝐷_{𝑖} & \forall & 𝑖 = 1, \dots, 5 & (Demand Constraint) \\ 𝑥_{𝑗} \in {0, 1} & \forall & 𝑗 = 1, \dots, 5 & (Binary Constraint) \\ 𝑦_{𝑖 𝑗} \geq 0 & \forall & 𝑖 = 1, \dots, 5, 𝑗 = 1, \dots, 5 & (Positivity Constraint) \end{aligned}

Parameters

$𝑓_{𝑗}$ : weekly operating cost of distribution center $𝑗$
$𝑐_{𝑖 𝑗}$ : shipping cost per book from distribution center $𝑗$ to region $𝑖$
$𝐾_{𝑗}$ : capacity of distribution center $𝑗$
$𝐷_{𝑖}$ : book demand of region $𝑖$

Decision variable

$𝑥_{𝑖 𝑗}$ : binary variable

𝑥_{𝑖 𝑗} = {\begin{cases} 1 if a distribution center is build at location 𝑗 \\ 0 otherwise \end{cases}

$𝑦_{𝑖 𝑗}$ : number of books shipped from distribution center $𝑗$ to region $𝑖$

Supply

	WA	NV	NE	PA	FL	Demand ( $𝐷_{𝑖}$ )
NorthWest	$𝑦_{11}$	$𝑦_{12}$	$𝑦_{13}$	$𝑦_{14}$	$𝑦_{15}$	8000
SouthWest	$𝑦_{21}$	$𝑦_{22}$	$𝑦_{23}$	$𝑦_{24}$	$𝑦_{25}$	12000
MidWest	$𝑦_{31}$	$𝑦_{32}$	$𝑦_{33}$	$𝑦_{34}$	$𝑦_{35}$	9000
SouthEast	$𝑦_{41}$	$𝑦_{42}$	$𝑦_{43}$	$𝑦_{44}$	$𝑦_{45}$	14000
NorthEast	$𝑦_{51}$	$𝑦_{52}$	$𝑦_{53}$	$𝑦_{54}$	$𝑦_{55}$	17000

Fixed Costs ( $𝑓_{𝑗}$ ) and Capacity ( $𝐾_{𝑗}$ )

	$𝑥_{1}$	$𝑥_{2}$	$𝑥_{3}$	$𝑥_{4}$	$𝑥_{5}$
Operation Cost ( $𝑓_{𝑖}$ )	40000	30000	25000	40000	30000
Capacity ( $𝐾_{𝑖}$ )	20000	20000	15000	25000	15000

Shipping Cost ( $𝑐_{𝑗}$ )

	WA	NV	NE	PA	FL
NorthWest	2.4	3.25	4.05	5.25	6.95
SouthWest	3.5	2.3	3.25	6.05	5.85
MidWest	4.8	3.4	2.85	4.3	4.8
SouthEast	6.8	5.25	4.3	3.25	2.1
NorthEast	5.75	6	4.75	2.75	3.5

Binary Decision Variable

WA	$𝑥_{1}$
NV	$𝑥_{2}$
NE	$𝑥_{3}$
PA	$𝑥_{4}$
FL	$𝑥_{5}$

model.py

model.py

from pyomo.environ import *
from pyomo.dataportal import DataPortal

model = AbstractModel()

# Sets
model.I = Set(doc='Regions (demand points)')
model.J = Set(doc='Candidate distribution centers')

# Parameters
model.D = Param(model.I, within=NonNegativeReals, doc='Demand at region i')
model.K = Param(model.J, within=NonNegativeReals, doc='Capacity at distribution center j')
model.f = Param(model.J, within=NonNegativeReals, doc='Fixed cost to open center j')
model.c = Param(model.I, model.J, within=NonNegativeReals, doc='Shipping cost from j to i')

# Decision Variables
model.x = Var(model.J, within=Binary, doc='1 if center j is opened')
model.y = Var(model.I, model.J, within=NonNegativeReals, doc='Units shipped from j to i')

# Objective Function: Minimize total cost
def total_cost_rule(model):
    fixed = sum(model.f[j] * model.x[j] for j in model.J)
    shipping = sum(model.c[i, j] * model.y[i, j] for i in model.I for j in model.J)
    return fixed + shipping
model.TotalCost = Objective(rule=total_cost_rule, sense=minimize)

# Constraints

# Capacity Constraint: Total shipped from center ≤ capacity if opened
def capacity_rule(model, j):
    return sum(model.y[i, j] for i in model.I) <= model.K[j] * model.x[j]
model.CapacityConstraint = Constraint(model.J, rule=capacity_rule)

# Demand Constraint: Total received by region ≥ its demand
def demand_rule(model, i):
    return sum(model.y[i, j] for j in model.J) >= model.D[i]
model.DemandConstraint = Constraint(model.I, rule=demand_rule)

# Load data from .dat file
data = DataPortal()
data.load(filename='data.dat', model=model)

# Create an instance of the model
instance = model.create_instance(data)

# Create solver
solver = SolverFactory('glpk')
solver.options['tmlim'] = 60

# Solve with solver timeout (optional)
results = solver.solve(instance, tee=True)

# Display results
instance.display()

data.dat

set I := NorthWest SouthWest MidWest SouthEast NorthEast;
set J := WA NV NE PA FL;

param: D :=
NorthWest 8000
SouthWest 12000
MidWest 9000
SouthEast 14000
NorthEast 17000;

param: f :=
WA 40000
NV 30000
NE 25000
PA 40000
FL 30000;

param: K :=
WA 20000
NV 20000
NE 15000
PA 25000
FL 15000;

param c:
        WA     NV     NE     PA     FL :=
NorthWest 2.4   3.25   4.05   5.25   6.95
SouthWest 3.5   2.3    3.25   6.05   5.85
MidWest   4.8   3.4    2.85   4.3    4.8
SouthEast 6.8   5.25   4.3    3.25   2.1
NorthEast 5.75  6      4.75   2.75   3.5 ;

Output:

Variables:
x : 1 if center j is opened
    Size=5, Index=J
    Key : Lower : Value : Upper : Fixed : Stale : Domain
     FL :     0 :   1.0 :     1 : False : False : Binary
     NE :     0 :   0.0 :     1 : False : False : Binary
     NV :     0 :   1.0 :     1 : False : False : Binary
     PA :     0 :   1.0 :     1 : False : False : Binary
     WA :     0 :   0.0 :     1 : False : False : Binary
y : Units shipped from j to i
    Size=25, Index=I*J
    Key                 : Lower : Value   : Upper : Fixed : Stale : Domain
      ('MidWest', 'FL') :     0 :  1000.0 :  None : False : False : NonNegativeReals
      ('MidWest', 'NE') :     0 :     0.0 :  None : False : False : NonNegativeReals
      ('MidWest', 'NV') :     0 :     0.0 :  None : False : False : NonNegativeReals
      ('MidWest', 'PA') :     0 :  8000.0 :  None : False : False : NonNegativeReals
      ('MidWest', 'WA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthEast', 'FL') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthEast', 'NE') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthEast', 'NV') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthEast', 'PA') :     0 : 17000.0 :  None : False : False : NonNegativeReals
    ('NorthEast', 'WA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthWest', 'FL') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthWest', 'NE') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthWest', 'NV') :     0 :  8000.0 :  None : False : False : NonNegativeReals
    ('NorthWest', 'PA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('NorthWest', 'WA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthEast', 'FL') :     0 : 14000.0 :  None : False : False : NonNegativeReals
    ('SouthEast', 'NE') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthEast', 'NV') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthEast', 'PA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthEast', 'WA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthWest', 'FL') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthWest', 'NE') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthWest', 'NV') :     0 : 12000.0 :  None : False : False : NonNegativeReals
    ('SouthWest', 'PA') :     0 :     0.0 :  None : False : False : NonNegativeReals
    ('SouthWest', 'WA') :     0 :     0.0 :  None : False : False : NonNegativeReals

Objectives:
  TotalCost : Size=1, Index=None, Active=True
      Key  : Active : Value
      None :   True : 268950.0

Constraints:
  CapacityConstraint : Size=5
      Key : Lower : Body : Upper
      FL :  None :  0.0 :   0.0
      NE :  None :  0.0 :   0.0
      NV :  None :  0.0 :   0.0
      PA :  None :  0.0 :   0.0
      WA :  None :  0.0 :   0.0
  DemandConstraint : Size=5
      Key       : Lower   : Body    : Upper
        MidWest :  9000.0 :  9000.0 :  None
      NorthEast : 17000.0 : 17000.0 :  None
      NorthWest :  8000.0 :  8000.0 :  None
      SouthEast : 14000.0 : 14000.0 :  None
      SouthWest : 12000.0 : 12000.0 :  None

291.6. Machine Scheduling

	Problem	Definition
One Machine	Single Machine Serial Production	Scheduling jobs one after another on a single machine
Multiple Machines	Multiple Parallel Machines	Scheduling jobs on two or more identical machines working in parallel; each job can be assigned to any machine
	Flow Shop	All jobs follow the same sequence of machines; each job visits every machine in the same order
	Job Shop	Each job has its own specific sequence of machines to follow

Job Splitting
- Non-premptive problems
Once a job starts processing on a machine, it must continue without interruption until completion
- Preemptive problems
A job can be interrupted and resumed later, possibly on a different machine, without losing progress
Performance Metrics
- Makespan: The sum of completion times of all jobs, possibly weighted by job importance
- (Weighted) total completion time: The sum of completion times of all jobs, possibly weighted by job importance (measures overall throughput)
- (Weighted) number of delayed jobs: The total number of jobs completed after they are due, possibly weighted by job priority
- (Weighted) total lateness: The sum of differences between each job’s completion time and due date (can be negative or positive), possibly weighted
- (Weighted) total tardiness: The sum of positive delays (i.e., lateness when a job finishes after its due date), possibly weighted. Negative values (early completions) are treated as zero.
- …

291.6.1. Single Machine Serial Production

Notation

$𝑛$ : Total number of jobs
$𝐽 = {1, 2, \dots, 𝑛}$ : Set of jobs
$𝑗 \in 𝐽$ : A job
$𝑝_{𝑗}$ : processing time of job $𝑗$
$𝑥_{𝑗}$ : completion time of job $𝑗$
$𝑧_{𝑖 𝑗} \in {0, 1}$ : Binary variable

𝑧_{𝑖 𝑗} = {\begin{cases} 1 if job 𝑗 is before job 𝑖 \\ 0 otherwise \end{cases}

Job Order Constraints

We must ensure that either job $𝑖$ comes before job $𝑗$ or vice versa, but not both

If job $𝑖$ is before job $𝑗$ ( $𝑧_{𝑖 𝑗} = 0$ )

𝑥_{𝑗} \geq 𝑥_{𝑖} + 𝑝_{𝑗}

If job $𝑗$ is before job $𝑖$ ( $𝑧_{𝑖 𝑗} = 1$ ):

𝑥_{𝑖} \geq 𝑥_{𝑗} + 𝑝_{𝑖}

These two cases can be rewritten using a big- $𝑀$ formulation:

\begin{aligned} 𝑥_{𝑖} + 𝑝_{𝑗} - 𝑥_{𝑗} & \leq 𝑀 𝑧_{𝑖 𝑗} \\ 𝑥_{𝑗} + 𝑝_{𝑖} - 𝑥_{𝑖} & \leq 𝑀 (1 - 𝑧_{𝑖 𝑗}) \end{aligned}

Where:

$𝑀 = \sum_{𝑗 \in 𝐽} 𝑝_{𝑗}$

Complete Formulation

\begin{aligned} min & \sum_{𝑗 \in 𝐽} 𝑥_{𝑗} \\ 𝑠 . 𝑡 . & 𝑥_{𝑖} + 𝑝_{𝑗} - 𝑥_{𝑗} \leq 𝑀 𝑧_{𝑖 𝑗} & \forall & 𝑖 \in 𝐽, 𝑗 \in 𝐽, 𝑖 < 𝑗 \\ 𝑥_{𝑗} + 𝑝_{𝑖} - 𝑥_{𝑖} \leq 𝑀 (1 - 𝑧_{𝑖 𝑗}) & \forall & 𝑖 \in 𝐽, 𝑗 \in 𝐽, 𝑖 < 𝑗 \\ 𝑥_{𝑗} \geq 𝑝_{𝑗} & \forall & 𝑗 \in 𝐽 \\ 𝑥_{𝑗} \geq 0 & \forall & 𝑗 \in 𝐽 \\ 𝑧_{𝑖 𝑗} \in {0, 1} & \forall & 𝑖 \in 𝐽, 𝑗 \in 𝐽, 𝑖 < 𝑗 \end{aligned}

Interpretation

If jobs are run in order $1, 2, \dots, 𝑛$ , the completion times are:

\begin{aligned} 𝑥_{1} & = 𝑝_{1} \\ 𝑥_{2} & = 𝑝_{1} + 𝑝_{2} \\ 𝑥_{3} & = 𝑝_{1} + 𝑝_{2} + 𝑝_{3} \\ ⋮ \\ 𝑥_{𝑛} & = \sum_{𝑖 = 1}^{𝑛} 𝑝_{𝑖} \end{aligned}

So, the completion time of a job depends on the sum of processing times of all jobs before it in the schedule

Optional: Release Times

If jobs have release times $𝑅_{𝑗}$ , meaning each job $𝑗$ cannot start before $𝑅_{𝑗}$ , then we add:

𝑥_{𝑗} \geq 𝑅_{𝑗} + 𝑝_{𝑗} \forall 𝑗 \in 𝐽

291.6.2. Multiple Parallel Machines

We aim to assign jobs to machines such that:

Each job is assigned to exactly one machine.
A job can be processed on any machine.
The objective is to minimize the makespan, which is the time when the last machine finishes processing.

Notation

$𝐽 = {1, 2, \dots, 𝑛}$ : set of jobs
$𝐼 = {1, 2, \dots, 𝑚}$ : set of machines
$𝑝_{𝑗}$ : processing time of job $𝑗 \in 𝐽$
$𝑥_{𝑖 𝑗}$ : a binary variable that indicates whether job $𝑗$ is assigned to machine $𝑖$ :

𝑥_{𝑖 𝑗} = {\begin{cases} 1 if job 𝑗 is assigned to machine 𝑖 \\ 0 otherwise \end{cases}

The completion time of machine $𝑖$ is the total processing time of all jobs assigned to it

𝐶_{𝑖} = \sum_{𝑗 \in 𝐽} 𝑝_{𝑗} 𝑥_{𝑖 𝑗}

The makespan $𝑤$ is the maximum completion time across all machines:

𝑤 \geq \sum_{𝑗 \in 𝐽} 𝑝_{𝑗} 𝑥_{𝑖 𝑗} \forall 𝑖 \in 𝐼

Objective

Minimize makespan $𝑤$

Complete Formulation

\begin{aligned} min & 𝑤 \\ 𝑠 . 𝑡 . & \sum_{𝑗 \in 𝐽} 𝑝_{𝑗} 𝑥_{𝑖 𝑗} \leq 𝑤 & \forall & 𝑖 \in 𝐼 \\ \sum_{𝑖 \in 𝐼} 𝑥_{𝑖 𝑗} = 1 & \forall & 𝑗 \in 𝐽 \\ 𝑥_{𝑖 𝑗} \in {0, 1} & \forall & 𝑖 \in 𝐼, 𝑗 \in 𝐽 \end{aligned}

The first constraint ensures the makespan is at least as large as each machine’s workload
The second ensures each job is assigned to one and only one machine

model.py

from pyomo.environ import *

model = AbstractModel()

model.MACHINES = Set()
model.JOBS = Set()

model.p = Param(model.JOBS, within=PositiveReals)

model.x = Var(model.MACHINES, model.JOBS, domain=Binary)
model.w = Var(domain=NonNegativeReals)

def obj_rule(m):
    return m.w
model.Obj = Objective(rule=obj_rule, sense=minimize)

def job_assignment_rule(m, j):
    return sum(m.x[i, j] for i in m.MACHINES) == 1
model.JobAssignment = Constraint(model.JOBS, rule=job_assignment_rule)

def machine_completion_rule(m, i):
    return sum(m.p[j] * m.x[i, j] for j in m.JOBS) <= m.w
model.MachineCompletion = Constraint(model.MACHINES, rule=machine_completion_rule)

291.6.3. Flow Shop

291.6.4. Job Shop

291.7. Vehicle Routing

291.7.1. Traveling Salesperson

Let $𝐺 = (𝑉, 𝐸)$ be a directed complete graph
Let $𝑑_{𝑖 𝑗}$ be the distance (cost) from node $𝑖$ to $𝑗$
Let $𝑥_{𝑖 𝑗}$ be a binary decision variable:

𝑥_{𝑖 𝑗} = {\begin{cases} 1 if (𝑖, 𝑗) is selected \\ 0 otherwise \end{cases}

Objective

Minimize the total travel cost

min \sum_{(𝑖, 𝑗) \in 𝐸} 𝑑_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

Constraints

Flow Balancing

For node $𝑘 \in 𝑉$

One incoming edge:

\sum_{𝑖 \in 𝑉, 𝑖 \neq 𝑘} = 1

One outgoing edge:

\sum_{𝑗 \in 𝑉, 𝑗 \neq 𝑘} = 1

Subtours

a. Miller-Tucker-Zemlin (MTZ)

Let $𝑢_{𝑖} 𝑠$ : be the position of node $𝑖$ in the tour (e.g., $𝑢_{𝑖} = 𝑘$ if node $𝑖$ is the $𝑘$ th node to be passed on the tour)

\begin{aligned} 𝑢_{1} = 1 \\ 2 \leq 𝑢_{𝑖} \leq 𝑛 & \forall & 𝑖 \in 𝑉 \ {1} \\ 𝑢_{𝑖} - 𝑢_{𝑗} + 1 \leq (𝑛 - 1) (1 - 𝑥_{𝑖 𝑗}) & \forall & (𝑖, 𝑗) \in 𝐸, 𝑖 \neq 1, 𝑗 \neq 1 \end{aligned}

b. Subtour Elimination Constraint (SEC)

For every subset $𝑆 \subset 𝑉$ with $| 𝑆 | \geq 2$ :

\sum_{\begin{matrix} 𝑖 \in 𝑆, 𝑗 \in 𝑆 \\ 𝑖 \neq 𝑗 \end{matrix}} 𝑥_{𝑖 𝑗} \leq | 𝑆 | - 1 \forall 𝑆 \subset 𝑉, | 𝑆 | \geq 2

This ensures that no subset of nodes forms a closed tour independent of the main tour.

Complete Formulation

\begin{aligned} min & \sum_{(𝑖, 𝑗) \in 𝐸} 𝑑_{𝑖 𝑗} 𝑥_{𝑖 𝑗} \\ 𝑠 . 𝑡 . & \sum_{𝑖 \in 𝑉, 𝑖 \neq 𝑘} = 1 & \forall & 𝑘 \in 𝑉 \\ \sum_{𝑗 \in 𝑉, 𝑗 \neq 𝑘} = 1 & \forall & 𝑘 \in 𝑉 \\ 𝑥_{𝑖 𝑗} \in {0, 1} & \forall & (𝑖, 𝑗) \in 𝐸 \\ MTZ or SEC \end{aligned}

291. Integer Programming

291.1. IP (Integer Programming)

291.2. Selection and Logical Relations on Binary Variables 𝑥𝑖∈{0,1}

291.2.1. Cardinality Constraints

291.2.2. Logical OR

291.2.3. Conditional Selection: “If X, then Y”

291.2.4. Conditional OR: “If not X, then select Y and Z”

291.2.5. XOR / Exclusive Conditions

291.3. Constraint Activation and Relaxation via Binary Indicators 𝑧𝑖∈{1,0}

291.3.1. Base Case: At Least One of Two Constraints Satisfied

291.3.2. General Formulation for 𝑚 Constraints with At Least 𝑘 Satisfied

291.4. Fixed Charge Constraints (Setup Costs)

291.5. Facility Location

291.5.1. Set Covering Problem

291.5.2. Maximum Covering Problem

Output:

291.6. Machine Scheduling

291.6.1. Single Machine Serial Production

291.6.2. Multiple Parallel Machines

291.6.3. Flow Shop

291.6.4. Job Shop

291.7. Vehicle Routing

291.7.1. Traveling Salesperson

291.2. Selection and Logical Relations on Binary Variables $𝑥_{𝑖} \in {0, 1}$

291.3. Constraint Activation and Relaxation via Binary Indicators $𝑧_{𝑖} \in {1, 0}$

291.3.2. General Formulation for $𝑚$ Constraints with At Least $𝑘$ Satisfied