Module

INTEGER LINEAR PROGRAMMING

6
OBJECTIVES:
At the end of this module, you are expected to accomplish the following:

1. Be familiar with the idea of integer linear programming;

2. Describe the various kinds of integer linear programming models;
3. Identify and solve various integer linear programming models.

OVERVIEW
We will talk about a category of problems that are demonstrated as linear
programs in this module, with the other restriction that either all or some of the decision
variables are needed to be integer(s).
Additional modeling flexibility is offered by the inclusion of integer variables,
particularly 0-1 integer variables. Because of this, there are more practical applications
that the linear programming framework can handle. An application for employee
scheduling, for instance, is described in the Management Science in Action: Scheduling
Employees at McDonald's Restaurants. The increased modeling flexibility comes at
the expense of problems involving integer variables typically being much more
challenging to solve. Despite the fact that commercial linear programming programs
can routinely solve linear programming problems with thousands of continuous
variables, solving all-integer programming problems with fewer than 100 variables can
be very challenging. The types of integer linear programs that are simplest to solve
may typically be determined by experienced quantitative analysts; in such
circumstances, problems involving hundreds or even thousands of 0-1 integer variables
can be solved using existing computer codes. There are now spreadsheets with integer
capabilities. For instance, integer problems can be solved using Microsoft Excel's
standard edition.
A brief section outlining the many categories of integer linear programming
models comes first. In the unit that follows, we present a real-world scenario that calls
for the creation of an all-integer linear program. We go over some scenarios where 0–
1 integer variable is used. Additional modeling practice including the generation of
models with integer variables is the objective. Our attention is on applications, not on
the specifics of the solution process.
 Definitions
The linear programming paradigm serves as the mathematical foundation for integer
programming, with the additional requirement that the variables only have integer values
(Taha, 2007).
Minimize 𝑐𝑇𝑥
Subject to 𝐴𝑥 ≤ 𝑏, 𝐺𝑥 = 𝑑
𝑥 ∈ Ζ𝑛

TYPES OF INTEGER LINEAR PROGRAMMING (ILP) MODELS:

 Mixed Integer Linear Programming (MILP) – The assumption of divisibility is
satisfied for the remainder of the variables as just some of them must have integer
values.
 Pure Integer Linear Programming (PILP) – Integer values must be present for every
variable.
 Binary Integer Linear Programming (BILP) – IP problems that only use binary
variables or numbers 0 or 1 (also known as 0-1 integer programming).

Integer linear programming is primarily studied for two reasons. Firstly, many
applications do not allow fractional values of the decision variables. Methods for determining
the ideal integer answer are required since rounding the linear programming solution can lead
to subpar outcomes. Studying integer linear programming is also important since it allows for
more flexible modeling by using 0–1 variable.

OR Application

Scheduling Employees at McDonald’s Restaurants

The owner and operator of four McDonald’s restaurants in the Cumberland, Marylan, area was spending
more than eight hours every week manually preparing employee work schedules. He had to forecast sales
by hour and then convert the hourly forecasts into personnel requirements for the grill, counter, and drive-
thru work areas. Then, he had to match the employees available work hours and job skills with the hourly
requirements to develop a work schedule for each employee. The scheduling process is further complicated
by the following: Employee needs vary dramatically over the course of each day, the fast food industry has
no standard work shifts, the availability of students and other part-time employee is limited, and employee
qualifications vary.

A typical McDonald’s restaurant has three work areas (grill, counter, and drive-thru), 150
employees, and 30 work shifts. A complete integer linear programming model for scheduling employees
in this situation would involve approximately 100,000 integer variables and 3000 constraints. The
company’s management wanted to obtain a solution in 15 minutes or less on a personal computer, so using
the complete model to obtain a solution was impossible. As a result, a quantitative analysis decomposed
the problem into two subproblems. The solution to the first subproblem determines the shift requirements
that minimize surplus scheduled hours, and the solution to the second subproblem determines the
assignment of employees to meet the shift requirements from the first subproblem. The analysts developed
specialized solution algorithms that enabled a restaurant manager to develop a schedule in about 15 mins.

Using the new system, restaurant managers can generate employee schedules in only 10-20% of
the time formerly needed to do so. The system satisfies hal-hourly labore requirements while minimizing
surplus scheduled hours and reducing direct labor costs. Additionally, employees are more likely to get
their preferred work hours and the work areas where they perform best.
Based on Love, R. Jr., and J.M. Hovey, “Management Science Improves Fast-Food Operations.” Interfaces, March-April 1990, pp.
21-29.
GRAPHICAL SOLUTION FOR A PURE INTEGER AND MIXED INTEGER LINEAR
PROGRAM

