Mixed Integer Linear
Programming Tutorial
Pano Santos, PhD, Technical Content Manager

Tutorial Agenda
Video

FormatTime (min)1- Why Mixed Integer Programming (MIP)?

Slides10

2- Resource Assignment Problem (RAP) – Introduction

Slides10

3- Linear Programming (LP) Formulation – RAP

Slides10

4- Formulation With Gurobi Python API - RAP

Slides10

5- Jupyter Notebook 001- RAP

Demo

10

6- Perfect Formulation 002 – RAP

Slides & Demo10

7- Methods for Solving a MIP Problem

Slides10

8- Methods for Solving a MIP Problem: Branch-and-Bound Approach

Slides

15

9- Methods for Solving a MIP Problem: Cutting Planes Approach

Slides10

10- Why MIP Is Better Than Simple Heuristics ?
RAP 003Demo

15

11- Conclusions

Slides52© 2019, Gurobi Optimization, LLC

Why Mixed Integer Programming (MIP)?

3© 2019, Gurobi Optimization, LLC

Why MIP?...1• Mixed integer programming (MIP) can be successfully implemented to optimize the operational
efficiency of a complex organization, while considering resource demand and capacity
constraints, and critical business rules.
• Applications of MIP models:• Supply Chain Optimization: SAP Advanced Planning and Optimization and SAP HANA help solve
complex optimization problems.
• Electrical Power Optimization: NYISO managed New York’s wholesale electrical power market($7.5 billion in annual transactions) to optimize 500 power-generation units and 11,000 miles oftransmission lines with consumer demand in real time.
• Government: The Federal Communications Commission (FCC) used optimization to generate thefirst two-sided spectrum auction, generating $20 billion in revenue.

4© 2019, Gurobi Optimization, LLC

Why MIP?...2• Mixed-integer-programming (MIP) models have been applied in a variety of business realms,
often resulting in cost savings of tens or even hundreds of millions of dollars.
• MIP model formulations allow us to combine predicate logic (aka first-order-logic) with
optimization.
• This means several rules can be embedded in the mathematical problem formulation.
• For example, a production planning model might include a rule that says if product A is produced,
then product B must be produced, and product C cannot be produced.

5© 2019, Gurobi Optimization, LLC

Why MIP?...3• Applications of MIP models relevant to data scientists:• Marketing Campaign Optimization•

There is a set of products and a set of customers.

•

The problem is to identify which product to advertise to which customer, maximizing the advertised product’s
ROI and staying within a budget.

• Price Optimization•

There is a set of inventories of various retail products.

•

The problem is to determine at which price each retail product should be sold in order to maximize profits,
while considering a minimum level of ROI and market share, and other business rules.

• Resource Management Optimization

6•

There is a set of resources with various qualifications, and there is a set of jobs with specific requirements
regarding resources qualifications.

•

The problem is to determine an assignment of resources to jobs that maximizes the total matching score of
the assignments.
© 2019, Gurobi Optimization, LLC

Why MIP?...4• Approaches to solving MIP problems:• Branch-and-bound approach• Cutting planes approach7© 2019, Gurobi Optimization, LLC

Resource Assignment Problem
Introduction

8© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…1• Consulting company’s open positions: Tester, Java-Developer, and Architect• Three top resources: Carlos, Joe, and Monika• Results of competency tests: matching scores• Assumption: Only one resource can be assigned to a job, and at most one job can be assigned to a
resource.

9

Matching Scores

TesterJava-Developer

Architect

Carlos

53%

27%

13%

Joe

80%

47%

67%

Monika

53%

73%

47%

© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…2• Simple heuristic approach
1. Consider the highest score, match the resource with the job of the highest score, eliminate theresource and the job from the table.
2. Choose the next highest score. If no scores are available, STOP; all jobs have been assigned to
all resources. Otherwise, go to 1.

10

Matching Scores

TesterJava-Developer

Architect

Carlos

53%

27%

13%

Joe

80%

47%

67%

Monika

53%

73%

47%

© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…3• Simple heuristic approach
1. Consider the highest score, match the resource with the job of the highest score, eliminate theresource and the job from the table.
2. Choose the next highest score. If no scores are available, STOP; all jobs have been assigned to
all resources. Otherwise, go to 1.

11

Matching Scores

TesterJava-Developer

Architect

Carlos

53%

27%

13%

Joe

80%

47%

67%

Monika

53%

73%

47%

© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…4• Simple heuristic approach
1. Consider the highest score, match the resource with the job of the highest score, eliminate theresource and the job from the table.
2. Choose the next highest score. If no scores are available, STOP; all jobs have been assigned to
all resources. Otherwise, go to 1.
Matching Scores

TesterCarlosJoe
Monika12Java-Developer

Architect

27%

13%

73%

47%

80%

© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…5• Simple heuristic approach
1. Consider the highest score, match the resource with the job of the highest score, eliminate theresource and the job from the table.
2. Choose the next highest score. If no scores are available, STOP; all jobs have been assigned to
all resources. Otherwise, go to 1.
Matching Scores

TesterJava-Developer

13%

CarlosJoe
Monika13

Architect

80%
73%© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…6• Simple heuristic approach
1. Consider the highest score, match the resource with the job of the highest score, eliminate theresource and the job from the table.
2. Choose the next highest score. If no scores are available, STOP; all jobs have been assigned to
all resources. Otherwise, go to 1.
Matching Scores

TesterJava-Developer

13%

CarlosJoe
Monika14

Architect

80%
73%© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…7
Simple heuristic approach• Remarks• The total score of the assignment is 80% + 73% + 13%= 166%.
• Note that this assignment is far from optimal since
Carlos was assigned to a job with the lowest score.
We can certainly do much better than that!
Matching Scores

TesterJava-Developer

13%

CarlosJoe
Monika15

Architect

80%
73%© 2019, Gurobi Optimization, LLC

1. Consider the highest score,match the resource with thejob of the highest score,eliminate the resource and thejob from the table.
2. Choose the next highest
score. If no scores areavailable, STOP; all jobs havebeen assigned to all
resources. Otherwise go to 1.

Resource Assignment Problem…8• Another simple approach:• Assign the first job to any of the three candidates.
• Assign the second job to any of the remaining two candidates.
• Assign the third job to the remaining candidate.
• The number of possible assignments is 3*2*1 = 6. Note: The number (3 factorial) 3!= 3*2*1 = 6.

16

© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…9
Another simple approach:
Number

1
2

∙

∙

3
4
5
6

∙

∙

∙

∙

17

∙

Assignment∙

Tester - Carlos (53%) Java - Joe (47%) Archt.- Monika (47%)∙

Tester- Joe (80%) Java - Carlos (27%) Archt.- Monika (47%)∙

Tester - Monika (53%) Java - Joe (47%) Archt.- Carlos (13%)∙

Tester - Carlos (53%) Java - Monika (73%) Archt.- Joe (67%)∙

Tester - Joe (80%) Java - Monika (73%) Archt.- Carlos (13%)∙

Tester - Monika (53%) Java - Carlos (27%) Archt.- Joe (67%)

∙

Score

147%
154%
113%
193%
166%
147%

© 2019, Gurobi Optimization, LLC• Assign the first job to anyof the three candidates.
• Assign the second job toany of the remaining two
candidates.
• Assign the third job to theremaining candidate.

• The number ofpossible assignments
is 3*2*1 = 6.
Note: the number (3factorial) 3!= 3*2*1 = 6.

Resource Assignment Problem…10• The consulting company wins a major government contract that requires 100 jobs.
• The problem is to assign 100 candidates to 100 jobs.
• The enumeration algorithm proposed above enumerates 100! possible assignments.
• 100! ≈ 9.3×10157 ,• This number is humongous, much larger than the number of atoms in the universe, which isapproximately 1080 .

18© 2019, Gurobi Optimization, LLC

Resource Assignment Problem…11• Even the fastest supercomputer called“Summit”• That can make mathematical calculations at
a rate of 200 petaflops/second• Will take an astronomical number of years
to enumerate all the assignments anddetermine the optimal one.

19

© 2019, Gurobi Optimization, LLCLinear Programming Formulation
Resource Assignment Problem (RAP)20© 2019, Gurobi Optimization, LLCLinear Programming Formulation…1• Problem statement

21•

Three jobs: Tester, Java-Developer, and Architect•

Three resources: Carlos, Joe, and Monika•

Data: matching scores for all job-resource combinations•

Assumption: Only one resource can be assigned to a job, and at most one job can be assigned to a
resource•

Problem: Determine an assignment that ensures each job is fulfilled and each resource is assigned to at
most one job, maximizing the total matching scores of the assignments.
Matching Scores

TesterJava-Developer

Architect

Carlos

53%

27%

13%

Joe

80%

47%

67%

Monika

53%

73%

47%

© 2019, Gurobi Optimization, LLCLinear Programming Formulation…2• Decision variables
•
•
•
•

