UNIT-10

Integer programming
 Integer Linear Programming
Problem
• Types of Integer Linear Programming Models

• Graphical and Computer Solutions for an All-Integer Linear

Programming

• Applications Involving 0-1 Variables

• Modeling Flexibility Provided by 0-1 Variables

 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.
 Example 1: All-Integer LP
• Consider the following all-integer linear program:
 Example 1: All-Integer LP
• 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
 Example 1: All-Integer LP
• LP Relaxation
 Example 1: All-Integer LP
• 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.
 Example 1: All-Integer LP
• Rounded Up Solution
 Example 1: All-Integer LP
• 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 two slides.
 Example 1: All-Integer LP
• Complete Enumeration of Feasible ILP Solutions
 Example 1: All-Integer LP
• Optimal All-Integer Solution
 Example 2: 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 as follows:
 Example 2: Capital Budgeting
 Decision Variables

The four 0-1 decision variables are as follows:

P = 1 if the plant expansion project is accepted;
0 if rejected

W = 1 if the warehouse expansion project is accepted;

0 if rejected

M = 1 if the new machinery project is accepted;

0 if rejected

R = 1 if the new product research project is accepted;

0 if rejected
 Example 2: Capital Budgeting
 In a capital budgeting problem, the company aims to maximize the net present
value of capital budgeting projects.

 Problem Formulation
Max 90P + 40W + 10M + 37R
s.t. 15P + 10W + 10M + 15R < 40 (Yr. 1 capital avail.)
20P + 15W + 10R < 50 (Yr. 2 capital avail.
20P + 20W + 10R < 40 (Yr. 3 capital avail.)
15P + 5W + 4M + 10R < 35 (Yr. 4 capital avail.)
P, W, M, R = 0, 1
 Example 2: Capital Budgeting
 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.
Example 3: Fixed Cost(0r Charged)
Problem
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 is a blend of 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 is a blend
of 0.6 tons of material 1, 0.1 tons of material 2, and 0.3 tons of material 3.
 Example 3: Fixed Cost
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.

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
 Example 3: Fixed Cost
 Decision Variables:

F = tons of fuel additive produced

S = tons of solvent base produced
C = tons of carpet cleaning fluid produced

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
 Example 3: Fixed Cost
 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 - 50SF < 0 (Max. C)

F, S, C > 0; SF, SS, SC = 0 or 1

 Example 3: Fixed Cost
 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.
 Example 4: Distribution System 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.
 Example 4: Distribution System Design

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
 Example 4: Distribution System Design

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
 Example 4: Distribution System Design

The shipping cost per unit from each plant to each distribution center is
shown below.
 Example 4: Distribution System Design
 Decision Variables
y1 = 1 if a plant is constructed in Detroit;
0 if not
y2 = 1 if a plant is constructed in Toledo;
0 if not
y3 = 1 if a plant is constructed in Denver;
0 if not
y4 = 1 if a plant is constructed in Kansas City;
0 if not
xij = the units shipped (in 1000s) from plant i to
distribution center j , with i = 1, 2, 3, 4, 5 and
j = 1, 2, 3
 Example 4: Distribution System Design

• Problem Formulation
 Example 4: Distribution System Design

 Optimal Solution
Construct a plant in Kansas City (y4 = 1).

20,000 units will be shipped from Kansas City to Atlanta (x42 = 20), 20,000
units will be shipped from Kansas City to Houston (x43 = 20), and 30,000 units will
be shipped from St. Louis to Boston (x51 = 30).

The total cost of this solution including the fixed cost of $500,000 for the
plant in Kansas City is $860,000.
 Example 5: 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.
 Example 5: Bank Location
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.
Example 5: Bank Location
 Example 5: Bank Location
Decision Variables

xi = 1 if a PBB is established in county i;

0 otherwise
Problem Formulation
 Example 5: Bank Location
this 20-variable, 20-constraint problem:
 Optimal Solution

For this 20-variable, 20-constraint problem:

Establish PPBs in Ashland, Stark, and 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.
ou in these three counties, Ohio Trust can place branch banks in all 20 ci.)
All other decision variables have an optimal value of zero, indicating that a PPB
should not be placed in these counties.
Example 6: Product Design & Market
Share
Market Pulse Research has conducted a study for Lucas Furniture on some
designs for a new commercial office desk. Three attributes were found to be
most influential in determining which desk is most desirable: number of file
drawers, the presence or absence of pullout writing boards, and simulated wood
or solid color finish. Listed on the next slide are the part-worths for each level of
each attribute provided by a sample of 7 potential Lucas customers.
 Example 7: Metropolitan