ILLUSTRATION EXAMPLE:
Currently, Security Realty Investors has $1,365,000 available for investments in new
rental properties. Security has narrowed down the available investment options to a collection
of townhouses and a collection of apartment buildings in a sizable apartment complex after
conducting an initial examination. There are now just four blocks of townhouses available, and
each block of three townhomes costs $195,000 to buy. The 12 dwelling units in each of the
apartment complex's buildings sell for $273,000 each. The complex developer has committed to
create as many 12-unit apartment buildings as Security Realty desires to purchase, and the
individual apartment buildings can be bought independently.
The property manager at Security can commit 140 hours a month to these initiatives. The
property manager will need to devote 4 hours per month to each townhouse block and 40 hours
per month to each apartment complex. To maximize yearly cash flow, the expected cash flow
after mortgage payments and operational costs is $2000 for townhouse blocks and $3000 for
apartment buildings.

Dropping the integer requirements and tackling the LP Relaxation that results to starting
step in resolving this problem. When we remove the need for integer decision variable
requirements, LP relaxation occurs. The value of the optimal LP relaxation solution for a
maximization problem is an upper constraint on the value of the optimal integer solution.
The decision variables could then be rounded in an effort to solve the integer linear
program as efficiently as possible. However, it's possible that this method won't lead to the
optimal solution. In fact, rounding the choice variable values can lead to an impractical answer.
Any integer or mixed-integer LP involving maximization has an optimal solution with a value
that is less than or equal to the value of the LP relaxation.

BINARY INTEGER LINEAR PROGRAMMING

All the decision variables have the binary form
1 if decision 𝑗 is yes
𝑥𝑗 = { j = 1, 2, 3, …, n
0 if decision 𝑗 is no
ILLUSTRATION EXAMPLE: (Capital Budgeting)

Over the next four years, The Ice-Cold Refrigerator Company will evaluate a range of projects
with various capital requirements. The business must decide which capital expenditure projects will be
the most profitable given its limited capital resources.
Estimated Capital Requirements ($)
Project Net Present Year 1 Year 2 Year 3 Year 4
Value ($)
Plant expansion 90,000 15,000 20,000 20,000 15,000
Warehouse expansion 40,000 10,000 15,000 20,000 5,000
New machinery 10,000 10,000 0 0 4,000
New product research 37,000 15,000 10,000 10,000 10,000
Available capital funds 40,000 50,000 40,000 35,000
 ILLUSTRATION EXAMPLE:
All of SOUTHWESTERN AIRWAYS' forthcoming flights require crew assignments. We will
concentrate on the issue of pairing three San Francisco-based crews with the flights indicated in the table's first
column. The remaining 12 columns display the crew's 12 plausible flight paths. Every flight must be covered
by exactly three sequences, one for each crew (the numbers in each column indicate the order of the flights).
The cost of assigning a crew to a specific sequence of flights is given in the bottom row of the table (in thousands
of dollars). It is legal to have more than one crew on a flight, but union contracts mandate that the extra crews
still need to be paid for their time as if they were working. The goal is to keep the three crew assignments that
cover all the flights' total costs as low as possible.

We have 12 possible flight sequences, and 12 yes/no options:

Should a crew be assigned to sequence j?(j = 1, 2, …, 12)
To represent these many choices, we therefore use 12 binary variables:

1 if sequence 𝑗 is assigned to a crew

𝑥𝑗 = {
0 otherwise.

Minimize: 𝑍 = 2𝑥1 + 3𝑥2 + 4𝑥3 + 6𝑥4 + 7𝑥5 + 5𝑥6 + 7𝑥7 + 8𝑥8 + 9𝑥9 + 9𝑥10 +
8𝑥11 + 9𝑥12
Subject to: 𝑥1 + 𝑥4 + 𝑥7 + 𝑥10 ≥ 1 (SF to LA)
𝑥2 + 𝑥5 + 𝑥8 + 𝑥11 ≥ 1 (SF to Denver)
𝑥3 + 𝑥6 + 𝑥9 + 𝑥12 ≥ 1 (SF to Seattle)
𝑥4 + 𝑥7 + 𝑥9 + 𝑥10 + 𝑥12 ≥ 1 (LA to Chicago)
𝑥1 + 𝑥6 + 𝑥10 + 𝑥11 ≥ 1 (LA to SF)
𝑥4 + 𝑥5 + 𝑥9 ≥ 1 (Chicago to Denver)
𝑥7 + 𝑥8 + 𝑥10 + 𝑥11 + 𝑥12 ≥ 1 (Chicago to Seattle)
𝑥2 + 𝑥4 + 𝑥5 + 𝑥9 ≥ 1 (Denver to SF)
𝑥5 + 𝑥8 + 𝑥11 ≥ 1 (Denver to Chicago)
𝑥3 + 𝑥7 + 𝑥8 + 𝑥12 ≥ 1 (Seattle to SF)
𝑥6 + 𝑥9 + 𝑥10 + 𝑥11 + 𝑥12 ≥ 1 (Seattle to LA)
12
∑𝑗=1 𝑥𝑗 = 3 (assign 3 crews)
And 𝑥𝑗 is binary, for j = 1, 2, …, 12

Using Lingo 13.0 software to solve this problem resulted to two possible optimal
solutions:
Solution 1: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 , 𝑥9 , 𝑥10 , 𝑥11 , 𝑥12 ) = (0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0) 𝑍 = $18,000
Solution 2: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 , 𝑥9 , 𝑥10 , 𝑥11 , 𝑥12 ) = (1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1) 𝑍 = $18,000
 CONCEPT REVIEW
