Introduction to Integer Programming

Problem

Dr. Vandana
Decision Sciences

14-11-2024 Dr. Vandana 1

Integer Linear Programming

• Types of Integer Linear Programming Models

• Graphical and Computer Solutions for an All-Integer Linear Program
• Applications Involving 0-1 Variables
• Modeling Flexibility Provided by 0-1 Variables

14-11-2024 Dr. Vandana 2

Types of Integer Programming Models

• An LP in which all the variables are restricted to be integers is called an

all-integer linear program (ILP).
• The LP that results from dropping the integer requirements is called the
LP Relaxation of the ILP.
• If only a subset of the variables are restricted to be integers, the problem
is called a mixed-integer linear program (MILP).
• Binary variables are variables whose values are restricted to be 0 or 1.
If all variables are restricted to be 0 or 1, the problem is called a 0-1 or
binary integer linear program.

14-11-2024 Dr. Vandana 3

Example

• Consider the following all-integer linear program:

Max 3x1 + 2x2

s.t. 3x1 + x2 < 9

x1 + 3x2 < 7
-x1 + x2 < 1

x1, x2 > 0 and integer

14-11-2024 Dr. Vandana 4

Example-All Integer Programming Problem

• LP Relaxation
Solving the problem as a linear program ignoring the integer
constraints, the optimal solution to the linear program gives fractional
values for both x1 and x2. From the graph on the next slide, we see that
the optimal solution to the linear program is:

x1 = 2.5, x2 = 1.5,
Max 3x1 + 2x2 = 10.5

14-11-2024 Dr. Vandana 5

Cont…

14-11-2024 Dr. Vandana 6

Cont…

• Rounding Up
If we round up the fractional solution (x1 = 2.5, x2 = 1.5) to the LP
relaxation problem, we get x1 = 3 and x2 = 2. From the graph on the next
slide, we see that this point lies outside the feasible region, making this
solution infeasible.

14-11-2024 Dr. Vandana 7

Cont…

14-11-2024 Dr. Vandana 8

Cont…

• Rounding Down
• By rounding the optimal solution down to x1 = 2, x2 = 1, we see that this
solution indeed is an integer solution within the feasible region, and
substituting in the objective function, it gives 3x1 + 2x2 = 8.

• We have found a feasible all-integer solution, but have we found the

OPTIMAL all-integer solution?
---------------------
• The answer is NO! The optimal solution is x1 = 3 and x2 = 0 giving 3x1
+ 2x2 = 9, as evidenced in the next slides.

14-11-2024 Dr. Vandana 9

Cont…

• Complete Enumeration of Feasible ILP Solutions

There are eight feasible integer solutions to this problem:
x1 x2 3x1 + 2x2
1. 0 0 0
2. 1 0 3
3. 2 0 6
4. 3 0 9 optimal solution
5. 0 1 2
6. 1 1 5
7. 2 1 8
8. 1 2 7

14-11-2024 Dr. Vandana 10

Cont…

14-11-2024 Dr. Vandana 11

Example 2

Eastborne Realty has $2 million available for the purchase of new rental property. After
an initial screening, Eastborne reduced the investment alternatives to townhouses and
apartment buildings. Each townhouse can be purchased for $282,000, and five are
available. Each apartment building can be purchased for $400,000, and the developer will
construct as many buildings as Eastborne wants to purchase.

Eastborne’s property manager can devote up to 140 hours per month to these new
properties; each townhouse is expected to require 4 hours per month, and each apartment
building is expected to require 40 hours per month. The annual cash flow, after deducting
mortgage payments and operating expenses, is estimated to be $10,000 per townhouse
and $15,000 per apartment building. Eastborne’s owner would like to determine the
number of townhouses and the number of apartment buildings to purchase to maximize
annual cash flow. We begin by defining the decision variables as follows:

14-11-2024 Dr. Vandana 12

Example 2

13

14-11-2024 Dr. Vandana

Example 2

14

14-11-2024 Dr. Vandana

 0-1 integer programming

0-1 integer programming (which can also be written as '0-1'

integer programming) is a mathematical method of using a
series of binary functions.

in particular, yes ('1') and no ('0') answers to arrive at a solution