Microwaves
Metropolitan Microwaves, Inc. is planning to expand its sales operation
by offering other electronic appliances. The company has identified
seven new product lines it can carry. Relevant information about each
line follows on the next slide.
 Example 7: Metropolitan
Microwaves
Initial Floor Space Exp. Rate
Product Line Invest. ([Link].) of Return
1. TV/VCRs $ 6,000 125 8.1%
2. TVs 12,000 150 9.0
3. Projection TVs 20,000 200 11.0
4. VCRs 14,000 40 10.2
5. DVD Players 15,000 40 10.5
6. Video Games 2,000 20 14.1
7. Home Computers 32,000 100 13.2
 Example 7: Metropolitan
Microwaves
Metropolitan has decided that they should not stock projection TVs
unless they stock either TV/VCRs or TVs. Also, they will not stock both
VCRs and DVD players, and they will stock video games if they stock
TVs. Finally, the company wishes to introduce at least three new
product lines.

If the company has $45,000 to invest and 420 sq. ft. of floor space
available, formulate an integer linear program for Metropolitan to
maximize its overall expected return.
 Example 7: Metropolitan
Microwaves
• Define the Decision Variables
xj = 1 if product line j is introduced;
= 0 otherwise.
where:
Product line 1 = TV/VCRs
Product line 2 = TVs
Product line 3 = Projection TVs
Product line 4 = VCRs
Product line 5 = DVD Players
Product line 6 = Video Games
Product line 7 = Home Computers
 Example 7: Metropolitan
Microwaves
 Define the Decision Variables
xj = 1 if product line j is introduced;
= 0 otherwise.
 Define
the Objective Function
Maximize total expected return:
Max .081(6000)x1 + .09(12000)x2 + .11(20000)x3
+ .102(14000)x4 + .105(15000)x5 + .141(2000)x6
+ .132(32000)x7
 Example 7: Metropolitan
Microwaves
• Define the Constraints
1) Money:
6x1 + 12x2 + 20x3 + 14x4 + 15x5 + 2x6 + 32x7 < 45

2) Space:
125x1 +150x2 +200x3 +40x4 +40x5 +20x6 +100x7 < 420

3) Stock projection TVs only if stock TV/VCRs or TVs:

x1 + x2 > x3 or x1 + x2 - x3 > 0
 Example 7: Metropolitan
Microwaves
• Define the Constraints (continued)
4) Do not stock both VCRs and DVD players:
x4 + x5 < 1
5) Stock video games if they stock TV's:
x2 - x6 > 0
6) Introduce at least 3 new lines:
x1 + x2 + x3 + x4 + x5 + x6 + x7 > 3
7) Variables are 0 or 1:
xj = 0 or 1 for j = 1, , , 7
 Example 7: Metropolitan
Microwaves
• Optimal Solution

Introduce:
TV/VCRs, Projection TVs, and DVD Players

Do Not Introduce:
TVs, VCRs, Video Games, and Home Computers

Total Expected Return:

$4,261
EXAMPLE-8
A manufacturing firm contracts a logistics firm to transport its products to
Mumbai port. The total weight of the materials that are to be transported is
36T. Since each truck can carry at the maximum 20T, the idea is to contract
two trucks from the logistics firm. It is well known that the fuel consumed by
the trucks is directly proportional to the weight they carry and a truck which
carries a larger weight (say 23T) will stop for frequent fuel refilling over a
truck that carries lesser weight (say 13T). Since frequent stoppings will delay
the heavier truck, it is intended that the firm wishes that both the trucks
carry more or less the same weight, so that they reach the port at more or
less the same time together. Formulate an integer programming model to
address this need. The details of the materials to be transported are given
below (do not solve the problem)
CONTINUED…..
Material Weight(T)

1 7

2 5

3 8

4 4

5 3

6 4

7 3

8 2
 Cautionary Note About Sensitivity
Analysis
• Sensitivity analysis often is more crucial for ILP problems than for LP
problems.

• A small change in a constraint coefficient can cause a relatively large

change in the optimal solution.

• Recommendation: Resolve the ILP problem several times with slight

variations in the coefficients before choosing the “best” solution for
implementation.