Optimization Techniques-

Mixed-Integer Programming

Shamik Misra
Mixed integer Programming
• Many problems in plant operation, design, location, and scheduling involve variables that are not continuous but
instead have integer values.
• Decision variables for which the levels are a dichotomy-to install or not install a new piece of equipment for
example-are termed "0-1" or binary variables.
• Other integer variables might be real numbers 0, 1, 2, 3, and so on.

The most general mixed-integer problems are mixed-integer non-linear programming involving continuous and integer
variables 𝑥, 𝑦.
MINLP MINLP with Binaries MILP MILP with binaries
min 𝑓(𝑥, 𝑦) min 𝑓(𝑥, 𝑦) min 𝑓 𝑥, 𝑦 = 𝑐 𝑇 𝑥 + 𝑏𝑇 𝑦 min 𝑓 𝑥, 𝑦 = 𝑐 𝑇 𝑥 + 𝑏𝑇 𝑦
s.t. s.t. s.t. s.t.
ℎ 𝑥, 𝑦 = 0 ℎ 𝑥, 𝑦 = 0 𝐴𝑥 + 𝐵𝑦 ≤ 𝑑 𝐴𝑥 + 𝐵𝑦 ≤ 𝑑
𝑔 𝑥, 𝑦 ≤ 0 𝑔 𝑥, 𝑦 ≤ 0 𝑥 ≥ 0, y ∈ ℤ𝑚 𝑥 ≥ 0, y ∈ {0,1}𝑚
𝑥 ∈ ℝ𝑛 , y ∈ ℤ𝑚 𝑥 ∈ ℝ𝑛 , y ∈ {0,1}𝑚

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 2

Modeling with 0-1 Variables
• Multiple choice constraints • Discontinuous domains and functions
o Select at least one σ𝑗∈𝐽 𝑦𝑗 ≥ 1. o Fixed-charge cost model
𝛼 + 𝛽𝑥 𝐿≤𝑥≤𝑈
o Select exactly one σ𝑗∈𝐽 𝑦𝑗 = 1. 𝐶=ቊ
0 𝑥=0

o Select not more than one σ𝑗∈𝐽 𝑦𝑗 ≤ 1.

The fixed-cost function can be represented with linear 0-1
variables by,
• If then condition 𝐶 = 𝛼𝑦 + 𝛽𝑥
o If select 𝑦𝑘 then select 𝑦𝑗 : 𝑦𝑘 − 𝑦𝑗 ≤ 0 𝐿𝑦 ≤ 𝑥 ≤ 𝑈𝑦
𝑥 ≥ 0, 𝑦 = {0,1}
o If and only if condition : 𝑦𝑘 = 𝑦𝑗

• Disjunction
o Either constraint 𝑔1 (𝑥)or constraint 𝑔2 (𝑥) must be satisfied:
𝑔1 (𝑥) ≤ 𝑀(1 − 𝑦1 )
𝑔2 (𝑥) ≤ 𝑀(1 − 𝑦2 )
𝑦1 + 𝑦2 = 1

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 3

Modeling with 0-1 Variables
• Let 𝑃𝑖 represent a logical proposition and 𝑦𝑖 its associated binary variable. For instance, these are involved when
representing shipping or mailing costs.

• A few instances are given below.

o If 𝑃1 or 𝑃2 is true then, 𝑃3 is true

𝑦1 ≤ 𝑦3 , 𝑦2 ≤ 𝑦3

o If 𝑃3 is true, then 𝑃1 or 𝑃2 is true:

𝑦1 + 𝑦2 ≥ 𝑦3

o If both 𝑃1 and 𝑃2 are true, then 𝑃3 is true:

1 + 𝑦3 ≥ 𝑦1 + 𝑦2

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 4

Assignment Problem
Given a set of 𝑛 jobs 𝑖 and given a set of 𝑛 machines 𝑗. The cost for assigning jobs to machines is 𝑐𝑖𝑗 . The problem then is
finding the minimum cost for the assignment of jobs to machines.
o For every job 𝑖 only one machine 𝑗 can be assigned
o For every machine 𝑗 only one job 𝑖 can be assigned
𝑛 𝑛

min 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑦𝑖𝑗

𝑖=1 𝑗=1
𝑛

෍ 𝑦𝑖𝑗 = 1 ∀𝑖
𝑗=1
𝑛