22

We need to identify which resource is assigned to which job
Therefore, we have 9 decision variables, one per possible assignment
To simplify the mathematical notation of the model formulation, let’s define the following indices for the
resources and for the jobs
The decision variable 𝑥𝑟,𝑗 = 1 represents that resource r is assigned to job j, and 0 otherwise, for r = 1,2,3
and 𝑗 = 1,2,3.
Decision Variables

Tester = 1

Java-Developer = 2

Architect = 3

Carlos = 1

𝒙𝟏,𝟏

𝒙𝟏,𝟐

𝒙𝟏,𝟑

Joe = 2

𝒙𝟐,𝟏

𝒙𝟐,𝟐

𝒙𝟐,𝟑

Monika = 3

𝒙𝟑,𝟏

𝒙𝟑,𝟐

𝒙𝟑,𝟑

© 2019, Gurobi Optimization, LLCLinear Programming Formulation…3• Job constraints•

The job constraint of the Tester position is that either resource 1 (Carlos), resource 2 (Joe), or resource 3 (Monika)
is assigned to this job.

•

Constraint (Tester = 1): 𝑥1,1 + 𝑥2,1 + 𝑥3,1 = 1••

Similarly the constraints for the Java Developer and Architect positions can be defined as follows
Constraint (Java Developer = 2): 𝑥1,2 + 𝑥2,2 + 𝑥3,2 = 1•

Constraint (Architect = 3): 𝑥1,3 + 𝑥2,3 + 𝑥3,3 = 1•

Notice that the job constraints are defined by the columns of the following table.

Decision Variables

Tester = 1

Java-Developer = 2

Architect = 3

Monika = 3

𝒙𝟏,𝟏
𝒙𝟐,𝟏
𝒙𝟑,𝟏

𝒙𝟏,𝟐
𝒙𝟐,𝟐
𝒙𝟑,𝟐

𝒙𝟏,𝟑
𝒙𝟐,𝟑
𝒙𝟑,𝟑

Requirement

1

1

1

Carlos = 1
Joe = 223

© 2019, Gurobi Optimization, LLCLinear Programming Formulation…4• Resource constraints
•
•
•
•
•
•

24

The constraint for Carlos is that either job 1 (Tester), job 2 (Java Developer ), or job 3 (Architect) is assigned
to this resource. Assume #resources ≥ #jobs.
Constraint (Carlos = 1): 𝑥1,1 + 𝑥1,2 + 𝑥1,3 ≤ 1
Similarly the constraints for the resources Joe and Monika can be defined as follows:
Constraint (Joe = 2): 𝑥2,1 + 𝑥2,2 + 𝑥2,3 ≤ 1
Constraint (Monika = 3): 𝑥3,1 + 𝑥32 + 𝑥3,3 ≤ 1
Notice that the resource constraints are defined by the rows of the following table.
Decision Variables

Tester = 1

Java-Developer = 2

Architect = 3

Availability

Carlos = 1

𝒙𝟏,𝟏

𝒙𝟏,𝟐

𝒙𝟏,𝟑

1

Joe = 2

𝒙𝟐,𝟏

𝒙𝟐,𝟐

𝒙𝟐,𝟑

1

Monika = 3

𝒙𝟑,𝟏

𝒙𝟑,𝟐

𝒙𝟑,𝟑

1

© 2019, Gurobi Optimization, LLCLinear Programming Formulation…5• Objective function
•

•
•
•
•

25

The objective function is to maximize the total matching score of the assignments that satisfy the job andresource constraints. Notice that for job1 the matching score is 53𝑥1,1 -if resource Carlos is assigned, or 80𝑥2,1 if resource Joe is assigned, or 53𝑥3,1 -if resource Monika is assigned. Consequently,
Job 1 (Tester ) matching score: (53𝑥1,1 +80𝑥2,1 + 53𝑥3,1 )Job 2 (Java Developer ) matching score: (27𝑥1,2 + 47𝑥2,2 + 73𝑥3,2 )Job 3 (Architect ): (13𝑥1,3 + 67𝑥2,3 + 47𝑥3,3 )Maximize total matching score:(53𝑥1,1 +80𝑥2,1 + 53𝑥3,1 ) + (27𝑥1,2 + 47𝑥2,2 + 73𝑥3,2 )+(13𝑥1,3 + 67𝑥2,3 + 47𝑥3,3 ).
Decision Variables

Tester = 1

Java-Developer = 2

Architect = 3

Carlos = 1