The integer linear program is a significant addition to the linear programming model that
we have presented. The additional restriction on some of the variables is the only distinction
between the integer linear programming issue and the linear programming problem covered in
earlier sections. An all-integer linear program is one in which all the variables must be integer;
a mixed-integer linear program is one in which some variables must be integer but not necessarily
all of them. Finally, we have a 0-1 (binary) integer linear program if the integer variables can
only take values of 0 or 1. All-integer or mixed-integer binary integer programs are both possible.
The application of integer linear programming has expanded significantly in recent years
thanks to the availability of commercial integer linear programming computer codes. This
growth and the creation of new applications can be anticipated to continue as researchers create
solution processes capable of handling linear programs with bigger numbers of variables and as
computer speeds improve.
NAME: ____________________________________ SCORE: __________________

COURSE/YEAR: _______________________________ DATE: _______________

EXERCISE 5

1. Consider the following ILP problem.

Maximize 𝑍 = 5𝑥1 + 𝑥2 ,
Subject to
-𝑥1 + 2𝑥2 ≤ 4
𝑥1 − 𝑥2 ≤ 1
4𝑥1 + 𝑥2 ≤ 12
and
𝑥1 ≥ 0, 𝑥2 ≥ 0
𝑥1 , 𝑥2 are integers.

a. Solve this problem graphically.

b. Solve the LP relaxation graphically. Round this solution to the nearest integer solution and check
whether it is feasible. Then enumerate all the rounded solutions by rounding this solution for the
LP relaxation in all possible ways (i.e., by rounding each non-integer value both up and down). For
each rounded solution, check for feasibility and, if feasible, calculate Z. Are any of these feasible
rounded solutions optimal for the IP problem?

 SOLUTION:
NAME: ____________________________________ SCORE: __________________

COURSE/YEAR: _______________________________ DATE: _______________

2. Consider the following IP problem.

Maximize 𝑍 = 2𝑥1 + 3𝑥2 ,
Subject to
4𝑥1 + 9𝑥2 ≤ 36
7𝑥1 + 5𝑥2 ≤ 35
𝑥1 , 𝑥2 ≥ 0 and 𝑥1 integer
a. Graph the constraints for this problem. Indicated on your graph all feasible mixed-integer solutions.
b. Find the optimal solution to the LP Relaxation. Round the value of 𝑥1 down to find a feasible mixed-
integer solution. Is this solution optimal? Why or why not?
c. Find the optimal solution for the mixed-integer linear program.

 SOLUTION:
NAME: ____________________________________ SCORE: __________________

COURSE/YEAR: _______________________________ DATE: _______________

3. A community council must decide which recreation facilities to construct in its community. Four new
recreation facilities have been proposed – a swimming pool, a tennis center, an athletic field, and a
gymnasium. The council wants to construct facilities that will maximize the expected daily usage by the
residents of the community, subject to land and cost limitations. The expected daily usage and cost and
land requirements for each facility follow:
Recreation Facility Expected Usage Cost Land Requirements
(people/day) ($) (acres)
Swimming pool 300 35,000 4
Tennis center 90 10,000 3
Athletic field 400 25,000 7
Gymnasium 150 90,000 3
The community has a $120,000 construction budget and 12 acres of land. Because the swimming pool
and tennis center must be built on the same part of the land parcel, however, only one of these two
facilities can be constructed. The council wants to know which of the recreation facilities to construct
and maximize the expected daily usage.

 SOLUTION: