Integer programming

MGMT 306

Alex L. Wang

Purdue University

What is an integer program?

Motivation for Integer Programming

• In a LP, the variables can be set to any real value including fractional values
• In an Integer Linear Program, we are allowed to constrain variables to be
  • integers: …, -3, -2, -1, 0, 1, 2, 3, …
  • binary: 0 or 1
• Integer programs allow us to model variables that are naturally
  • integers, e.g., # of bikes to make
  • binary, e.g., should we accept a contract yes/no

Integer Linear Program

• An integer linear program (ILP), or integer program (IP) for short, is a model (decision variables, objective function, constraints) where
  • Objective function is linear
  • Some variables are constrained to be integers or binary
  • Remaining constraints are standard form linear constraints

What does an integer program look like?

\[ \begin{aligned} \max\quad& 3x_{1} + 2x_{2}\\ \text{s.t.}\quad& 3x_{1} + x_{2} \leq 9\\ & x_{1} + 3x_{2} \leq 7\\ & -x_{1} + x_{2} \leq 1\\ & x_{1}, x_{2} \geq 0 \text{ and integer}\\ \end{aligned} \]

• Things to notice:
  • Objective function is linear in variables
  • Some constraints of the form \(x_i\) integer or \(x_i\) binary
  • All other constraints are linear

Why do we care about integer programs?

• Compared to LPs, IPs have more modeling power (more accurate models), but are also more difficult to solve

LP Relaxations of IPs

IPs have LP relaxations

• Given an IP, we can relax (drop) the IP constraints to get an LP \[ \begin{aligned} \max\quad& 3x_{1} + 2x_{2}\\ \text{s.t.}\quad& 3x_{1} + x_{2} \leq 9\\ & x_{1} + 3x_{2} \leq 7\\ & -x_{1} + x_{2} \leq 1\\ & x_{1}, x_{2} \geq 0 \text{ and integer} \end{aligned} \]

IPs have LP relaxations

\[ \begin{aligned} \max\quad& 3x_{1} + 2x_{2}\\ \text{s.t.}\quad& 3x_{1} + x_{2} \leq 9\\ & x_{1} + 3x_{2} \leq 7\\ & -x_{1} + x_{2} \leq 1\\ & x_{1}, x_{2} \geq 0 \end{aligned} \]

• The optimal value of the LP relaxation will be better than the optimal value of the IP (larger for maximize, smaller for minimize)
• Rounding the LP optimal solution is not guaranteed to find the ILP optimal solution

Capital budgeting example

Problem Description

• The local parks department would like to construct new rec facilities to encourage citizens to be healthier. It can build at most one of each facility type. They want to maximize expected daily use.
• They have a budget of $800,000 and 13 acres of land.
• We cannot build both the swimming pool and tennis center.
• If a tennis center is built, then a gym must be built.

	Expected daily use	Cost ($)	Land req’d (acres)
Swimming pool	450	300,000	2
Tennis center	150	100,000	3
Athletic field	500	250,000	7
Gymnasium	550	400,000	3

IP Model Variables and Objective Function

• Variables \[\begin{aligned} &S &&\text{whether we build a swimming pool}\\ &T &&\text{whether we build a tennis center}\\ &A &&\text{whether we build an athletic field}\\ &G &&\text{whether we build a gymnasium} \end{aligned}\]
• Objective function \[\max \quad 450 S + 150 T + 500 A + 550 G \quad \text{(expected daily use)}\]

IP Model Constraints

• \(S\), \(T\), \(A\), \(G\) model yes/no decision so: \[S, T, A, G \text{ are binary}\]
• Budget of $800,000 and 13 acres of land: \[\begin{aligned} &300 S + 100 T + 250 A + 400 G \leq 800 &&\text{(budget constraint in \$K)}\\ &2 S + 3 T + 7 A + 3 G \leq 13 &&\text{(acreage constraint)} \end{aligned}\]

IP Model Constraints (continued)

• We cannot build both the swimming pool and tennis center \[S + T \leq 1 \quad\text{(not both swimming pool and tennis center)}\]
• If a tennis center is built, then a gym must be built \[T – G \leq 0 \quad\text{(if tennis center, then gym)}\]

A closer look at logical constraints

• We do not build both the swimming pool and tennis center
• This statement is either satisfied or violated depending on whether we build a pool and whether we build a tennis center
• The \(S\), \(T\) variables each have two possible values
• We want to write a linear constraint on \(S\) and \(T\) that is true exactly when the statement is satisfied

S	T	Statement	\(S+T\leq 1\)
0	0	True	True
0	1	True	True
1	0	True	True
1	1	False	False

A closer look at logical constraints (continued)

• If we build a tennis center, then we also build a gym
• This statement is either satisfied or violated depending on whether we build a tennis center and whether we build a gym
• The \(T\), \(G\) variables each have two possible values
• We want to write a linear constraint on \(T\) and \(G\) that is true exactly when the statement is satisfied

T	G	Statement	\(T - G \leq 0\)
0	0	True	True
0	1	True	True
1	0	False	False
1	1	True	True

Integer Program formulation

\[\begin{aligned} &S &&\text{whether we build a swimming pool}\\ &T &&\text{whether we build a tennis court}\\ &A &&\text{whether we build an athletic field}\\ &G &&\text{whether we build a gymnasium} \end{aligned}\] \[\begin{aligned} \max\quad&450 S + 150 T + 500 A + 550 G &\text{(exp daily use)}\\ \text{s.t.}\quad&300 S + 100 T + 250 A + 400 G \leq 800 &\text{(budg. in \$K)}\\ &2 S + 3 T + 7 A + 3 G \leq 13 &\text{(acreage constraint)}\\ &S + T \leq 1 &\text{(not both S and T)}\\ &T – G \leq 0 &\text{(if T, then G)}\\ &S, T, A, G \text{ are binary} \end{aligned}\]

Spreadsheet Model

• We will set up the Excel spreadsheet just like for a linear program

How to set up Solver for Integer Programs

• Similar to setting up Solver for LP except that you need to add integrality restrictions (“int” or “bin”) on integer variables as shown in the Solver Parameters Box.
• We will use “Simplex LP” with additional options (next slide)

Solver Options for Integer Programs

• In the Solver Options dialogue box, set the Integer Optimality % to 0 as shown to the right.
• With very large IP, this could cause a very long run time to find the optimal solution.
• With the small IP, this will ensure that we get the optimal solution.

Excel usage

• The optimal solution:

Modeling Basic Logical Conditions

What are logical conditions

• A logical statement is a “sentence” that can be either true or false, but not both. There should be no ambiguity.
  • Example: The local parks department built a tennis center.
• A logical constraint requires a logical statement made about some variables to be true.
• Once the variables are fixed, the logical constraint either holds or it does not hold.

Interpreting binary variables as true/false

• Suppose \[ \begin{aligned} &A\quad\text{whether to advertise on Amazon}\\ &B\quad\text{whether to advertise on Bing} \end{aligned} \]

• “We must advertise on Amazon” can be modeled as constraint: \[A = 1\]

• “We may not advertise on Amazon” can be modeled as constraint: \[A = 0\]

Modeling A and B

We must advertise on Amazon and Bing

Truth table

A	B	A and B
0	0	False
0	1	False
1	0	False
1	1	True

Can be modeled as \(\qquad A + B = 2 \qquad\text{or}\qquad A=1,\, B=1\)

Inclusive OR vs. Exclusive OR

• In English, “or” comes in two types “Inclusive or” and “Exclusive or”
  • “To succeed you need talent or hard work”
  • “The meal comes with a side of salad or fries”
• For MGMT 306, “or” is always inclusive unless we explicitly say “exclusive”

Modeling A or B

We must advertise on Amazon or Bing

Truth table

A	B	A or B
0	0	False
0	1	True
1	0	True
1	1	True

Can be modeled as \(\qquad A + B \geq 1\)

Modeling A xor B

We must advertise on either Amazon or Bing exlusively

Truth table

A	B	A xor B
0	0	False
0	1	True
1	0	True
1	1	False

Can be modeled as \(\qquad A + B = 1\)

Modeling If A, then B

If we advertise on Amazon, then we must advertise on Bing

Truth table

A	B	If A, then B
0	0	True
0	1	True
1	0	False
1	1	True

Can be modeled as \(\qquad A \leq B\)

Vehicle routing model

Example of a covering problem

Problem description

• TruckCo wants to choose truck routes to serve 5 cities: A, B, C, D, E

Route no.	Route	Cost
1	A-C-D	10
2	A-D-E	12
3	A-B-E	12
4	B-C-E	13
5	B-D-E	11
6	C-D-E	9
7	A-B	7
8	B-C	8
9	D-E	8

• Write an ILP to cover all cities with minimum cost.

ILP Model

• Decision Variables: \[x_i\qquad\text{whether or not we choose route $i$ for $i = 1,...,9$}\]
• Objective function: \[\min\qquad 10 x_1 + 12 x_2 + 12 x_3 + \dots + 8 x_9\qquad\text{(total cost)}\]
• Constraints: \[\begin{aligned} &x_1 + x_2 + x_3 + x_7 \geq 1 &&\text{(service to city A)}\\ &\dots\\ &x_2 + x_3 + x_4 + x_5 + x_6 + x_9 \geq 1 &&\text{(service to city E)}\\ &x_i \text{ binary for $i=1,\dots,9$} \end{aligned}\]

TruckCo spreadsheet

TruckCo spreadsheet

• Don’t forget to set the binary constraints and to turn the integer optimality to 0%

TruckCo spreadsheet with solution

Logical Constraint Modeling Practice

With a neighbor, write linear constraints modeling the following requirments:

• If Route 1 is picked, Route 2 should be picked
• Routes 3 or 4 should be picked
• At most 3 of Routes 1, 3, 5, 7, 9 should be picked

Fixed cost model

Problem Description

• Franklin clothing company manufactures dresses, shorts and pants
• They do not own their own equipment and must pay a fixed cost to rent the machinery to produce each type of garment

	Labor (hrs)	Cloth (sq. yd.)	Revenue ($)	Rental cost ($/week)
Dresses	3	4	15	200
Shorts	2	3	8	150
Pants	6	4	14	100
Available	150/week	160/week

Problem Description (continued)

• Additional requirements are:
  • If shorts machinery is rented, then at least 40 shorts should be produced per week
  • If pants machinery is rented, then at most 30 dresses should be produced per week
• Formulate an IP whose solution maximizes Franklin’s profit

IP formulation Variables and Objective

• Variables: \[\begin{aligned} &D &&\text{number of dresses to produce/week}\\ &S &&\text{number of shorts to produce/week}\\ &P &&\text{number of pants to produce/week}\\ &R_D &&\text{whether or not we rent dress machinery}\\ &R_S &&\text{whether or not we rent shorts machinery}\\ &R_P &&\text{whether or not we rent pants machinery} \end{aligned}\]

• Objective: \[\max\qquad 15 D + 8 S + 14 P – 200 R_D – 150 R_S – 100 R_P\qquad\text{(total profit)}\]

IP formulation constraints

• Standard “allocation type” constraints \[\begin{aligned} &3 D + 2 S + 6 P \leq 150 &&\text{(labor)}\\ &4 D + 3 S + 4 P \leq 160 &&\text{(cloth)}\\ &D, S, P \geq 0 &&\text{(nonnegativity)} \end{aligned}\]

• Binary/integer constraints \[\begin{aligned} &D,S,P\text{ are integers} &&\text{(Integer constraints)}\\ &R_D,R_S,R_P\text{ are binary} &&\text{(Binary constraints)} \end{aligned}\]