𝟓𝟑𝒙𝟏,𝟏

𝟐𝟕𝒙𝟏,𝟐

𝟏𝟑𝒙𝟏,𝟑

Joe = 2𝟖𝟎𝒙𝟐,𝟏

𝟒𝟕𝒙𝟐,𝟐

𝟔𝟕𝒙𝟐,𝟑

Monika = 3

𝟓𝟑𝒙𝟑,𝟏

𝟕𝟑𝒙𝟑,𝟐

47𝒙𝟑,𝟑© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API
Resource Assignment Problem (RAP)26© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…1• This line of code imports the Gurobi Python callable library.

27© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…2• Input data
• List of resources and jobs•

The “multidict” function describes thematching score associated witheach possible assignment.

28© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API …3• Declare the resource assignment problem (RAP) model formulation.

29© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…4• Decision variables• Gurobi “tupledict” object x contains the newly created variables.

30© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…5• Job constraints• The job constraint of the Tester position is that either resource 1 (Carlos), resource 2 (Joe), or
resource 3 (Monika) is assigned to this job.
• Constraint (Tester = 1): 𝑥1,1 + 𝑥2,1 + 𝑥3,1 = 1• Constraint (Java Developer = 2): 𝑥1,2 + 𝑥2,2 + 𝑥3,2 = 1• Constraint (Architect = 3): 𝑥1,3 + 𝑥2,3 + 𝑥3,3 = 1

31© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…5• Resource constraints• The constraint for Carlos is that either job 1 (Tester), job 2 (Java Developer ), or job 3 (Architect)is assigned to this resource. Assume #resources ≥ #jobs.
• Constraint (Carlos = 1): 𝑥1,1 + 𝑥1,2 + 𝑥1,3 ≤ 1• Constraint (Joe = 2): 𝑥2,1 + 𝑥2,2 + 𝑥2,3 ≤ 1• Constraint (Monika = 3): 𝑥1,3 + 𝑥2,3 + 𝑥3,3 ≤ 1

32© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…6• Objective function

33•

The objective function is to maximize the total matching score of the assignments that satisfy the job andresource constraints.

•

Maximize total matching score:(53𝑥1,1 +80𝑥2,1 + 53𝑥3,1 ) + (27𝑥1,2 + 47𝑥2,2 + 73𝑥3,2 )+(13𝑥1,3 + 67𝑥2,3 + 47𝑥3,3 ).
Decision Variables

Tester = 1

Java-Developer = 2

Architect = 3

Carlos = 1

𝟓𝟑𝒙𝟏,𝟏

𝟐𝟕𝒙𝟏,𝟐

𝟏𝟑𝒙𝟏,𝟑

Joe = 2𝟖𝟎𝒙𝟐,𝟏

𝟒𝟕𝒙𝟐,𝟐

𝟔𝟕𝒙𝟐,𝟑

Monika = 3

𝟓𝟑𝒙𝟑,𝟏

𝟕𝟑𝒙𝟑,𝟐

47𝒙𝟑,𝟑© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…7•

The “write( )” function prints

the model formulation.

34© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…8• Solving the RAP problem• The “optimize( )” function invokes the optimize method on the model object “m”.

35

© 2019, Gurobi Optimization, LLCLinear Programming Formulation With Gurobi Python API…9
Gurobi Solution of the RAP Problem.

36∙

Solution by Complete Enumeration.

© 2019, Gurobi Optimization, LLC

Jupyter Notebook Demo: RAP 001

37© 2019, Gurobi Optimization, LLC

Perfect Formulation
Resource Assignment Problem (RAP)38© 2019, Gurobi Optimization, LLC

Perfect Formulation – RAP...1• Decision variables (binary): 𝑥𝑟,𝑗 = 1 if resource r is assigned to job j, 0 otherwise.

• The default value of the type variables in the “addVars( )” method is: non-negative andcontinuous. This includes fractional values.

• The optimal solution is:• The values of the assignment variables are binary even though we did not require them to bebinary. Why?
39

© 2019, Gurobi Optimization, LLC

Perfect Formulation – RAP...2• A mathematical optimization problem with decision variables that are non-negative andcontinuous (fractional values), linear constraints, and a linear objective function is called alinear programming (LP) problem.
• The resource assignment problem (RAP) that we formulated is an LP problem.

• The RAP model belongs to a special class of LP problems that guarantees that if all the input
data are integers (RAP: matching scores and the RHS of the job and resource constraints),
then the optimal solution are integer numbers (RAP: optimal solution is defined as binary
numbers).

