AERO 489/689

Foundations of
Aerospace
Autonomy
Dr. Daniel Selva dselva@[Link]
Integer Programming
October 1-3, 2024

1
Logistics
• Will complete grading of HW 2 this week, HW 3 by next week
• Homework 4 (short) was posted yesterday 9/29, due Thursday 10/10

2
Why this topic?
• Natural implementation of a utility-based agent given a discrete set (or
sequence) of actions to choose from at any given point

• Many types of decisions taken by autonomous aerospace systems can be

naturally formulated as discrete optimization problems:
• Path planning
• Task-to-agent allocation
• Discrete resource allocation
• Task planning and scheduling
• Network flow optimization
• …
•

3
Integer Programming max 𝑍 = 3𝑥1 + 5𝑥2
𝑥
𝑠. 𝑡.
𝑥1 ≤ 4
max 𝑍 = 𝑐 𝑇 𝑥 2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥
𝑥1 , 𝑥2 ∈ ℤ+
𝑠. 𝑡. 𝐴𝑥 ≤ 𝑏
𝑥 ∈ ℤ+ 𝑥2

unfeasible
• An extension of a linear program feasible
where all variables are integer
• Note: A mixed-integer program has a mix
of continuous and integer variables
• Feasible region becomes a discrete
set of points 𝑥1

4
Integer Programming
• In general, the optimal solution is not
on a corner point!

• Solving the relaxed LP (without

integrality constraints) and rounding
to the nearest integer solution does
not always work.

• Optimal solution may not be unique!

IP problem formulations

6
Binary Integer Programming
max 𝑍 = 𝑐 𝑇 𝑥
𝑥
𝑠. 𝑡. 𝐴𝑥 ≤ 𝑏
𝑥 ∈ 0,1
• All binary variables – most popular formulation.
• Natural model for many classical combinatorial optimization problems
• Knapsack problem
• Assignment/matching problem
• Set cover/partitioning problem
• …
• Nice because very efficient algorithms exist for some classes of problems
• Greedy algorithms
• Dynamic programming
• Network simplex
• Hungarian algorithm
• Simplex (!)

7
Example: Knapsack problem
• There are 𝑛 items (e.g., an apple, a knife, a map, a water bottle, …)
• Each item 𝑖 has a value 𝑣𝑖 and a weight (or cost) 𝑤𝑖
• Goal is to choose a subset of the items so as to maximize the total value of
the items subject to a max weight (cost) constraint W
• Let 𝑥𝑖 = 1 if item 𝑖 is chosen, and 0 otherwise
• Formulation?
max ෍ 𝑥𝑖 𝑣𝑖
𝑥𝑖
𝑖
s.t. σ𝑖 𝑥𝑖 𝑤𝑖 ≤ 𝑊
𝑥𝑖 ∈ 0,1

8
Typical constraints in BIP
• Mutually exclusive options: σ𝑗∈𝐽 𝑥𝑗 = 1
• You must choose one among a set of “competing” options.
• Example: 𝑥𝑖𝑗 = 1 if task 𝑖 assigned to agent 𝑗.
• Assign each task 𝑖 to exactly 1 agent: σ𝑗 𝑥𝑖𝑗 = 1 ∀𝑖

• Covering constraints: σ𝑗 𝑥𝑗 ≥ 1
• Example: assign each task to at least one agent: σ𝑗 𝑥𝑖𝑗 ≥ 1 ∀𝑖

9
Assignment problem
• We have a set of tasks to be assigned to a set of agents.
• Variables: 𝑥𝑖𝑗 = 1 if task 𝑖 assigned to agent 𝑗, 0 otherwise
• Each assignment task-agent incurs some cost 𝑐𝑖𝑗 (assumed integer)
• Goal is to find an assignment of tasks to agents such that minimizes the total
cost
• min σ𝑖,𝑗 𝑥𝑖𝑗 𝑐𝑖𝑗
• Subject to (balanced formulation)
• Each agent must do one task σ𝑖 𝑥𝑖𝑗 = 1 ∀𝑗
• Each task must be assigned to exactly one agent σ𝑗 𝑥𝑖𝑗 = 1 ∀𝑖
• Note: This is a BIP but if you replace the constraints 𝑥𝑖𝑗 ∈ 1 with 0 ≤ 𝑥𝑖𝑗 ≤
1 and solve it as an LP, you get the correct (integer) optimal solution!
• Some LP problems with certain structure are guaranteed to have integer solutions

