CHAPTER 9

Integer linear programming

Real-life application. Optimization of truck trailer loads

in PFG Building Glass
PFG uses specially equipped fifth-wheel tow trucks to
deliver packages of flat glass sheets to customers. The packages vary in size
depending on the orders, a load can include different packages, according to weight
cibidos. Government regulations limit the weights on the axles and the place-
The positioning of the packages in the trailer is crucial for determining these weights. The
problema tiene que ver con la determinación de la carga óptima de los paquetes sobre
the truck bed to meet the weight limits on the axles. The problem is re-
Solve as a complete program. Case 7 of chapter 26 on the website provides
the details of the study.

9.1 Illustrative Applications

Generally, integer linear programming (ILP) applications fall within
two categories: direct and transformed. In the direct category, the nature of the situation -
This condition prevents the assignment of fractional values to the model's variables. For example,
The problem may involve determining whether or not to undertake a project.
(binary variable), or the determination of the optimal number of machines needed to
to carry out a task (general integer variable). In the transformation category, they use
auxiliary integer variables to analytically convert unsolvable situations into
models that can be solved through available optimization algorithms.
For example, in the sequence of two jobs, A and B, on a single machine, job A
can precede the work or vice versa. The 'or' nature of the restrictions is the
what makes the problem analytically unsolvable, because all programming algorithms
mathematical formations deal only with 'and' restrictions. Section 9.1.4 shows how
auxiliary binary variables are used to transform the 'or' constraints into
"y", without modifying the nature of the model.

315

[Link]
316 Chapter 9 Integer Linear Programming

For convenience, a problem is defined as a pure integer program when all

The variables are integers. Otherwise, it is a combined integer program (PEC).
which involves a combination of integer and continuous variables.

9.1.1 Capital budget

The decision to undertake a project or not is usually made according to...
considerations and pre-established priorities of a limited budget. The following example-
plo presents one of these situations.

Example 9.1-1 (Project Selection)

Five projects are being evaluated over a planning horizon of 3 years.
The following table presents the expected returns and the annual expenses involved.

Expenses ($ million)/year

Project 1 2 3 Rendimientos ($ millones)

1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Available funds ($ million) 25 25 25

Which projects should be selected over the 3-year period?

The problem reduces to a 'yes-no' decision for each project. Define the binary variable.
xj how xj=e
1, if the project is selected
0, if the project is not selected
The PLE model is
Maximize z = 20x1+40x2+20x3+15x4+30x5
Subject to
5x1+4x2+3x3+7x4+8x525
x1+7x2+9x3+4x4+6x525
8x1+10x2+2x3+x4+10x525
x1,x2,x3,x4,x5(0,1)
The optimal integer solution (obtained with AMPL, Solver, or TORA)1esx15x25x35x451
x550, conz595 ($ million). The solution excludes project 5 from the project combination.

1 Touse TORA, select the Integer Programming menu from the Main menu bar. After...
Enter the problem data, go to the results screen, and select Automated B&B to obtain
find the optimal solution. Solver is used the same way as in LP, only that the variables must be declared as integers.
The integer option (intobin) is available in the Solver Parameters dialog box when you add a
new restriction. The implementation of AMPL for integer programming is the same as in LP, ex-
I accept that some or all variables are declared as integers by adding the keyword integer (binary)
in the variable definition instruction. For example, the instruction varx{J} >= 0, integer; decla-
theaxisjas it is not negative for all the elements J. Sixjit is binary, the instruction changes avar x{J}>=0,
binary; For its execution, the instruction option solver cplex; must precede a solve;

[Link]
 9.1 Illustrative applications

Comments. It is interesting to compare the continuous LP solution with the PLE solution.
optimal solution of LP, obtained by replacing xj5(0,1) with 0#xj#1 for all thej, take for
results15.5789,x25x35x451,x55.7368, yz5108.68 ($ million). The solution does not have
sense because lax1yx5Binaries take fractional values. We can round the solution.
to the nearest whole number, which dax15x551. However, the resulting solution violates the res-
Trictions. Furthermore, the concept of rounding loses its meaning in this case because xjrepresents
a "yes-no" decision.

SET OF PROBLEMS 9.1A2

1. Modify and solve the capital budgeting model of example 9.1-1 to have
take into account the following additional restrictions:
Project 5 must be selected regardless of whether project 1 or project 3 is selected.
Projects 2 and 3 are mutually exclusive.
2. Five items will be loaded onto a ship. Below is the weight [Link] vo-
lumenviand the valueiof the article.