40© 2019, Gurobi Optimization, LLC

Perfect Formulation – RAP...3• Let’s revise the RAP problem as follows:• There is a fixed cost associated to assigning a resource to a job: 𝐶𝑟,𝑗 .
• There is a limited budget that can be used for assigning resources to jobs: 𝐵
Assignment Costs ($K)

Tester = 1

Java-Developer = 2

Architect = 3

Carlos = 1

𝟏

𝟏

𝟏

Joe = 2𝟐

𝟐

𝟐

Monika = 3

𝟑

𝟑

𝟑

• The budget is $5,000.

41© 2019, Gurobi Optimization, LLC

Perfect Formulation – RAP...4• Jupyter Notebook demo:• Formulate a new mathematical optimization model considering assignment costs and budget
constraint.

42© 2019, Gurobi Optimization, LLC

Methods for Solving MIP Problems
Reference book: Integer Programming, by Michele Conforti, Gérard
Cornuéjols, and Giacomo Zambelli43© 2019, Gurobi Optimization, LLC

Mixed Integer (Linear) Programming (MIP) Models

𝑀𝑎𝑥 𝑐𝑥 + ℎ𝑦
Subject to: 𝐴𝑥 + 𝐺𝑦 ≤ 𝑏

𝑥 ≥ 0 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑦≥044© 2019, Gurobi Optimization, LLC

Graphical Representation of a MIP and a Pure IP
IP solutions

MIP solutions
YY

LP relaxation

LP relaxation

5

5

4

4

3

3

2

2

1

1

X
1

45

2

3

4

5

X
1

© 2019, Gurobi Optimization, LLC

2

3

4

5

Solving MIP Problems• In mathematical programming, the key idea in solving MIP problems is to use the LP
relaxation.
• As we have seen, there are LP problems, such as the assignment problem, for which the
LP relaxation provides integer optimal solutions.
• In the following sections, we will present two methods to solve MIP problems. They arebased on solving a series of LP problem relaxations.
• Branch-and-bound• Cutting planes46© 2019, Gurobi Optimization, LLC

Approach 1: Branch-and-Bound
Methods for Solving MIP Problems
Reference book: Integer Programming, by Michele Conforti, Gérard
Cornuéjols, and Giacomo Zambelli47© 2019, Gurobi Optimization, LLC

Branch-and-Bound Method...1• MIP problem.

𝑀𝑎𝑥 𝑧 = 5.5𝑥1 + 2.1𝑥2
Subject to:1)− 𝑥1 + 𝑥2 ≤ 2
2)
8𝑥1 + 2𝑥2 ≤ 17
𝑥1 , 𝑥2 ≥ 0 and integer• P0 = LP relaxation of MIP problem (i.e., the integrality constraints are removed).
• P0 contains all the integer solutions of the original MIP problem.

48© 2019, Gurobi Optimization, LLC

Graphical Representation of P0 Problem
𝑥2

Integer solutions
Infeasible integer
solutions
Feasibility
direction1) − 𝑥1 + 𝑥2 ≤ 2

3

Objective Function2

𝑧 = 5.5𝑥1 + 2.1𝑥2

P0
1

0

49

The optimal solution of P0,
the LP relaxation of the
MIP problem is:
x1=1.3, x2=3.3.
Objective function value: 14.08

2) 8𝑥1 + 2𝑥2 ≤ 17

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Branch-and-Bound Method...2• Notice that the objective function value (14.08) of P0 is an upper bound to the MIP problem.
• Branching:• The optimal values of the decision variables are fractional (x1 = 1.3 and x2 = 3.3).

• We partition the set of solutions for the problem P0, into two subproblems.
• P1 is the original problem P0 and the constraint x1 ≤ 1.
• P2 is the original problem P0 and the constraint x1 ≥ 2.

• This process of partitioning a problem into subproblems is called branching.

50© 2019, Gurobi Optimization, LLC

Branching of P0 Problem2) 8𝑥1 + 2𝑥2 ≤ 17

𝑥2

Integer solutions
Infeasible integer
solutions
Feasibility
direction1) − 𝑥1 + 𝑥2 ≤ 2

𝑥1 ≤ 1The optimal solution of P0,
x1=1.3, x2=3.3.

32

𝑥1 ≥ 2

P1

Objective Function𝑧 = 5.5𝑥1 + 2.1𝑥2

1

P2
0

51

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Solving Problems P1 and P2
2) 8𝑥1 + 2𝑥2 ≤ 17

𝑥2