Linking constraints / Big-M constraint

If we do not rent dress machinery, then we may not produce dresses

\[\begin{aligned} &D\geq 0 \text{ and integer}\\ &R_D \text{ binary} \end{aligned} \]

Suppose \(M\) is a big number and consider the constraints

Add \(D\leq M \cdot R_D\)

This works if \(M\) is large enough so we don’t cut off optimal solution

“What is the maximum number of dresses we can produce?”

How to choose M

• In this example, our standard constraints say: \[\begin{aligned} &3 D + 2 S + 6 P \leq 150 &&\text{(labor)}\\ &4 D + 3 S + 4 P \leq 160 &&\text{(cloth)} \end{aligned}\]
  • The labor constraint restricts \(D \leq 50\)
  • The cloth constraint restricts \(D \leq 40\)
• Hence, there is no feasible solution that produces more than 40 dresses.
• So, we can use the linking constraint: \[D – 40 R_D \leq 0\]
• \(D - 50R_D\leq 0\) is technically also correct, but is not as good

Linking constraints practice

• With your neighbor, write the linking constraints for shorts and pants

	Labor (hrs)	Cloth (sq. yd.)	Revenue ($)	Rental cost ($/week)
Dresses	3	4	15	200
Shorts	2	3	8	150
Pants	6	4	14	100
Available	150/week	160/week

IP Formulation Recap

• Objective: \[\max\qquad 15 D + 8 S + 14 P – 200 R_D – 150 R_S – 100 R_P\qquad\text{(total profit)}\]

• Constraints \[\begin{aligned} &3 D + 2 S + 6 P \leq 150 &&\text{(labor)}\\ &4 D + 3 S + 4 P \leq 160 &&\text{(cloth)}\\ &D – 40 R_D \leq 0 &&\text{(linking constraint dresses)}\\ &S – 53 R_S \leq 0 &&\text{(linking constraint shorts)}\\ & P – 25 R_P \leq 0 &&\text{(linking constraint pants)}\\ &D,S,P\geq 0\text{ and integer}\\ &R_D,R_S,R_P\text{ are binary} \end{aligned}\]

• Still missing: two logical constraints

Logical constraint 1

If shorts machinery, then at least 40 shorts should be produced per week

\[\begin{aligned} &S\leq 53 R_S\\ &S\geq 0 \text{ and integer}\\ &R_S \text{ binary} \end{aligned} \]

Add: \[S \geq 40 R_S\]

Logical constraint 2

If pants machinery is rented, then at most 30 dresses should be produced per week.

\[\begin{aligned} &D\geq 0 \text{ and integer}\\ &R_P \text{ binary} \end{aligned} \]

Add: \[D \leq 40 - 10R_P\]

This works since we know that \(D\leq 50\) at an optimal solution

Completed IP Model

\[\begin{aligned} \max\qquad &15 D + 8 S + 14 P – 200 R_D – 150 R_S – 100 R_P&&\text{(total profit)}\\ \text{s.t.}\qquad&3 D + 2 S + 6 P \leq 150 &&\text{(labor)}\\ &4 D + 3 S + 4 P \leq 160 &&\text{(cloth)}\\ &D – 40 R_D \leq 0 &&\text{(linking dresses)}\\ &S – 53 R_S \leq 0 &&\text{(linking shorts)}\\ & P – 25 R_P \leq 0 &&\text{(linking pants)}\\ & S - 40 R_S \geq 0 &&\text{(logical 1)}\\ & D + 10 R_P \leq 50 && \text{(logical 2)}\\ &D,S,P\geq 0\text{ and integer}\\ &R_D,R_S,R_P\text{ are binary} \end{aligned}\]

Spreadsheet model

Solver settings

Variation on Big-M/Linking Constraints

• In some problems, one binary decision might control multiple other variables
• E.g., suppose dresses and shorts are produced using the same machine