when there are two mutually exclusive options.

14-11-2024 Dr. Vandana 15

Example: Capital Budgeting
The Ice-Cold Refrigerator Company is considering investing in several
projects that have varying capital requirements over the next four
years. Faced with limited capital each year, management would like
to select the most profitable projects. The estimated net present
value for each project, the capital requirements, and the available
capital over the four-year period are shown on the next slide.

14-11-2024 Dr. Vandana 16

Cont…

14-11-2024 Dr. Vandana 17

Cont…

Decision Variables

The four 0-1 decision variables are as follows:

P = 1 if the plant expansion project is selected;

0 if rejected
W = 1 if the warehouse expansion project is selected;
0 if rejected
M = 1 if the new machinery project is selected;
0 if rejected
R = 1 if the new product research project is selected;
0 if rejected

14-11-2024 Dr. Vandana 18

Cont…

• In a capital budgeting problem, the company’s objective function is to maximize

the net present value of capital budgeting projects. This problem has four
constraints: one for the funds available in each of the next four years. A 0-1 integer
linear programming model with dollars in thousands is as follows:

14-11-2024 Dr. Vandana 19

 Optimal Solution
• P = 1, W = 1, M = 1, R = 0.
• Total estimated net present value = $140,000

• The company should fund the plant expansion, the warehouse expansion, and
the new machinery projects. The new product research project should be put on
hold unless additional capital funds become available.

• The company will have $5,000 remaining in year 1, $15,000 remaining in year
2, and $11,000 remaining in year 4. Additional capital funds of $10,000 in
year 1 and $10,000 in year 3 will be needed to fund the new product research
project.

14-11-2024 Dr. Vandana 20

Example: Fixed Cost
Three raw materials are used to produce 3 products: a fuel additive, a solvent base,
and a carpet cleaning fluid. The profit contributions are $40 per ton for the fuel
additive, $30 per ton for the solvent base, and $50 per ton for the carpet cleaning
fluid.
Each ton of fuel additive required 0.4 tons of material 1 and 0.6 tons of material 3.
Each ton of solvent base requires 0.5 tons of material 1, 0.2 tons of material 2, and
0.3 tons of material 3. Each ton of carpet cleaning fluid required 0.6 tons of
material 1, 0.1 tons of material 2, and 0.3 tons of material 3.
RMC has 20 tons of material 1, 5 tons of material 2, and 21 tons of material 3, and
is interested in determining the optimal production quantities for the upcoming
planning period.

14-11-2024 Dr. Vandana 21

Example: Fixed Cost

14-11-2024 Dr. Vandana 22

Example: Fixed Cost

The optimal solution consists of 27.5 tons of fuel additive, 0 tons of solvent
base, and 15 tons of carpet cleaning fluid, with a value of $1850.

14-11-2024 Dr. Vandana 23

Cont…

There is a fixed cost for production setup of the products, as well as a

maximum production quantity for each of the three products.

Product Setup Cost Maximum Production

Fuel additive $200 50 tons
Solvent base $ 50 25 tons
Cleaning fluid $400 40 tons

14-11-2024 Dr. Vandana 24

Cont…

Decision Variables

SF = 1 if the fuel additive is produced; 0 if not

SS = 1 if the solvent base is produced; 0 if not
SC = 1 if the cleaning fluid is produced; 0 if not

These binary variables allow the model to account for setup costs and enforce
production limits only when a product is actually produced. Without them, the
model would not be able to conditionally apply setup costs or control
production limits based on whether or not a product is being produced.

14-11-2024 Dr. Vandana 25

Cont…
Problem Formulation

Max 40F + 30S + 50C – 200SF – 50SS – 400SC

s.t. 0.4F + 0.5S + 0.6C < 20 (Mat’l. 1)

0.2S + 0.1C < 5 (Mat’l. 2)
0.6F + 0.3S + 0.3C < 21 (Mat’l. 3)
F - 50SF < 0 (Max.F)
S - 25SS < 0 (Max. S)
C - 40SC < 0 (Max. C)
F, S, C > 0; SF, SS, SC = 0, 1

14-11-2024 Dr. Vandana 26