Integer solutions
Infeasible integer
solutions
Feasibility
direction1) − 𝑥1 + 𝑥2 ≤ 2

𝑥1 ≤ 1+ Notice that the optimal solution of P0: x1=1.3, x2=3.3
is infeasible for problems P1 and P2, these problems
contain all the integer solutions of the MIP problem, andP1 ∩ P2 = ∅+ The optimal solution of P1: x1=1, x2=3
Objective function value = 11.8
+ The optimal solution of P2: x1=2, x2=0.5
Objective function value = 12.05

32

𝑥1 ≥ 2

P1

Objective Function𝑧 = 5.5𝑥1 + 2.1𝑥2

1

P2
0

52

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Remarks on Solving Problem P1• The optimal solution of the LP relaxation P1 is integer (x1 = 1 and x2 = 3).

• The optimal objective function value of P1 is: 11.8. It is a lower bound of the MIP problem.
• This problem does not need to be explored further.

• We say that this problem is pruned by integrality.

53© 2019, Gurobi Optimization, LLC

Remarks on Solving Problem P2• The optimal solution of the LP relaxation P2 is fractional (x1 = 2 and x2 = 0.5).

• The optimal objective function value of P2 is: 12.05. It is a tighter upper bound of the MIP
problem.
• This optimal solution is not integer; therefore, this problem needs to be explored further.

54© 2019, Gurobi Optimization, LLC

Branch-and-Bound Method...3• Branching of P2 Problem:• The optimal objective function value of P2 is 12.05 > 11.8 (best integer solution found so far).
• X2 = 0.5 ➔ branch on x2.
• We partition the set of solutions of problem P2, into two subproblems.
• P3 is the original problem P2 and the constraint x2 ≤ 0,
• P4 is the original problem P2 and the constraint x2 ≥ 1.

55

© 2019, Gurobi Optimization, LLC

Solving Problem P3𝑥22) 8𝑥1 + 2𝑥2 ≤ 17

Integer solutions
Infeasible integer
solutions
Feasibility
direction+ The optimal solution of P3: x1=2.125, x2=0
Objective function value = 11.6875

32

𝑥1 ≥ 2
Objective Function𝑧 = 5.5𝑥1 + 2.1𝑥2

1

P2
0

56

1

2

𝑥2 ≤ 0𝑥1

P3© 2019, Gurobi Optimization, LLC

Remarks on Solving Problem P3:• The optimal solution of the LP relaxation P3 is fractional (x1 = 2.125 and x2 = 0).

• The optimal objective function value of P3 is: 11.6875.
• Since P3 is an LP relaxation, the value 11.6875 is an upper bound of the integer optimal
solution of any subproblem derived from P3.
• Since 11.6875 < 11.8 (objective function value of the best integer solution found so far),then problem P3 does not require further exploration, and it is considered to be pruned bybound.

57© 2019, Gurobi Optimization, LLC

Solving Problem P4𝑥22) 8𝑥1 + 2𝑥2 ≤ 17

Integer solutions
Infeasible integer
solutions
Feasibility
direction32

𝑥1 ≥ 2P4= ∅𝑥2 ≥ 1

1

Problem P4 is pruned by infeasibility
Objective Function𝑧 = 5.5𝑥1 + 2.1𝑥2

P2
0

58

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Branch-and-Bound method...4• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08

59

x1 ≤ 1x1 ≥ 2P1

P2© 2019, Gurobi Optimization, LLC

Branch-and-Bound Method...5• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08
x1 ≤ 1x1 ≥ 2

P1
Node 1x1 = 1 and x2 = 3
z = 11.8

P2

Pruned by integrality60© 2019, Gurobi Optimization, LLC

Branch-and-Bound Method...6• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08
x1 ≤ 1x1 ≥ 2

P1
Node 1

Node 2x1 = 1 and x2 = 3
z = 11.8

x2 ≤ 0Pruned by integrality
P3

61© 2019, Gurobi Optimization, LLC

P2

x1 = 2 and x2 = 0.5
z = 12.05

x2 ≥ 1

P4

Branch-and-Bound Method...7• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08
x1 ≤ 1x1 ≥ 2

P1
Node 1

Node 2x1 = 1 and x2 = 3
z = 11.8

x2 ≤ 0Pruned by integrality

P2

x1 = 2 and x2 = 0.5
z = 12.05

x2 ≥ 1

P3
Node 3x1 = 2.125, x2 = 0
z = 11.6875
Pruned by bound62© 2019, Gurobi Optimization, LLC

