Integer Programming

288. Integer Programming

288.1. IP (Integer Programming)

288.2. Selection and Logical Relations on Binary Variables

288.2.1. Cardinality Constraints

Given a subset :

At least of the items in

Example

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

At most of the items in

Example

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

Exactly of the items in

Example

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

288.2.2. Logical OR

Given a subset :

At least 1 item in

Example

Select item 1 or item 2, or both

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

(Implication Constraints)

If , then

Example

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

		Valid?
0	0	✅
0	1	✅
1	0	✅
1	1	❌

If , then

Example

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

		Valid?
0	0	✅
0	1	✅
1	0	✅
1	1	❌

If , then (generalized)

Example

For binary variables 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	✅

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

If , then at least items in must be selected (generalized)

Example

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

If , then

			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	✅

288.2.5. XOR / Exclusive Conditions

Exactly one item in a set

Select one or the other but not both (i.e., )

Example

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

		Sum	Valid?
0	1	1	✅
1	0	1	✅
1	1	2	❌
0	0	0	❌

288.3. Constraint Activation and Relaxation via Binary Indicators

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

You are given 2 constraints

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

Binary Indicator Variables

Define:

Let and be upper bounds on how much each constraint’s LHS can exceed :

Big-M Reformulation

We relax each constraint as follows:

When , the original constraint is enforced

When , the original constraint can be violated by up to

At Least One Constraint Enforced

We require:

288.3.2. General Formulation for Constraints with At Least Satisfied

Introduce a binary variable for each constraint , where:

: the constraint is enforced (i.e., )
: the constraint may be violated

Use “big-M” constraint to relax when , like:

Where

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

288.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 ,
: Binary variable indicating whether factory is used

Objective Function

Capacity Constraints

Demand Fullfilment

Logical Linking of and

To ensure if any production occurs at factory :

If , this forces
If , can be 0 or 1 (but to minimize cost, will be 0)

Binary & Non-negative Constraints

General Form (Big-M Formulation)

Where must be set to the upper bound of

288.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

288.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
: Distance between demand node and location node
: Maximum allowable distance (a facility at can cover demand node if )
Demand is “covered” by location if
: Cost of building facility at location (usually set to for minimizing number of facilities, but can reflect other costs)
: Indicator of whether location can cover demand

Complete Formulation

288.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
: Distance between demand node and location node
: maximum number of facilities
: Cost of building facility at location (usually set to for minimizing number of facilities, but can reflect other costs)
: Indicator of whether location can cover demand

Complete Formulation

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
: Demand size at demand node
: Unit shipping cost from location node to demand node
: Fixed construction cost at location

Complete Formulation

Capacitated Facility Location Problem (CFL)

If locations have a capacity, we may add constraint

Where:

: Capacity of location

Example

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

: number of books shipped from distribution center to region

Supply

	WA	NV	NE	PA	FL	Demand ()
NorthWest						8000
SouthWest						12000
MidWest						9000
SouthEast						14000
NorthEast						17000

Fixed Costs () and Capacity ()


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
NV
NE
PA
FL

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

288.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.
- …

288.6.1. Single Machine Serial Production

Notation

: Total number of jobs
: Set of jobs
: A job
: processing time of job
: completion time of job
: Binary variable

Job Order Constraints

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

If job is before job ()

If job is before job ():

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

Where:

Complete Formulation

Interpretation

If jobs are run in order , the completion times are:

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:

288.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

: set of jobs
: set of machines
: processing time of job
: a binary variable that indicates whether job is assigned to machine :

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

The makespan is the maximum completion time across all machines:

Objective

Minimize makespan

Complete Formulation

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)

288.6.3. Flow Shop

288.6.4. Job Shop

288.7. Vehicle Routing

288.7.1. Traveling Salesperson

Let be a directed complete graph
Let be the distance (cost) from node to
Let be a binary decision variable:

Objective

Minimize the total travel cost

Constraints

Flow Balancing

For node

One incoming edge:

One outgoing edge:

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)

b. Subtour Elimination Constraint (SEC)

For every subset with :

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

Complete Formulation