10
Unimodularity
• Definition: A matrix A is a totally unimodular matrix if every square submatrix's
determinant is -1, 0, or 1.
1 1 0 0
• Example (assignment problem with n=2): 𝐴 = 0 0 1 1
1 0 1 0
0 1 0 1

• Theorem: Let A be the constraint matrix of an LP. If A is totally unimodular, then if

an optimal solution to the problem exists, it is guaranteed to be integer.
• Examples of unimodular problems:
• Assignment problem
• Shortest path problem
• Minimum cost flow problem

11
Think-pair-share: Airline crew scheduling
• An airline has 11 flights and 3 crews. It has to assign a crew to each flight so as to cover all
flights and bring the crew back to their starting location (ideally the crew base) at the end
of the day.
• Assume part of this problem has been pre-solved and there are 12 valid sequences of
flights for a crew to do that satisfy the crew constraint (e.g., 𝐴 → 𝐵, 𝐵 → 𝐴 ሼ𝐵 → 𝐶, 𝐶 →
𝐵ሽ, 𝐴 → 𝐵, 𝐵 → 𝐶, 𝐶 → 𝐴 ).
• Given some cost for each valid sequence, formulate the problem to find the subset of
these sequences that covers all flights while minimizing cost.
• Variables: 𝑥𝑖𝑗 is crew 𝑖 assigned to sequence 𝑗?
• Parameters:
• 𝑐𝑖𝑗 is cost of assigning crew 𝑖 to sequence 𝑗 (very high if crew is assigned to a city≠ base city)
• 𝑎𝑗𝑘 does sequence j cover (include) flight 𝑘?
min ෍ 𝑥𝑖𝑗 𝑐𝑖𝑗
x
𝑖𝑗
s.t. σ𝑖𝑗 𝑥𝑖𝑗 𝑎𝑗𝑘 ≥ 1 ∀𝑘
𝑥𝑖 ∈ 0,1
12
Contingent or If-Then constraints in BIP
• How do we model constrains of the type If 𝑥𝑖 = 1, then 𝑥𝑗 = 1 in BIP?
• Recall the definition of 𝑥𝑖 → 𝑥𝑗 : 𝑥𝑖 can only be 1 if 𝑥𝑗 = 1 too
• This constraint forbids the assignment 𝑥𝑖 = 1, 𝑥𝑗 = 0
• All other assignments 𝑥𝑖 = 0, 𝑥𝑗 = 1 ,(0,0) and (1,1) are allowed
• Solution: 𝑥𝑖 ≤ 𝑥𝑗
• If 𝑥𝑗 = 0, then 𝑥𝑖 must be 0
• If 𝑥𝑖 = 0, 𝑥𝑗 is free (consistent with → truth table)

13
In-class question
• Consider the problem of allocating observation tasks (i) to UAVs (j).
• Different UAVs have different types of sensors (e.g.,
UAV1=visible/UAV2=infrared/UAV3=radar…).
• Write a constraint so that anytime that we send the UAV with a
thermal sensor to do a task (UAV2) we also want to send the one with
the visible camera (UAV1).
𝑥2𝑗 ≤ 𝑥1𝑗 ∀𝑗

14
Non-binary variables
• How do we deal with integer but non-binary variables?
• Note that one can represent integer variables as binary, e.g. via one-
hot coding or binary coding
• Example (one-hot): If 𝑥1 ∈ 0,15 then we can use 15 dummy binary variables
and one constraint 𝑥1 = σ15𝑗=0 𝑦𝑗
• Example (binary): 4 binary variables 𝑦1 , 𝑦2 , 𝑦3 , 𝑦4 and substitute 𝑥1 =
σ3𝑗=0 2𝑗 𝑦𝑗 = 𝑦0 + 2𝑦1 + 4𝑦2 + 8𝑦3
• But that is only efficient if done for a few variables.
• Otherwise, we need to resort to general integer programming