P4

Branch-and-Bound Method...8• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08
x1 ≤ 1x1 ≥ 2

P1
Node 1

Node 2x1 = 1 and x2 = 3
z = 11.8

x2 ≤ 0Pruned by integrality

P2

x1 = 2 and x2 = 0.5
z = 12.05

P3
Node 3x1 = 2.125, x2 = 0
z = 11.6875
Pruned by bound63© 2019, Gurobi Optimization, LLC

x2 ≥ 1
P4

Node 4

Infeasible
Pruned byinfeasibility

Branch-and-Bound Method...9• The branch-and-bound implicit enumeration tree is:
P0
Node 0 x1 = 1.3 and x2 = 3.2

z = 14.08
x1 ≤ 1x1 ≥ 2

P1
Node 1x1 = 1 and x2 = 3
z = 11.8

Node 2

OptimalSolutionx2 ≤ 0Pruned by integrality

P2

x1 = 2 and x2 = 0.5
z = 12.05

P3
Node 3x1 = 2.125, x2 = 0
z = 11.6875
Pruned by bound64© 2019, Gurobi Optimization, LLC

x2 ≥ 1
P4

Node 4

Infeasible
Pruned byinfeasibility

Branch-and-Bound Approach: Final Remarks...1• The branch-and-bound algorithm is based on two principles.
• Branching: partitions the set of solutions of the original MIP into disjoint subproblems.
• Bounding: prunes the implicit enumeration tree.

• The optimal objective function value of any subproblem in the tree is checked against
the current best upper bound of the original MIP and the current best lower bound of
the original MIP.

65

© 2019, Gurobi Optimization, LLC

Branch-and-Bound Approach: Final Remarks...2• The process stops when there are no more subproblems to explore.

• The optimal solution of the MIP problem is the integer solution corresponding to thesubproblem with the current best objective function values.
• Notice that the current best lower bound and current best upper bound of the original
MIP objective function value give us information about how close we are to finding the
optimal solution of the original MIP.
• This is called the optimality gap.

66

© 2019, Gurobi Optimization, LLC

Approach 2: Cutting Planes
Methods for Solving MIP Problems
Reference book: Integer Programming, by Michele Conforti, Gérard Cornuéjols,
and Giacomo Zambelli67© 2019, Gurobi Optimization, LLC

Cutting Planes Approach• MIP problem
𝑀𝑎𝑥 𝑧 = 5.5𝑥1 + 2.1𝑥2

Subject to:−𝑥1 + 𝑥2 ≤ 2
8𝑥1 + 2𝑥2 ≤ 17
𝑥1 , 𝑥2 ≥ 0 and integer• P0 = LP relaxation of MIP problem (i.e., the integrality constraints are removed).
• Similar to branch-and-bound, but rather than imposing restrictions on the fractionalvariables, we generate a series of constraints called Gomory cuts, add them to the
LP relaxation model P0, and re-solve. Cuts do not eliminate integer solutions of the
MIP problem.

68© 2019, Gurobi Optimization, LLC

Graphical Representation of P0 Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible integer
solutions
Feasibility
Direction

The optimal solution of P0,
the LP relaxation of theoriginal MIP problem is:
x1=1.3, x2=3.3.
Objective function value: 14.08

3

2

P0
1

0

69

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Graphical Representation of P0 Problem…2𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible integer
solutions
Feasibility
direction

The optimal solution of P0,
the LP relaxation of theoriginal MIP problem is:
x1=1.3, x2=3.3.
Objective function value: 14.08

3

2

1

0

70

Key idea: Gomory cut removes fractional optimal solutionof P0, while keeping all integer solutions of P0.

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

First Gomory Cut for MIP Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible Integer
solutions
Feasibility
direction

The optimal solution of P1 is:
x1 = 1.375, x2 = 3
Objective function value: 13.8625

03

𝐺1 𝑥2 ≤ 3

2

P1
1

0

71

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Second Gomory Cut for MIP Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible integer
solutions
Feasibility
direction

The optimal solution of P2 is:x1 = 1.5, x2 = 2.5
Objective function value: 13.5

0

3

1

𝐺1 𝑥2 ≤ 3

2

P2
1

𝐺2 𝑥1 + 𝑥2 ≤ 4

0

72

1

𝑥1

2

© 2019, Gurobi Optimization, LLC

Third Gomory Cut for MIP Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible integer
solutions
Feasibility
direction

The optimal solution of P3 is:x1 = 1.75, x2 = 1.5
Objective function value: 12.775