෍ 𝑦𝑖𝑗 = 1 ∀𝑗
𝑖=1
𝑦𝑖𝑗 = 0,1 ∀𝑖, 𝑗

An interesting property of this problem is that it can be solved as an LP with continuous variables 𝑦𝑖𝑗 , such that
0 ≤ 𝑦𝑖𝑗 ≤ 1. The reason that all the extreme points of the polytope defined by assignment constraints correspond to 0-1
variables for the continuous variables 𝑦𝑖𝑗 .

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 5

Plant Location Problem
Consider 𝑛 potential plants that are to serve 𝑚 customers (j) with demands 𝑑𝑗 . Each plant has a fixed cost 𝑓𝑖 and
maximum production capacity 𝑈𝑖 . Also the combined transportation and manufacturing cost from a plant 𝑖 to customer
𝑗 is given by the cost 𝑐𝑖𝑗 . The problem then consists of selecting the plants that serve the customers so as to satisfy the
demands at the minimum total cost.
𝑛 𝑛 𝑚

min 𝑍 = ෍ 𝑓𝑖 𝑦𝑖 + ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑖=1 𝑗=1
𝑛

෍ 𝑥𝑖𝑗 = 𝑑𝑗 ∀𝑗
𝑖=1
𝑛

෍ 𝑥𝑖𝑗 − 𝑈𝑖 𝑦𝑖 ≤ 0 ∀𝑖
𝑗=1
𝑦𝑖 = 0,1 ∀𝑖, 𝑥𝑖𝑗 ≥ 0 ∀𝑖, 𝑗

In contrast to the assignment problem, plant location problem is known to be NP-Hard, meaning that in the worst case
the computational time scales increases exponentially with the problem size of the MILP.
[Link]

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 6

Knapsack Problem
We have 𝑛 objects. The weight of the 𝑖𝑡ℎ object is 𝑤𝑖 , and its value is 𝑣𝑖. Select a subset of the objects such that their total
weight does not exceed 𝑊 (the capacity of the knapsack) and their total value is a maximum.

Despite its apparent simplicity, this problem is also known to be NP-Hard.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 7

Set Covering Problem
Assume that we are given 𝑛 computer files containing units of information 𝑖, which are represented by the set that
indicates the location of the unit of information 𝑖 in file 𝑗, 𝑃𝑗 = {𝑖: unit 𝑖 in file 𝑗}. Furthermore, assume that the size of
each file 𝑗 is given by 𝑐𝑗 . The problem that consists of deciding which files to open for reading so as to retrieve the
required units of information 𝑖 ∈ 𝑃𝑗 and so as to minimize the total size of the files that are searched.
𝑛

min 𝑍 = ෍ 𝑐𝑗 𝑦𝑗
𝑗=1
𝑛

෍ 𝑎𝑖𝑗 𝑦𝑗 ≥ 1 ∀𝑖: (𝑖 = 1 … 𝑚)
𝑗=1
𝑦𝑗 = 0,1 ∀𝑗

1 𝑖𝑓 𝑖 ∈ 𝑃𝑗
𝑎𝑖𝑗 = ቊ
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 8

Blending Problem
You are given a list of possible ingredients to be blended into a product, from a list containing the weight, value, cost, and
analysis of each ingredient. The objective is to select from the list a set of ingredients so as to have a satisfactory total weight
and analysis at minimum cost for a blend. Let 𝑥𝑗 be the quantity of ingredient 𝑗 available in continuous amounts and 𝑦𝑘
represent ingredients to be used in discrete quantities 𝑣𝑘 (𝑦𝑘 = 1 if used and 𝑦𝑘 = 0 if not used). Let 𝑐𝑗 and 𝑑𝑘 be the respective
costs of the ingredients and 𝑎𝑖𝑗 be the fraction of component 𝑖 in ingredients 𝑗. The problem statement is

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 9

Traveling Salesman Problem
• The traveling salesman problem (TSP) is perhaps the most extensively studied integer programming problem.
• The TSP considers 𝑛 cities for which the distance or cost 𝑐𝑖𝑗 is given for every pair of cities 𝑖, 𝑗 𝑖 ≠ 𝑗 . The problem
then consists of finding the shortest or cheapest tour so that every city is visited only once.
𝑛 𝑛

min 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑦𝑖𝑗

𝑖=1 𝑗=1
𝑛