15
Example IP problem: Fixed charge problem
• Problem: investing on n products. Each product has
• a fixed non-recurring cost incurred for any non-zero level of
production
• and a recurring-cost proportional to production level.
• Choose production level for each product to minimize
total cost subject to a min production constraint. min σ𝑖 𝑛𝑐𝑖 𝑦𝑖 + 𝑟𝑐𝑖 𝑥𝑖
𝑥,𝑦
+
• Production level activity 𝑖: 𝑥𝑖 ∈ ℤ s.t. 𝑥𝑖 ≤ 𝑀𝑦𝑖 ∀𝑖
• Additional variable: if 𝑥𝑖 > 0, then 𝑦𝑖 = 1.
෍ 𝑥𝑖 ≥ 𝑃
• Can be expressed as constraint: 𝑥𝑖 ≤ 𝑀𝑦𝑖
𝑖
• Non-recurring costs activity 𝑖: 𝑛𝑐𝑖 (incurred once iff 𝑦𝑖 ∈ 0,1 , 𝑥𝑖 ≥ 0 ∀𝑖
𝑥𝑖 > 0, i.e. 𝑦𝑖 = 1)
• Recurring costs activity i: 𝑟𝑐𝑖 (incurred for every unit of
𝑥𝑖 )
16
Think-pair-share: Transportation problem
Goal is to distribute commodities between sources and destinations to match supply and demands
while minimizing total transportation cost.
• 𝑥𝑖𝑗 : flow from source node 𝑖 to destination node 𝑗 (here assumed integer)
• 𝑐𝑖𝑗 : cost of sending one unit commodity from node 𝑖 to node 𝑗
• 𝑠𝑖 : supply at source node 𝑖 𝑐11 𝐷1 −𝑑1
• 𝑑𝑗 : demand at destination node 𝑗 𝑠1 𝑆1
𝑚 𝑛
𝑐12
min 𝑍 = σ𝑖=1 σ𝑗=1 𝑐𝑖𝑗 𝑥𝑖𝑗
s.t. 𝑐21 𝑐13 𝐷2 −𝑑2
𝑛
𝑠2 𝑆2 …
෍ 𝑥𝑖𝑗 = 𝑠𝑖 , ∀𝑖 𝑐24 𝑐14
𝑗=1
𝑚 𝑐31 𝐷3 −𝑑3
…
෍ 𝑥𝑖𝑗 = 𝑑𝑗 , ∀𝑗 𝑠3 𝑆3
𝑖=1 𝑐34 𝐷4 −𝑑4

𝑥𝑖𝑗 ≥ 0, 𝑥𝑖𝑗 ∈ ℤ
17
Network optimization: Min cost flow problem
• Directed and connected graph with n nodes including at least one supply node and one demand node.
Goal is to min the cost of transporting supply to demand subject to capacity and flow conservation
constraints.
• Variables: 𝑥𝑖𝑗 : flow through edge 𝑖 → 𝑗 (here assumed integer)
• Parameters (given):
• 𝑐𝑖𝑗 : cost per unit flow through edge 𝑖 → 𝑗
• 𝑢𝑖𝑗 : capacity for edge 𝑖 → 𝑗
• 𝑏𝑖 : net flow generated at node 𝑖
• 𝑏𝑖 > 0 at supply nodes
min 𝑍 = σ𝑛𝑖=1 σ𝑛𝑗=1 𝑐𝑖𝑗 𝑥𝑖𝑗
• 𝑏𝑖 < 0 at demand nodes
• 𝑏𝑖 = 0 at transshipment nodes
s.t.
𝑛 𝑛

෍ 𝑥𝑗𝑖 + 𝑏𝑖 = ෍ 𝑥𝑖𝑗 , ∀𝑖
𝑗=1 𝑗=1
0 ≤ 𝑥𝑖𝑗 ≤ 𝑢𝑖𝑗 ∀𝑖, 𝑗
𝑥𝑖𝑗 ∈ ℤ+ ∀𝑖, 𝑗
18
More BIP Formulation Tricks
• Either-or and N-out-of-K constraints
• Ex: Either 3𝑥1 + 2𝑥2 ≤ 18 or 𝑥1 + 4𝑥2 ≤ 16 (e.g., can choose between two
resources, two design concepts, etc.)
• Equivalent to 3𝑥1 + 2𝑥2 ≤ 18 + 𝑀𝑦 and 𝑥1 + 4𝑥2 ≤ 16 + 𝑀 1 − 𝑦 where y
is an auxiliary binary variable and M is a large constant.
• Can be generalized to K out of N constraints by using N auxiliary variables and
adding constraint σ𝑖 𝑦𝑖 = 𝑁 − 𝐾
• Functions with N possible values
• Ex: 3𝑥1 + 2𝑥2 ∈ 𝑑1 , … , 𝑑𝑁 (𝑒. 𝑔. , 𝑑1 = 6, 𝑑2 = 12, 𝑑3 = 18)
• Rewrite as 3𝑥1 + 2𝑥2 = σ𝑖 𝑑𝑖 𝑦𝑖 and add σ𝑖 𝑦𝑖 = 1

