2-504-09 Lecture Notes - Lecture 14: Grapefruit Juice, Prentice Hall, Decision Analysis
1"
"
Integer programming
1. Introduction
In previous chapters, we have proposed and solved models where the solution
could take any value in a given interval. In some situations, it may be that this
solution is impractical because the value has to be integer. In the case where
the values obtained are very large, the difference is negligible. For example,
if the model used by a car manufacturer suggests manufacturing 10,272.27
and 18,736.84 models A and B, respectively, the manufacturer will always
attempt to round these values and correct the situation with a workable
solution that is sufficiently close to the optimal one. But when the required
values are small, rounding can produce solutions far from the optimal solution
or impractical solutions. If our manufacturer makes planes, not cars, and his
model suggests producing 2.27 and 3.84 models C and D, respectively, it may
be impossible to produce 2 planes of model C and 4 planes of model D. The
optimal solution could even be to produce 4 models C and 1 model D.
You may have noticed that when introducing a constraint in the Excel Solver,
the options are ≥, ≤, =, int, and bin. The int (for integer) and bin (for binary)
options allow us to impose the value of a variable cell to be integer (or binary).
So it is very simple, when modelling our problem and implementing it in
Excel or any other software, to impose integer values for one, several, or all
of the variables. One must be careful when using these constraints because the
computing time can be seriously affected. It is not uncommon for such models
to take several minutes or even hours to be solved.
In this chapter, we will see why the computational time can increase
drastically. We will also see that some complex situations can be easily
modelled with binary variables.
2. A first example
To illustrate this concept, consider a common situation: choosing the
composition of our next meal. Let’s imagine that we are entering a fast food
type of restaurant. On the wall, a menu is displayed. This menu contains a list
of items and their price. This is fast food and therefore not the healthiest
choice. On the restaurant’s website, you can find details about the nutritional
composition of these items; refer to the Excel file ILP-1-Menu.xlsx under the
find more resources at oneclass.com
find more resources at oneclass.com
2"
"
tab Data. For each of the 15 items on the menu, it includes the price, the
number of calories, the amount of protein and fat in grams, the amount of
sodium in milligrams, and some vitamins as a percentage of the
Recommended Dietary Allowance (RDA) by the U.S. Department of Health
and Human Services. According to this organization, the calories must be at
least 30 times the amount of fat measured in grams, we must have at least 55
grams of protein and cannot exceed 3,000 mg of sodium. All other vitamins
should be at least 100% of the recommended amount. We will compose a
menu from these 15 items that meets these standards. A linear programming
model enables us to find the cheapest menu respecting all those constraints.
Our goal here is to compose the menu, that is to say how many hamburgers,
fries, juice, etc. to order. To find these numbers, we introduce the following
fifteen variables: xi = number of ordered item i, for i=1, 2, … 15.
Each hamburger costs $0.59. If you order a quantity x1, it will cost 0.59·x1. It
is the same for all other items. We seek to minimize the price of our menu
which can be expressed as:
Minimize 0.59 x1 + 1.79 x2 + … + 0.68 x15.
Our solution will satisfy some constraints. We need to make sure that our
menu respects the RDA recommendations. Thus, we will measure the amount
of protein and verify that this amount is at least 55. We will also impose that
the number of calories contained in our menu is at least 30 times the amount
of fat measured in grams. For each of the vitamins, we will measure the
percentage contained in our menu and check that it is at least 100%.
Let us look at the amount of protein. Each hamburger contains 12 grams of
protein. If you buy x1 hamburgers, we will have 12·x1 g of protein. The deluxe
burger contains 22 g of protein per unit. It is therefore necessary to add 22·x2
in the amount of protein. And so on to the grapefruit juice, where we will add
1·x14 g of protein. The protein constraint can be written as follows:
!"#$%&""#$'& ( & # $%) *++
For the relationship between the amount of fat and the calories we impose the
following relationship:
,- ./$%&!-$'& ( & "$%' 0"++$%&,"-$'& ( & /-$%1
Which can be rewritten as follows:
find more resources at oneclass.com
find more resources at oneclass.com
3"
"
!+#$%2"-#$'& ( 2 /-#$%1 0 -
This gives the following linear programming model:
345 -6+/#$%& !67/$'& ( & -689#$%1
:6 ;6 !"#$%&""#$'& ( & ##!#$%) *++
!+#$%2"-#$'& ( 2 /-#$%1 0 -
< <
!+#$%&"-#$'& ( & =##$%1 *!--
$>* - ?#@
This model has been implemented in the Excel ILP-1-Menu.xlsx under the
Model tab. By using the Solver, one finds an optimal solution containing 5.3
burgers, 0.54 garden salad, etc. It is difficult to buy 5.3 hamburgers. By
rounding it to 5 burgers the amount of vitamin C will decrease below the 100%
threshold. If we order 6 burgers, the solution will cost more ($6.54 instead of
$6.13) and the amount of sodium will reach 3,343 mg with an excess of 343
mg. Rounding is not an option that leads here to the optimal solution.
To find the optimal solution that will have integer values for the variables, we
will add integrality constraints.
To enter these constraints in Excel, just add a constraint in the solver menu.
The left part of the constraint (Cell Reference) will contain the variable cells
which need to take integer values. Then, when choosing the type of constraints
≤, ≥ or =, the int option will be chosen (bin can be chosen only with binary
variables). One does not have to enter the right part of the constraint
(Constraint). If the cells on the left do not correspond to variable cells, Excel
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
In previous chapters, we have proposed and solved models where the solution could take any value in a given interval. In some situations, it may be that this solution is impractical because the value has to be integer. In the case where the values obtained are very large, the difference is negligible. But when the required values are small, rounding can produce solutions far from the optimal solution or impractical solutions. You may have noticed that when introducing a constraint in the excel solver, the options are , , =, int, and bin. The int (for integer) and bin (for binary) options allow us to impose the value of a variable cell to be integer (or binary). So it is very simple, when modelling our problem and implementing it in. Excel or any other software, to impose integer values for one, several, or all of the variables.