෍ 𝑦𝑖𝑗 = 1 ∀𝑖
𝑗=1
𝑛

෍ 𝑦𝑖𝑗 = 1 ∀𝑗
𝑖=1

෍ ෍ 𝑦𝑖𝑗 ≥ 1 ∀𝑄, 𝑄ത ⊆ 𝑉, 𝑄 ≠ ∅
𝑖=𝑄 𝑗∈𝑄ത

𝑦𝑖𝑗 ≥ 0 ∀𝑖, 𝑗

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 10

Polynomial 0–1 Programming
max 𝑍 = 𝑦12 + 𝑦2 𝑦3 − 𝑦33 Interesting polynomial properties for 0-1 variables:
Subject to,
−2𝑦1 + 3𝑦22 + 𝑦1 𝑦3 ≤ 3 • Any 0–1 variable 𝑥𝑖 raised to a positive integer p has the
𝑝
property 𝑥𝑖 = 𝑥𝑖 .
𝑦1 , 𝑦2 , 𝑦3 = {0,1}
o Thus, general polynomials can be reduced to the
• Can we convert this into a linear MILP? 𝑝 𝑝 𝑝
product form 𝑥1 1 𝑥2 1 … 𝑥𝑚𝑚 = 𝑥1 𝑥2 … 𝑥𝑚

• A product can be substituted by 𝑦 with two constraints

that ensure that 𝑦 is zero if any of 𝑥𝑖 is zero, and it is 1
only when all 𝑥𝑖 are 1. where 𝑦 is also a binary variable.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 11

Why Rounding off LP Solution won’t work
A furniture manufacturer produces lawn chairs and tables. The profit
from the sale of each chair is $2 and the profit from the sale of a table
is $3. Each chair weighs 4 pounds and each table weighs 10 pounds. A
supply of 45 pounds of material is available at hand. The labor per
chair is 4 hours and the labor per table is 4 hours. Only 23 hours of
labor is available. Determine the number of chairs and tables for
realizing maximum profit.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 12

Solution Methods (MILP)
• Cutting Plane Method:
This method consists of solving a sequence of LPs in which cutting planes are successfully generated to cut off the
solution of the relaxed LP with previously accumulated cutting planes. Method first proposed by Gomory (1958).

• Benders Decomposition:
This method partitions the problem into integer and continuous variables and consists of solving a sequence of integer
master problem and LP subproblems. The latter generates cuts that are successively incorporated into the master
problem that predicts lower bounds to the solution of the MILP. Method was proposed by Benders (1962).

• Branch and Bound Search:

This method consists of representing the integer variables through a tree-like framework in which LP subproblems are
solved to determine the lower and upper bounds in order to find the optimal solution by enumerating a subset of the
nodes of the tree. Method first proposed by Land and Doig(1960), and subsequently formalized by Dakin(1965).

• Branch and Cut Method:

These method combines the B&B method with the cutting plane method with the goal of strengthening the lower
bounds. Initial method developed by Crowder et al.(1983) and Van Roy and Wolsey (1987). Further improved general
branch and cut method proposed by Balas et al. (1993).

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 13

Tree and Network Representation
Given a mixture of four chemicals A, B, C, D for which different technologies are used to separate the mixture of
pure components. The cost of each technology is given in Table below. Formulate the problem as an optimization
problem with tree and network representations.

Cost of separation are given in 1000$/year

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 14

Tree and Network Representation

Tree Representation: Network Representation:

✓ The tree representation shows clear paths to final decisions. ✓ Network representation avoids duplication and each node
✓ The tree representation is suitable when the discrete decisions corresponds to a unique decision.
are represented separately (B&B Method) ✓ This representation is useful when one is using methods like
× Involves duplication discrete dynamic programming

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 15

Tree representation and cost diagram
Heuristics:

• The cost accumulated at any intermediate node is a

lower bound to the cost of any successor nodes, as
the successor node is bound to incur additional cost.

• For a terminal node, the total cost provides an upper

bound to the original problem because a terminal
node represents a solution that may or may not be
optimal.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 16

Pruning
If the cost at the current node is greater than or equal to the
upper bound defined earlier either from one of the prior
branches or known to us from experience, then we don’t need
to go further in that branch.

• Depth-first: Here, we successively perform one branching

on the most recently created node. When no nodes can be
expanded, we backtrack to a node whose successor nodes
have not been examined.