New variable: \[ R_\text{special}\qquad\text{whether to rent special machinery} \]

Constraints: \[\begin{aligned} &D + S \leq 93 R_\text{special}\\ &R_\text{special} \text{ binary} \end{aligned}\]

Building Compound Logical Constraints

Negations

Suppose \[ \begin{aligned} &A\quad\text{whether to advertise on Amazon}\\ &B\quad\text{whether to advertise on Bing}\\ &C\quad\text{whether to advertise on Comcast}\\ &D\quad\text{whether to advertise on DuckDuckGo} \end{aligned} \]

• \(A\) is a binary variable representing “We advertise on Amazon”
• \((1-A)\) is a binary variable representing “We do not advertise on Amazon”

Compound if-then statements

Four rules:

• If A and B and C, then D
• If A or B or C, then D
• If A, then B and C and D
• If A, then B or C or D

If-then statements with ANDs in the IF clause

If A and B and C, then D

• What do we need to rule out? \(A=1,B=1,C=1,D=0\)
• \(A + B + C - 2 \leq D\)

If A and B, then C

• What do we need to rule out? \(A=1,B=1,C=0\)
• \(A + B - 1 \leq C\)

If-then statements with ORs in the IF clause

If A or B or C, then D

• An “or” in the “if” clause splits
• This statement is equivalent to three separate constraints:
  • If A, then D
  • If B, then D
  • If C, then D
• Each can be modeled using a linear constraint
  • \(A \leq D\)
  • \(B \leq D\)
  • \(C \leq D\)

If-then statements with ANDs in the THEN clause

If A, then B and C and D

• An “and” in the “then” clause splits
• This statement is equivalent to three separate constraints:
  • If A, then B
  • If A, then C
  • If A, then D
• Each can be modeled using a linear constraint
  • \(A \leq B\)
  • \(A \leq C\)
  • \(A \leq D\)

If-then statements with ORs in the THEN clause

If A, then B or C or D

• Equivalently, if A is (1) true, then at least one of B, C, or D must be (1) true
• \(A \leq B + C + D\)

Practice

• Write linear constraints modeling the logical constraints:
  • If we advertise on Amazon, we may not advertise on Bing
  • If we advertise on Amazon or if we do not on advertise on Bing, then we must advertise on Comcast
  • If We advertise on Amazon and Bing, then we must advertise on Comcast and not DuckDuckGo

Assignment model

Problem Description

• Do-it-All Tailoring has four tailors and four garments to make. The estimated time (in hours) it would take each tailor to make each garment is listed below.
• Dtermine the assignment of tailors to garments so that the total working time is minimized
• Assignment means: each garment must be worked on by exactly one tailor, each tailor must work on at most one garment.

	Tailor 1	Tailor 2	Tailor 3	Tailor 4
1. Wedding gown	19	15	20	21
2. Clown costume	11	14	16	12
3. Admiral’s uniform	12	8	11	13
4. Bullfighter outfit	15	20	17	18

ILP Model Variables and Objective

• Decision Variables \[\begin{aligned} x_{i,j} \qquad&\text{whether garment $i$ is assigned to tailor $j$}\\ &\text{for $i=1,2,3,4$ and $j=1,2,3,4$} \end{aligned}\]

• Objective function \[\min\qquad 19 x_{1,1} + 15 x_{1,2} + 20 x_{1,3} + \dots + 18 x_{4,4}\qquad\text{(total time)}\]

• Constraints: \[x_{i,j} \text{ binary for $i=1,\dots,4$ and $j=1,\dots,4$}\]

ILP Model Assignment Constraints

• Exactly one tailor per garment \[\begin{aligned} x_{1,1} + x_{1,2} + x_{1,3} + x_{1,4} = 1\\ x_{2,1} + x_{2,2} + x_{2,3} + x_{2,4} = 1\\ x_{3,1} + x_{3,2} + x_{3,3} + x_{3,4} = 1\\ x_{4,1} + x_{4,2} + x_{4,3} + x_{4,4} = 1 \end{aligned}\] or equivalently \[\sum_{j=1}^4 x_{i,j}=1 \qquad\text{for $i=1,\dots,4$}\]