Article Unit Weight, wi(tons) Unit volume, vi(yd3Unit value, ri($100)

1 5 1 4
2 8 8 7
3 3 6 6
4 2 5 5
5 7 4 4

The maximum permissible weight and volume of the load are 112 tons and 109.
yd3, respectively. Formulate the integer linear programming model, and determine the
most valuable cargo.
Suppose you have 7 full wine bottles, 7 half full, and 7 empty. You would like to divide the
21 bottles among three individuals in such a way that each one receives exactly 7. In addition,
Each individual must receive the same amount of wine. Express the problem as res-
constraints of the PLE, and find a solution. (Suggestion: Use a fictitious objective function in
that all the target coefficients are zeros.)
An eccentric sheikh left a will to distribute a herd of camels among his three
children: Tarek receives half of the flock, Sharif gets a third part, and Maisa receives
a ninth. The rest is allocated to charity. The will does not specify the size of the re-
bathroom, it only says that it is an odd number of camels and that the charity institution nom-
Brada receives exactly one camel. Use the PLE to determine how many camels he left.
the sheikh in the will and how much each child receives.
A couple of farmers sends their three children to the market to sell 90 apples;
Karen, the oldest, has 50 apples; Bill, the middle one, has 30; and John, the youngest,
it only carries 10. The parents have established five rules: (a) the selling price is $1 per
7 apples or $3 for 1 apple; or a combination of the two prices. (b) Each child
may exercise one or both options of the sale price. (c) Each one must return with
exactly the same amount of money. (d) The income of each child must be in dollars
integers (cents are not allowed). (e) The amount received by each child must be the maximum
as much as possible according to the stipulated conditions. Given that the three children are capable of

2Problems 3 to 6 are an adaptation of MalbaTahan, The Man Who Calculated, Limusa Publishing.
Mexico City, pages 39-182, 1994. Problems 13 to 16 are an adaptation of puzzles compiled at http:
[Link]/puzzles/[Link]. Certainly without considering the compound letters CD
and LL. (N. of the T).

[Link]
318 Chapter 9 Integer linear programming

sell everything they carry, use the PLE to show how the conditions can be met
actions of their parents.
A captain of a merchant ship wanted to reward three members of the crew.
for their brave effort in saving the ship's cargo during an unexpected storm in
high seas. The captain set aside a sum of money in the purser's office and instructed the
officially to distribute it equally among the three sailors afterwards
that the ship would dock. One night, one of the sailors, without the others knowing,
he directed to the office of the steward and decided to claim a third (equitable) of the money of
in advance. After he divided the money into three equal parts, there was a remnant left.
Neda, the one that the sailor decided to keep (in addition to a third of the money). That night if-
Next, the second sailor had the same idea and repeated the same division into three parts.
with what was left, and ended up with an extra coin. On the third night the ter-
the sailor also took a third of what was left, plus an extra coin
that could not be divided. When the ship arrived, the first officer divided what was left of the
money divided equally among the three sailors, leaving one extra coin again.
To simplify things, the first officer set aside the extra coin and gave it to the marines.
ros his equal parts assigned. How much money was in the safe at the beginning? Formulate
the problem as a PLE, and find the solution. (Suggestion: The problem has an infini-
of integer solutions. For convenience, let's assume we are interested in determining the
minimum amount of money that satisfies the conditions of the problem. Then, increase it by one.
to the resulting sum, and add it as a lower bound to obtain the next minimum sum
Continuing this way, a general solution pattern will emerge.)
7. Weber (1990). Let's assume we have the following three-letter words: AFT, FAR,
TVA, ADV, JOE, FIN, OSF and KEN. Let’s assume we assign numeric values to
alphabet starting with A51 and ending with Z527. Each word is assigned
a rating by adding the numerical codes of its three letters. For example, AFT
It has a rating of 116120527. You must select five out of eight words.
given that give the maximum total rating. At the same time, the five words must
satisfy the following conditions:
sum of the grades sum of the grades sum of the grades
a b6a b6a b
from the letter 1 from letter 2 from letter 3
Formulate the problem as a linear programming model and find the optimal solution.

8. Solve problem 7 given that, in addition to the total sum being the maximum, the sum of the
column 1 and the sum of column 2 will also be the maximums. Find the optimal solution.
9. Weber (1990). Consider the following groups of words:

Group 1 Group 2

AREA FIRST
FORT FOOT
HOPE HEAT
SPAR PAST
THAT PROF
TREE STOP

All the words in groups 1 and 2 can be formed with the nine letters A, E, F, H, O.
P, R, S, and T. Develop a model to assign a unique numerical value from 1 to 9 to these.
letters, so that the difference between the total scores of the two groups will be what
as small as possible. Note: The score for a word is the sum of the values
numerical values assigned to their individual letters.

[Link]
 9.1 Illustrative Applications

The company Record-a-Song hired an up-and-coming star to record eight songs.

The sizes in MB of the different songs are 8, 3, 5, 5, 9, 6, and 12, respectively.
Record-a-Song uses two CDs for recording. The capacity of each CD is
of 30 MB. The company would like to distribute the songs across the two CDs in such a way that
the space used in each one should be approximately the same. Formulate the problem
as an integer linear programming and determine the optimal solution.
11. In problem 10, suppose that the nature of the melodies dictates that songs 3 and
4 cannot be recorded on the same CD. Formulate the problem as a PLE. Would it be possible-
Can you use a 25 MB CD to record the eight songs? If not, use the PLE to ...
determine the minimum capacity of the CD to perform the recording.
12. Graves and Associates (1993). The University of Ulern uses a mathematical model.
that optimizes the preferences of the students taking into account the limitation of
classroom and the faculty. To demonstrate the application of the model, consider the
simplified case of 10 students who were asked to select two courses from
among six offered. The following table shows the grades that represent the pre-
reference of each student for the individual courses, with 100 as the highest grade
high. To simplify, it is assumed that the rating of the preference of a selection of
The total of the grades is the sum of the individual grades. The capacity of the course is the nu-
my maximum number of students who can take the class.

Course preference rating

Student 1 2 3 4 5 6

1 20 40 50 30 90 100
2 90 100 80 70 10 40
3 25 40 30 80 95 90
4 80 50 60 80 30 40
5 75 60 90 100 50 40
6 60 40 90 10 80 80
7 45 40 70 60 55 60
8 30 100 40 70 90 55
9 80 60 100 70 65 80
10 40 60 80 100 90 10
Course capacity 6 8 5 5 6 5

Formulate the problem as a LP and find the optimal solution.

13. It has three denominations of currency with 11 coins of each. The total value (of the
11 coins) is 15 bits for denomination 1, 16 for denomination 2, and 17 bits
For the 3. You need to purchase an 11-bit item. Use the PLE to determine the
minimum amount of coins of the three denominations required to make
the purchase.
14. It has a board with 434 squares and a total of 10 tokens. Use the PLE to place the tokens.
on the board so that each row and each column have an even number of pieces.
A street vendor who sells electronic devices had all his merchandise stolen.
When he reported the incident to the police, the seller could not say how many devices that
he had but declared that when he divided the total into batches of 2, 3, 4, 5, or 6, there was always one left over.
device. On the other hand, none was left when the total was divided into batches of 7. Use
PLE to determine the total number of devices the seller had.
[Link] those 51, 2,...,n, formulate a PLE model (for any n) to determine the
minimum number that, when divided by the whole number 21i, will always produce
a remainder equal to ai; that is, ymod (21i)5i.

[Link]
320 Chapter 9 Integer linear programming

A well-known riddle requires that a single different digit (from 0 to 9) be assigned to each
lyrics of the equation SEND1MORE5MONEY. Formulate the problem as a progra-
My entire and found the solution. (Suggestion: This is an assignment model with condition-
Some collateral.
The world-famous Japanese logical puzzle, Sudoku, consists of a grid of a...
the 939 divided into 9 non-overlapping subgrids of 333. The puzzle with-
You need to assign the numeric digits from 1 to 9 to the cells of the grid in such a way that
each row, each column, and each sub-grid contains distinct digits. Some of the
Cells can be fixed in advance.
Formulate the problem as an integer program, and find the solution for the case.
given below.

6 1 4 5

8 3 5 6

2 7

8 4 7 6

6 3

7 9 1 4

5 2

7 2 6 9

4 5 8 7

Suggestion: seaxijk51 if the digitoken is placed in cell (i,j), i,j,k51, 2,...,n,n59. If uti-
Liza AMPL, please note that conn59, the number of variables that results will exceed the
capability of the student version of AMPL. If you do not have access to the full version of
AMPL can develop a general model for n54 or 9, and then solve them for the
simplest case (almost trivial) of a grid of 434 with a subgrid of 232.

9.1.2 Set Covering Problem

In this type of problems, several plants offer services that overlap at various instances.
relationships. The goal is to determine the minimum number of plants that cover (that is, that
satisfy the service needs of each installation. For example, can be built
water treatment plants in various places, and each plant serves a group of cities.
Overlap occurs when more than one plant serves a given city.

Example 9.1-2 (Installation of security phones)

To promote safety on campus, the University Public Safety Department
Arkansas is in the process of installing emergency phones in selected locations.
The department wishes to install a minimum number of these devices that provide service.
to each of the main streets of the campus. Figure 9.1 is a map of these streets.
It is logical to maximize the utility of phones by placing them at street intersections.
In this way, a single unit can serve at least two streets.
Define
xj=e
1, a phone is installed in the place j, j=1, 2,..., 8
0, otherwise

[Link]
 9.1 Illustrative Applications

1 StreetA 2 CalleB 3

StreetC
4 5

StreetE StreetD

6 7 8

FIGURE 9.1
Map of the streets of the University of Arkansas campus

The problem constraints require that at least one phone be installed in each of the
11 streets (AaK). Therefore, the model is

Minimizarz=x1+x2+x3+x4+x5+x6+x7+x8

Subject to
x1+x2 U1 (Street A)
x2+x3 U1 (B Street)
x4+x5 Street C
x7+x8Ú1 (Street D)
x6+x7 Ú1 (Street E)
x2 +x6 U1 (F Street)
x1 +x6 U1 (G Street)
x4 +x7 U1 (H Street)
x2 +x4 U1 (Street I)
x5 +x8Ú1 (Street J)
x3 +x5 Ú1 (Street K)
xj(0, 1), j=1, 2,..., 8
The optimal solution to the problem requires the installation of four phones at the intersections.
["1, 2, 5 and 7."]

Comments. In the strict sense, coverage issues are characterized by the si-
Following criteria: (1) The variables xjbinary coefficients; (2) the coefficients on the left side

[Link]
322 Chapter 9 Integer Linear Programming

I want the constraints to be 0 or 1; (3) the right side of each constraint is of the form ($1),
y (4) the objective function minimizes1x11c2x21…1c nxn, wherej.0 for all 51, 2,...,n.
In this example,j51 for all the j. Sicjrepresents the installation cost at the intersection
j, then these coefficients can take values different from 1. The variations of the prob-
coverage includes additional collateral conditions, as described by means of al-
some of the situations described in the problems of set 9.1b.

Moment of AMPL
The file [Link] provides a general model for any coverage problem.
The formulation is detailed in section C.9 on the website.

SET OF PROBLEMS 9.1B

[Link] is a transportation company for less than truckload shipments that delivers loads.
daily to five clients. The following list provides the clients associated with each route:

Route Clients served on the route

1 1, 2, 3, 4
2 4, 3, 5
3 1, 2, 5
4 2, 3, 5
5 1, 4, 2
6 1, 3, 5

The segments of each route depend on the capacity of the truck that delivers the
loads. For example, on route 1, the truck's capacity is sufficient to deliver the
charges to clients 1, 2, 3, and 4 only. The following table lists the distances (in mi-
between the truck terminal (ABC) and the customers.

Miles away

j ABC 1 2 3 4 5
i

ABC 0 10 12 16 9 8
1 10 0 32 8 17 10
2 12 32 0 14 21 20
3 16 8 14 0 15 18
4 9 17 21 15 0 11
5 8 10 20 18 11 0

The objective is to determine the minimum distance required to make the deliveries.
daily to the five clients. Even though the solution may result in a client-
you are served by more than one route, the implementation phase will use only one of those
routes. Formulate the problem as a PLE, and find the optimal solution.
*[Link] Universidad de Arkansas va a formar un comité para atender las quejas de los estu-
The administration wants the committee to include at least one woman, one man,
a student, an administrator, and a teacher. Ten people (identified, by limp

[Link]
 9.1 Illustrative Applications323

Dad, with the letters of laaa laj) they have been nominated, and they have been combined in the distinctions-
the following categories:

Category Persons

Women a,b,c,d,e
Men f,g,h,i,j
Students a,b,c,j
Administrators e,f
Teachers d,g,h,i

The University of Arkansas wishes to form the smallest committee with representation.
for each of the five categories. Formulate the problem as a PLE, and find the solution.
optimal action.
The county of Washington includes six populations that need ambulance service.
emergency stations. Due to the proximity of some populations, a single station
can serve more than one community. The stipulation is that the station must be
at most 15 minutes of driving time from the population it serves. The si-
The following table shows the driving times in minutes between the six populations.

Times in minutes

j 1 2 3 4 5 6
i

1 0 23 14 18 10 32
2 23 0 24 13 22 11
3 14 24 0 60 19 20
4 18 13 60 0 55 17
5 10 22 19 55 0 12
6 32 11 20 17 12 0

Formulate a PLE whose solution produces the minimum number of stations and their
locations. Determine the optimal solution.
The immense treasures of King Tut are on display at the Giza Museum in Cairo.
The layout of the museum is shown in figure 9.2 with the different rooms connected.
such through open doors. A guard standing at a door can oversee two adjacent rooms.
cents. The museum's security policy requires the presence of a guard at each
Room. Formulate the problem as a PLE to determine the minimum number of guards.

FIGURE 9.2
Distribution of the museum of problem 4,
set 9.1c

[Link]
324 Chapter 9 Integer linear programming

[Link] has just finished his exams for the academic year and wants to celebrate by watching all the
movies that are being shown in theaters in your city and other neighboring cities. If you travel to
another city, she will stay there until she sees all the movies she wants. The next table in-
information about movie offers and round trip distances to neighboring cities.

Location Offers of Miles of Cost per

of the cinema movies round trip movie ($)

In his city 1, 3 0 7.95

City A 1, 6, 8 25 5.50
City B 2, 5, 7 30 5.00
City C 1, 8, 9 28 7.00
City D 2, 4, 7 40 4.95
City E 1, 3, 5, 10 35 5.25
City F 4, 5, 6, 9 32 6.75

The cost of driving is 75 cents per mile. Bill wants to determine the cities
what you need to visit to see all the movies while minimizing your total cost.
6. Walmark stores are in the process of expanding in the western United States.
Walmark plans to build new stores that will provide service next year.
10 geographically dispersed communities. Past experience indicates that a co-
community must be within a maximum distance of 25 miles from a store to attract clients
test. In addition, the population of a community plays an important role in the location-
The location of a store, in the sense that larger communities generate more customers.
participants. The following table provides the populations and also the distances (in
miles) between the communities.

Miles of the community

j 1 2 3 4 5 6 7 8 9 10 Population
i

1 20 40 35 17 24 50 58 33 12 10,000
2 20 23 68 40 30 20 19 70 40 15,000
3 40 23 36 70 22 45 30 21 80 28,000
4 35 68 36 70 80 24 20 40 10 30,000
5 17 40 70 70 23 70 40 13 40 40,000
6 24 30 22 80 23 12 14 50 50 30,000
7 50 20 45 24 70 12 26 40 30 20,000
8 58 19 30 20 40 14 26 20 50 15,000
9 33 70 21 40 13 50 40 20 22 60,000
10 12 40 80 10 40 50 30 50 22 12,000

The idea is to build the smallest number of stores, taking into account the restriction.
from the distance and the concentration of populations.
Specify the communities where the stores should be located.
7. Guéret and Associates (2002). Section 12.6. MobileCo's budget for building 7
transmitters that cover the largest possible population in 15 geographical communities with-

[Link]
 9.1 Illustrative Applications

Tiguas, it is 15 million dollars. Below are the covered communities.

costs for each transmitter and the estimated construction costs.

Transmitter Covered communities Cost (millions of $)

1 1, 2 3.60
2 2, 3, 5 2.30
3 1, 7, 9, 10 4.10
4 4, 6, 8, 9 3.15
5 6, 7, 9, 11 2.80
6 5, 7, 10, 12, 14 2.65
7 12, 13, 14, 15 3.10

The following table provides the populations of the different communities:

Community 1 2 3 4 5 6 7 8 9 10

Population (in thousands) 10 15 28 30 40 30 20 15 60 12

¿Cuáles de los transmisores propuestos deben construirse?

8. Gavermini and Associates (2004). Modern electrical networks use electric meters
automatic tricos instead of the more expensive manual meters. In the system au-
automatically, the meters of several customers are wirelessly linked to a single receiver
The meter sends signals every month to a designated receiver to report the
customer electricity consumption. Then the data is channeled to a central computer.
trail to generate the receipts. The objective is to determine the minimum number of recipients needed.
rivers to serve a given number of meters. In real life, the problem includes
of thousands of meters and receivers. This problem uses 10 meters and 8 possible
locations for the receivers, with the following configurations:

Receptor 1 2 3 4 5 6 7 8

Meters 1, 2, 3 2, 3, 9 5, 6, 7 7, 9, 10 3, 6, 8 1, 4, 7, 9 4, 5, 9 1, 4, 8

9. Solve problem 8 if, in addition, each receiver can handle at most 3 media.
pains.

9.1.3 Fixed Charge Problem

The fixed cost problem relates to situations where economic activity
incurs in two types of costs: a fixed cost necessary to start the activity and a
variable cost proportional to the level of activity. For example, the initial tooling
Before starting production, a machine incurs a fixed setup cost.
regardless of how many units are produced. Once complete, it prepares
tion of the machine, the cost of labor and materials is proportional to the can-
produced quantity. Given that F is the fixed charge, c is the variable unit cost, and x is the
production level, the cost function is expressed as
C1x2=e
F+cx, six70
0, otherwise

[Link]