19
IP algorithms
Branch and Bound

20
Notes on solving general IP problems
• Despite having smaller feasible regions, IP problems are generally much harder to
solve than LP problems
• Solution space is exponential in the number of variables! (LP usually much more sensitive to
#constraints)
• No longer true that one can just look at the corner point feasible solutions.
• Most efficient IP algorithms rely on LP for solving parts of the IP problem
• LP relaxation: dropping the integer constraints
• If solution to the relaxed LP problem happens to be integer, you are done!
• For some problems, that is guaranteed to occur, e.g.:
• Transportation problems where every 𝑠𝑖 and 𝑑𝑗 have integer values
• Min cost flows where every 𝑏𝑖 and 𝑢𝑖𝑗 have integer values
• In general, solving the LP relaxed problem is not enough
• Could be unfeasible!
• only an approximation to the true IP solution – a bound.

21
Main algorithms for integer programming
• Branch-and-bound
• Divide and conquer approach
• Branch on values of variables (i.e., search) to create smaller sub-problems
• Find a bound on the best possible solution for a given subproblem by solving
the LP relaxation
• Prune suboptimal or infeasible branches
• Cutting planes
• Progressively reduce the feasible region
• Solve LP relaxation and if solution is not integer, find and add an inequality
constraint (cut) that excludes that solution but not any integer solutions
• Keep doing that until the solution of the LP relaxation is integer

22
The BIP Branch-and-bound algorithm: Idea
• Solve the LP relaxation. If the solution is integer, you are done.
• Otherwise, branch: create 2 smaller subproblems where values are assigned
to 1 variable: 𝑥1 = 1 and 𝑥1 = 0 and add them to a search queue
• Bound: Formulate the next sub-problem with the additional constraint and
solve the LP relaxation (bound step). A few cases:
• If there is no solution, prune that branch (fathom the sub-problem)
• If there is a non-integer solution and the objective is worse than the incumbent, also
prune it
• If there is a non-integer solution and the objective is better than the incumbent, keep
sub-problem
• If the solution is integer and the best one found so far, store the solution (incumbent)
and fathom subproblem (won’t find anything better deeper since you are just adding
more constraints)

23
The BIP Branch-and-bound algorithm: Idea
• Keep searching (typically depth-first): go back to branch step
• As we go deeper in the tree, the sub-problems have fewer variables since
some of the variables are assigned
• Stop iterating when no unfathomed subproblems remain.
• If there is an incumbent solution, then it is optimal.
• If there is no incumbent solution, then the problem is unfeasible.

24
The BIP Branch-and-bound algorithm
• Initialization: Solve the LP relaxation of the original problem.
• If the solution is integer, done.
• Otherwise, set 𝑍 ∗ = −∞, and queue = (subproblem with no assignments to any variables).
• While queue is not empty
1. Branch
• Dequeue most recent unfathomed subproblem
• Add 2 new subproblems to the queue by branching on an unassigned variable (add 𝑥𝑖 = 1 or 𝑥𝑖 = 0 )
2. Bound
• Solve LP relaxation of 1 (or both) subproblem(s).
• Round down the optimal values of Z to obtain an upper bound on the original problem (bound because solution
to IP will at most be as good as the solution to the relaxed LP problem)
3. Fathom
• Abandon (fathom) any subproblems where any of these conditions are met: 1) 𝑍 ≤ 𝑍 ∗ ; 2) unfeasible
subproblem; 3) Z is integer (it’s not going to get better by adding further constraints!).
• In case 3, Z is incumbent solution. If 𝑍 > 𝑍 ∗ then set 𝑍 ∗ = 𝑍 and reapply test 1 to all unfathomed subproblems.
• If there is an incumbent solution, return it.
• Otherwise, return unfeasible.

25
Example
• Initialization
• Incumbent = none, 𝑍 ∗ = −∞
max 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4 • Queue = 𝑃0 =
𝑥
• Dequeue most recent sub-
𝑠. 𝑡.
problem 𝑃0 (original problem)
6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10
• Solve LP relaxation of 𝑃0
𝑥3 + 𝑥4 ≤ 1 • Solution: x=[0.8333,1,0,1], Z=16.5
𝑥3 − 𝑥1 ≤ 0 -> round to 16
𝑥4 − 𝑥2 ≤ 0 • Fathoming tests:
𝑥𝑗 ∈ 0,1 , ∀𝑗 1. 𝑍 ≤ 𝑍 ∗ ? No
2. Unfeasible subproblem? No
3. Z integer? No
• Therefore we cannot fathom 𝑃0