Cont…

Optimal Solution
Produce 25 tons of fuel additive.
Produce 20 tons of solvent base.
Produce 0 tons of cleaning fluid.

The value of the objective function after deducting the setup cost is $1350. The
setup cost for the fuel additive and the solvent base is $200 + $50 = $250.
The optimal solution shows SC = 0, which indicates that the more expensive $400
setup cost for the carpet cleaning fluid should be avoided.

14-11-2024 Dr. Vandana 27

Example: Supply Chain Design

The Martin-Beck Company operates a plant in St. Louis with an annual

capacity of 30,000 units. Product is shipped to regional distribution
centers located in Boston, Atlanta, and Houston. Because of an
anticipated increase in demand, Martin-Beck plans to increase capacity
by constructing a new plant in one or more of the following cities:
Detroit, Toledo, Denver, or Kansas City.

14-11-2024 Dr. Vandana 28

Cont…

The estimated annual fixed cost and the annual capacity for the four proposed
plants are as follows:

Proposed Plant Annual Fixed Cost Annual Capacity

Detroit $175,000 10,000
Toledo $300,000 20,000
Denver $375,000 30,000
Kansas City $500,000 40,000

14-11-2024 Dr. Vandana 29

Cont…

The company’s long-range planning group developed forecasts of the

anticipated annual demand at the distribution centers as follows:

Distribution Center Annual Demand

Boston 30,000
Atlanta 20,000
Houston 20,000

14-11-2024 Dr. Vandana 30

Cont…

The shipping cost per unit from each plant to each distribution center is
shown below.

14-11-2024 Dr. Vandana 31

Cont…

14-11-2024 Dr. Vandana 32

14-11-2024 Dr. Vandana 33
Cont…

14-11-2024 Dr. Vandana 34

Cont…

14-11-2024 Dr. Vandana 35

Cont…

14-11-2024 Dr. Vandana 36

Cont…

14-11-2024 Dr. Vandana 37

Problem Statement

14-11-2024 Dr. Vandana 38

Optimal Solution

Optimal Solution

Construct plant in Kansas City (y4 = 1).

Ship 20,000 units: Kansas City to Atlanta (x42 = 20), Ship 20,000 units:
Kansas City to Houston (x43 = 20), Ship 30,000 units: St. Louis to Boston
(x51 = 30).
Total cost: $860,000 including fixed cost of $500,000.

14-11-2024 Dr. Vandana 39

Bank Location

The long-range planning department for the Ohio Trust Company is considering
expanding its operation into a 20-county region in northeastern Ohio. Ohio
Trust does not have, at this time, a principal place of business in any of the 20
counties.
According to the banking laws in Ohio, if a bank establishes a principal place of
business (PPB) in any county, branch banks can be established in that county
and in any adjacent county. To establish a new PPB, Ohio Trust must either
obtain approval for a new bank from the state’s superintendent of banks or
purchase an existing bank.

14-11-2024 Dr. Vandana 40

14-11-2024 Dr. Vandana 41
 Cont…

The 20 counties in the region and adjacent counties are listed on the next
slide. For example, Ashtabula County is adjacent to Lake, Geauga, and
Trumbull counties; Lake County is adjacent to Ashtabula, Cuyahoga, and
Geauga counties; and so on.

As an initial step in its planning, Ohio Trust would like to determine the
minimum number of PPBs necessary to do business throughout the 20-
county region. A 0-1 integer programming model can be used to solve
this location problem for Ohio Trust.

14-11-2024 Dr. Vandana 42

14-11-2024 Dr. Vandana 43
Cont…

14-11-2024 Dr. Vandana 44

Cont…

14-11-2024 Dr. Vandana 45

Cont…

14-11-2024 Dr. Vandana 46

Cont…

14-11-2024 Dr. Vandana 47

Cont…

Optimal Solution
For this 20-variable, 20-constraint problem:

Establish PPBs in Ashland, Stark, Geauga counties.

(With PPBs in these three counties, Ohio Trust can place branch banks
in all 20 counties.)
All other decision variables have an optimal value of zero, indicating that
a PPB should not be placed in these counties.

14-11-2024 Dr. Vandana 48