ILP Model Assingment Constraints Continued

• At most one garment per tailor \[\begin{aligned} x_{1,1} + x_{2,1} + x_{3,1} + x_{4,1} \leq 1\\ x_{1,2} + x_{2,2} + x_{3,2} + x_{4,2} \leq 1\\ x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} \leq 1\\ x_{1,4} + x_{2,4} + x_{3,4} + x_{4,4} \leq 1 \end{aligned}\] or equivalently \[\sum_{i=1}^4 x_{i,j}\leq1 \qquad\text{for $j=1,\dots,4$}\]
• Note: Since we have the same number of garments and tailors, we can change these \(\leq\) constraints to \(=\) constraints

Solved Excel Model

Excel Solver Setup

Solved Excel Model

Modification

• How would we change the model if Tailor 2 cannot make the wedding gown (Job 1)?
• Two ways:
  • Add constraint \(x_{1,2}=0\)
  • Set the time cost of \(x_{1,2}\) so high that the optimal solution never wants to assign wedding gown to tailor 2
• Both options are valid

Fixed-cost assignment problem

This combines ideas from “assignment problems” but now adds fixed costs

Problem Description

• Jackie and Casey are planning a very large wedding and need to decide on caterers and meals.
• Including themselves, there will be 50 vegetarian guests, 20 gluten-sensitive guests, and 75 lactose intolerant guests.
• There are three catering companies: (1) Star, (2) Big Blue, and (3) Unique Creations.
• Each caterer charges a flat fee just to show up plus a price per guest depending on the different menus. Each caterer has a maximum number of guests they can serve.
• Formulate an Integer Program to decide which caterers to hire (possibly multiple) and how many of each dish to order from each caterer to feed all their guests and to minimize costs.

Problem Data

Caterer	Flat Fee ($)	Capacity (meals)	Vegetarian ($/meal)	Gluten-Free ($/meal)	Dairy-Free ($/meal)
Star	250	120 meals	55	55	60
Big Blue	200	125 meals	60	40	50
Unique Creations	150	65 meals	120	40	30

ILP Model Variable and Objective

• Variables \[\begin{aligned} x_i \qquad&\text{whether to hire caterer $i$ for $i=1,2,3$}\\ y_{i,j} \qquad&\text{number of caterer $i$'s menu $j$ to order}\\ &\text{for $i=1,2,3$ and $j=1,2,3$} \end{aligned}\]

• Objective \[\begin{aligned} \min\qquad &250 x_1 + 200 x_2 + 150 x_3\\ & + \bigg( 55 y_{1,1} + 55 y_{1,2} + 60 y_{1,3} + \dots + 30 y_{3,3}\bigg)\end{aligned}\qquad \text{(total cost)}\]

ILP Model Constraints

• Hiring is binary \[x_i \text{ binary for $i=1,2,3$}\]
• Number of meals is nonnegative and integer \[y_{i,j}\geq 0 \text{ and integer for $i=1,2,3$ and $j=1,2,3$}\]
• Linking constraints \[\begin{aligned} y_{1,1} + y_{1,2} + y_{1,3} \leq 120 x_1\\ y_{2,1} + y_{2,2} + y_{2,3} \leq 125 x_2\\ y_{3,1} + y_{3,2} + y_{3,3} \leq 65 x_3 \end{aligned}\]

ILP Model Constraints

• Need to feed all guests \[\begin{aligned} y_{1,1} + y_{2,1} + y_{3,1} = 50\\ y_{1,2} + y_{2,2} + y_{3,2} = 20\\ y_{1,3} + y_{2,3} + y_{3,3} = 75 \end{aligned}\]

Spreadsheet setup

Spreadsheet formulas

Spreadsheet Solver Settings

Spreadsheet Completed