26
Example • Branch 𝑃0 =
• Add 𝑃1 = 𝑥1 = 0 to queue
Original problem
max 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4 • Add 𝑃2 = 𝑥1 = 1 to queue
𝑥
𝑠. 𝑡. 6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10
• Dequeue 𝑃1 and solve LP
𝑥3 + 𝑥4 ≤ 1 relaxation of resulting problem
𝑥3 − 𝑥1 ≤ 0 (substitute 𝑥1 = 0 )
𝑥4 − 𝑥2 ≤ 0
𝑥𝑗 ∈ 0,1 , ∀𝑗
max 𝑍 = 0 + 5𝑥2 + 6𝑥3 + 4𝑥4
𝑥
𝑃0 𝑠. 𝑡.
𝑥1 = 0 𝑥1 = 1 0 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10
𝑥3 + 𝑥4 ≤ 1
𝑥3 − 0 ≤ 0
𝑃1 𝑃2 𝑥4 − 𝑥2 ≤ 0
𝑥𝑗 ∈ 0,1 , ∀𝑗
• Incumbent = none, 𝑍 ∗ = −∞
• Queue = 𝑃1 = 𝑥1 = 0 , 𝑃2 = 𝑥1 = 1 • Solution: x=[0,1,0,1], Z=9
27
Example
• Solution: x=[0,1,0,1], Z=9
• Fathoming tests:
1. 𝑍 ≤ 𝑍 ∗ ? No • Dequeue 𝑃2
2. Unfeasible subproblem? No
𝑃0
3. Z integer? Yes
• Therefore, we fathom 𝑃1 𝑥1 = 0 𝑥1 = 1

• Since solution is integer, we update

incumbent 𝑃1 𝑃2
• Incumbent =,x*=[0,1,0,1], Z*=9

• Incumbent: x*=[0,1,0,1], Z*=9

• Queue = 𝑃2 = 𝑥1 = 1
28
 Original problem
max 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4
• Incumbent =,x*=[0,1,0,1], Z*=9 𝑥

Example • Queue = 𝑃2 = 𝑥1 = 1 𝑠. 𝑡. 6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10

𝑥3 + 𝑥4 ≤ 1
𝑥3 − 𝑥1 ≤ 0
𝑥4 − 𝑥2 ≤ 0
• LP relaxation of 𝑃2 𝑥𝑗 ∈ 0,1 , ∀𝑗

max 𝑍 = 9 + 5𝑥2 + 6𝑥3 + 4𝑥4

𝑥
𝑠. 𝑡. 6 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10
𝑥3 + 𝑥4 ≤ 1 𝑃0
𝑥3 − 1 ≤ 0
𝑥1 = 0 𝑥1 = 1
𝑥4 − 𝑥2 ≤ 0
𝑥𝑗 ∈ 0,1 , ∀𝑗
• Solution: x=[1,0.8,0,0.8], Z=7.2+9=16.2 𝑃1 𝑃2
• Fathoming tests:
1. 𝑍 ≤ 𝑍 ∗ ? No
2. Unfeasible subproblem? No
3. Z integer? No
29
• Therefore we cannot fathom 𝑃2
 Original problem
max 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4
𝑥

Example 𝑠. 𝑡. 6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10

𝑥3 + 𝑥4 ≤ 1
𝑥3 − 𝑥1 ≤ 0
𝑥4 − 𝑥2 ≤ 0
• Branch 𝑃2 𝑥𝑗 ∈ 0,1 , ∀𝑗
• Add 𝑃3 = 𝑥1 = 1, 𝑥2 = 0 to queue
• Add 𝑃4 = 𝑥1 = 1, 𝑥2 = 1 to queue 𝑃0
• Dequeue 𝑃3 𝑥1 = 0 𝑥1 = 1
• LP relaxation of 𝑃3
max 𝑍 = 9 + 0 + 6𝑥3 + 4𝑥4 𝑃1 𝑃2
𝑥
𝑠. 𝑡. 6 + 0 + 5𝑥3 + 2𝑥4 ≤ 10
𝑥3 + 𝑥4 ≤ 1 𝑥2 = 0 𝑥2 = 1
𝑥3 − 1 ≤ 0
𝑥4 − 0 ≤ 0 𝑃3 𝑃4
𝑥𝑗 ∈ 0,1 , ∀𝑗
• Incumbent =,x*=[0,1,0,1], Z*=9
• Queue = 𝑃3 = 𝑥1 = 1, 𝑥2 = 0 , 𝑃4 = 𝑥1 = 1, 𝑥2 = 1
30
 Original problem