• Breadth-first: Here, we select the node with the lowest

cost and expand all its successor nodes.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 17

Depth-first Strategy

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 18

Breadth-first strategy

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 19

Comparison
• In general, the breadth-first strategy requires the examination of fewer nodes and no backtracking.

• However, depth-first requires less storage of nodes because the maximum number of nodes to be stored at any
point is the number of levels in the tree.

• For this reason, the depth-first strategy is commonly used.

• Also, the depth-first strategy has a tendency to find the optimal solution earlier than the breadth-first strategy.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 20

Algebraic representation of the tree structure

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 21

Branch and Bound Method (Example with 0-1 variable)
• Branch and bound (BB) is a class of methods for linear and
nonlinear mixed-integer programming.

• If carried to completion, it is guaranteed to find an optimal

solution to linear and convex nonlinear problems.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 22

Branch & Bound Method (General Algorithm)
Consider an MIP problem of the form

• The first step is to solve the MIP problem as a linear program by ignoring the integer restrictions.

• Let us denote by LP-1 the linear program whose optimal value of the objective function is 𝑍1. Assume the optimal
solution to LP-1 contains some integer variables at fractional values.

• Hence we do not have an optimal solution to the MIP problem. But 𝑍1 is an upper bound on the maximum value of Z
for the MIP problem.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 23

Branch & Bound Method (Continued…)
• The next step is to partition the feasible region of LP-1 by
branching on one of the integer variables at a fractional
value.
• A number of rules have been proposed to select the
proper branching variable.
o Selecting the integer variable with the largest
fractional value in the LP solution.
o Priority branching
o Arbitrary selection rules: Variable with lowest index

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 24

Branch & Bound Method (Continued…)
• Assume that the optimal solutions to LP-2 and LP-3 are
still fractional and hence are infeasible to the MIP
problem with integer restrictions.
• The next step is to select either LP-2 or LP-3 and branch
from that by adding a new constraint. Here again, a
number of rules have been proposed for selecting the
proper node (LP problem) to branch from.
o Objective function value: choose the one whose LP
optimal value is the largest (for a maximization
problem).
o Last-In–First-Out Rule. The LP problem that was
solved most recently is selected (arbitrarily) for
further branching.

• Once the proper node (LP region) is selected for further

branching, we branch out by choosing an integer variable
with a fractional value.
• This process of branching and solving a sequence of linear
programs is continued until an integer solution is obtained
for one of the linear programs.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 25

Branch & Bound Method (Continued…)
• The value of Z for this integer solution becomes a lower
bound on the maximum value of Z for the MIP problem.

• At this point we can eliminate (fathomed) from

consideration all those nodes (LP regions) whose values
of Z are not better than the lower bound.

• Once the proper node (LP region) is selected for further

branching, we branch out by choosing an integer variable
with a fractional value.
• This process of branching and solving a sequence of linear
programs is continued until an integer solution is obtained
for one of the linear programs.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 26

Some Guidelines for Good Formulation
The solution time for solving the integer programming problem is very sensitive to the way the problem is formulated initially.
From practical experience in solving a number of integer programs by the branch-and-bound method, here are some general
suggestions on model formulations:

• Keep the number of integer variables as small as possible.

• Provide a good (tight) lower and upper bound on the integer variables when possible.

• Unlike the general LP problem, the addition of new constraints to a MIP problem will generally reduce the computational
time, especially when the new constraints contain integer variables.

• If there is no critical need to obtain an exact optimal integer solution, then considerable savings in computational time may
be obtained by accepting the first integer solution that is 1 percent of the continuous optimum. In other words, for a
maximization problem, we can terminate the branch-and-bound procedure whenever:

𝑈𝑝𝑝𝑒𝑟 𝑏𝑜𝑢𝑛𝑑 − 𝑙𝑜𝑤𝑒𝑟 𝑏𝑜𝑢𝑛𝑑

𝑂𝑝𝑡𝑖𝑚𝑎𝑙𝑖𝑡𝑦 𝑔𝑎𝑝 % = ≤ 0.01
𝑈𝑝𝑝𝑒𝑟 𝑏𝑜𝑢𝑛𝑑
• The order in which the integer variables are chosen for branching affects the solution time. It is recommended that the
integer variables be processed in a priority order based on their economic significance and user experience.

Optimization Techniques (CH 5022) Shamik Misra 11/11/2025 27