0

3

1

𝐺1 𝑥2 ≤ 3

2

2

P3
1

𝐺2 𝑥1 + 𝑥2 ≤ 4

0

73

1

2

𝐺3 2𝑥1 + 𝑥2 ≤ 5© 2019, Gurobi Optimization, LLC

𝑥1

Fourth Gomory Cut for MIP Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 171.0) − 𝑥1 + 𝑥2 ≤ 2Integer solutions
Infeasible integer
solutions
Feasibility
direction

The optimal solution of P4 is:x1 = 1, x2 = 3
Objective function value: 11.8

0

3

1

𝐺1 𝑥2 ≤ 3

2

3

2

P4
1

𝐺2 𝑥1 + 𝑥2 ≤ 4

0

74

1

2

𝐺4) 3𝑥1 + 𝑥2 ≤ 6

𝐺3 2𝑥1 + 𝑥2 ≤ 5© 2019, Gurobi Optimization, LLC

𝑥1

Solution Space of MIP Problem
𝑥22.0) 8𝑥1 + 2𝑥2 ≤ 17

Integer solutions

1.0) − 𝑥1 + 𝑥2 ≤ 2

Infeasible integer
solutions
Feasibility
direction1.0) − 𝑥1 + 𝑥2 ≤ 2
𝐺4) 3𝑥1 + 𝑥2 ≤ 6

The optimal solution of P4 is:
x1=1, x2=3 integer optimal solution

3

𝑥1 , 𝑥2 ≥ 0

2

P4
1

0

75

1

𝑥1

2

𝐺4) 3𝑥1 + 𝑥2 ≤ 6© 2019, Gurobi Optimization, LLC

Branch-and-Cut Approach• This approach combines the branch-and-bound approach with the cutting planes approach.
• The cutting planes approach is applied before the branching step in the branch-and-boundapproach.
• Frequently multiple rounds of cuts are added at the root problem P0, while fewer or no cutsmight be generated deeper in the branch-and-bound implicit enumeration tree.

76© 2019, Gurobi Optimization, LLC

Final Remarks• Gurobi users formulate MIP problems that are solved by the Gurobi callable library.
• The mathematics and computer science behind Gurobi algorithms are cutting-edge.
• Gurobi has world-class experts in mathematical optimization to solve complex and high-value
combinatorial optimization business problems.
• Gurobi has the best performance in the market.

77© 2019, Gurobi Optimization, LLC

Why MIP Is Better than Simple Heuristics ?
Demo

78

© 2019, Gurobi Optimization, LLC

Conclusions

79© 2019, Gurobi Optimization, LLC

What Have We Covered in This MIP Tutorial?
• Why mixed integer programming (MIP) problems and solvers are important.
• Introduced the Resource Assignment Problem (RAP).

• Demonstrated that simple heuristics can lead to poor assignments. We discussed that enumerating all
possible assignments is practically impossible, since the number of possible assignments is astronomical.

• Formulated the RAP problem as a linear programming (LP) problem.
• Implemented the LP formulation of the RAP using the Gurobi Python API.
• Gave a demo in Jupyter Notebook of the RAP problem implementation using the Gurobi Python
API.
• Discussed that the LP formulation of the RAP always leads to integer solutions.

• Added a constraint to the RAP LP formulation that destroyed RAP problem’s special structure that always
leads to integer solutions.

80© 2019, Gurobi Optimization, LLC

What Have We Covered in This MIP Tutorial?...Continued• The branch-and-bound approach to solving MIP problems.
• The cutting planes approach to solving MIP problems.
• The branch-and-cut approach that combines the branch-and-bound and cutting planes
approaches.

• Why MIP is better than simple heuristics in the context of the RAP problem with a budget
constraint.

81© 2019, Gurobi Optimization, LLC

Summary• George Dantzig, one of the founders of mathematical programming, said:• Mathematical optimization is a methodology that entails three steps:• The formulation of a real problem as a mathematical model.
• The development of algorithms to solve those mathematical models.
• The use of software and hardware to run these algorithms and develop mathematicalprogramming applications.

• The Gurobi Optimizer is the leading mathematical programming solver and incorporates
state-of-the-art algorithms to tackle mathematical optimization models.
• Gurobi Optimization is developing a multitude of modeling examples of mathematicalprogramming applications with the potential to serve as templates to solve optimization
problems in many industries - including certain classes of machine learning problems.

82© 2019, Gurobi Optimization, LLC

Model Building Mathematical
Programming
An Overview

Thank You – Questions?