max 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4
𝑥

Example 𝑠. 𝑡. 6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10

𝑥3 + 𝑥4 ≤ 1
𝑥3 − 𝑥1 ≤ 0
𝑥4 − 𝑥2 ≤ 0
• Solution: x=[1,0,0.8,0], Z=4.8+9=13.8 𝑥𝑗 ∈ 0,1 , ∀𝑗
• Fathoming tests:
1. 𝑍 ≤ 𝑍 ∗ ? No 𝑃0
2. Unfeasible subproblem? No 𝑥1 = 0 𝑥1 = 1
3. Z integer? No
• Therefore we cannot fathom 𝑃3
• Branch 𝑃3 𝑃1 𝑃2

𝑥2 = 0 𝑥2 = 1
• Incumbent =,x*=[0,1,0,1], Z*=9
• Queue = 𝑃4 = 𝑥1 = 1, 𝑥2 = 1 𝑃3 𝑃4

31
Example 𝑥1 = 0
𝑃0
𝑥1 = 1

• Add 𝑃5 = 𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 0 to queue
• Add 𝑃6 = 𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 1 to queue 𝑃1 𝑃2
• Dequeue 𝑃5
• Solve LP relaxation of 𝑃5 𝑥2 = 0 𝑥2 = 1
• max 𝑍 = 4𝑥4 s.t. 𝑥4 ≤ 0
𝑥
• Solution: x=[1,0,0,0], Z=0+9=9 𝑃3 𝑃4
• Fathoming tests:
1. 𝑍 ≤ 𝑍 ∗ ? Yes 𝑥3 = 0 𝑥3 = 1

2. Unfeasible subproblem? No
3. Z integer? Yes 𝑃5 𝑃6

• Therefore we fathom 𝑃5
• Incumbent =,x*=[0,1,0,1], Z*=9
• Queue = 𝑃4 , 𝑃5 , 𝑃6 32
Example 𝑥1 = 0
𝑃0
𝑥1 = 1

• Dequeue 𝑃6 and solve LP relaxation

max 𝑍 = 4𝑥4 𝑃1 𝑃2
𝑥
s.t. 2𝑥4 ≤ −1
𝑥4 ≥ 0 𝑥2 = 0 𝑥2 = 1

• Solution: Infeasible 𝑃3 𝑃4
• Therefore we fathom 𝑃6
• Dequeue 𝑃4 𝑥3 = 0 𝑥3 = 1

𝑃5 𝑃6

• Incumbent =,x*=[0,1,0,1], Z*=9

• Queue = 𝑃4 , 𝑃6 33
 Example 𝑥1 = 0
𝑃0
𝑥1 = 1

• Dequeue 𝑃4 and solve LP relaxation

max 𝑍 = 9 + 5 + 6𝑥3 + 4𝑥4 𝑃1 𝑃2
𝑥
𝑠. 𝑡. 6 + 3 + 5𝑥3 + 2𝑥4 ≤ 10 𝑥2 = 0 𝑥2 = 1
𝑥3 + 𝑥4 ≤ 1
𝑥3 − 1 ≤ 0
𝑃3 𝑃4
𝑥4 − 1 ≤ 0
𝑥𝑗 ∈ 0,1 , ∀𝑗
𝑥3 = 0 𝑥3 = 1
• Solution: x=[1,1,0,0.5], Z=2+14=16
• Fathoming tests: 𝑃5 𝑃6
1. 𝑍 ≤ 𝑍 ∗ ? No
2. Unfeasible subproblem? No
• Incumbent =,x*=[0,1,0,1], Z*=9
3. Z integer? No • Queue = 𝑃4
• Cannot fathom 𝑃4 ➔ branch 34
Example 𝑥1 = 0
𝑃0
𝑥1 = 1

• Branch on 𝑃4
• Add 𝑃7 = 𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 0 to queue 𝑃1 𝑃2
• Add 𝑃8 = 𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 1 to queue
• Dequeue 𝑃7 and solve LP relaxation 𝑥2 = 0 𝑥2 = 1
• Solution: x=[1,1,0,0], Z=0+14=14
• Fathoming tests: 𝑃3 𝑃4
1. 𝑍 ≤ 𝑍 ∗ ? No
2. Unfeasible subproblem? No 𝑥3 = 0 𝑥3 = 1
3. Z integer? Yes
• Fathom 𝑃7 𝑃5 𝑃6 𝑃7 𝑃8
• Update Incumbent: x*=[1,1,0,0], Z*=14
• Incumbent:
Incumbent =,x*=[0,1,0,1], Z*=9
x*=[0,1,0,1], Z*=14
• Queue = 𝑃7 , 𝑃8 35
 Example 𝑥1 = 0
𝑃0
𝑥1 = 1

• Dequeue 𝑃8 and solve LP relaxation

• Solution: infeasible ➔ fathom 𝑃8 𝑃1 𝑃2
• Queue empty
• No more unfathomed problems ➔ done 𝑥2 = 0 𝑥2 = 1

• Optimal solution: x*=[1,1,0,0], Z*=14 𝑃3 𝑃4

𝑥3 = 0 𝑥3 = 1

𝑃5 𝑃6 𝑃7 𝑃8
• Incumbent: x*=[0,1,0,1], Z*=14
• Queue = 𝑃8

36
Mixed-Integer (MIP) Branch and Bound
• How do we deal with non-binary and continuous variables?
• General MIP looks the same as BIP B&B, with 4 changes:
• Choice of branching variable: Branch only on integer variables with non-integer
values in the optimal solution of current subproblem
• Construction of sub-problems: two subproblems based on 𝑥𝑗 ≤ 𝑥𝑗∗ and 𝑥𝑗 ≥
𝑥𝑗∗ + 1, where 𝑥𝑗∗ is the value of 𝑥𝑗 in the optimal solution to the LP
relaxation of the current subproblem, and 𝑥 = 𝑓𝑙𝑜𝑜𝑟(𝑥).
• Bounding step: Don’t round down Z for each subproblem.
• Integer solution fathoming test: Only applied to integer variables

37
Solving MIP problems with computers
• Matlab: intlinprog
• Python: [Link]
• Other tools: CPLEX, Gurobi, SCIP (ZIMPL)

38
Other IP optimization methods
• Variations of Branch-and-bound (e.g., Lagrangian relaxation)
• Branch-and-cut: Similar to branch and bound but with 2 new ideas:
• Pre-processing:
• fixing variables (e.g., 3𝑥2 ≤ 2 means 𝑥2 = 0)
• eliminating redundant constraints (e.g., 6𝑥1 + 3𝑥2 ≤ 10 is redundant with 𝑥𝑖 binary)
• tightening constraints (e.g., 2𝑥1 + 3𝑥2 ≤ 4 can be replaced with 𝑥1 + 𝑥2 ≤ 1 without
changing the feasible/optimal solutions)
• Cutting planes: Add inequality constraints that eliminate solution to LP relaxation
problem but don’t change the optimal solution to the IP problem (same idea as
tightening constraints)
• Constraint programming: Use CSP techniques seen before (e.g., constraint
propagation)
• Heuristics and meta-heuristics

39
Example of script for commercial tool: Earth
Observation Constellation Planning with ZIMPL
• Problem: Decide where to point satellites to maximize total reward of observations subject to
slewing constraints and a pre-computed set of observation opportunities ([Link])
• Parameters
• param access[TIPS] := read "[Link]" as "<11n,10n,9n,8n> 12n" skip 1 default 0;
• param times[T] := read "[Link]" as "<11n> 4n" skip 1 default 0;
• param r[I] := read "[Link]" as "<10n> 7n" skip 1 default 0;
• param theta[<p> in P] := 5*(p-7);
• Variables
• var o[<t,p,s> in TPS] binary;
• Objective
• maximize obj: sum <t,i,p,s> in TIPS : (o[t,p,s] * access[t,i,p,s] * r[i]);
• Constraints:
• subto point : forall <t,s> in TS do sum <p> in P: o[t,p,s] <= 1;
• subto slew_torque: forall <t,s> in TS1 : (sum <p> in P: o[t,p,s] * theta[p]) - (sum <p> in P: o[t-1,p,s] * theta[p])
<= times[t] - times[t-1];

40