ISDS 440
Dr. Z. Goldstein
Notes on
Integer Linear Programming with Binary Variables
Introduction
Many decision situations require the implementation of integral decision variables. Rounding the values of continuous variables does not always work. For example, the number of bridges and streets to build need to be expressed as whole numbers, and rounding might lead to nonoptimal decisions. For cases such as this we need to develop integer programming models.
Integer variables of a special interest are binary variables, that take on only the values ‘0’ and ‘1’. They are used when decisions are of the ‘YES’ or ‘NO’ type.
Using binary variables to express various logical conditions:
The All or None condition
How can we express the condition that a variable X_{i} can get either the value 0 or some U>0? Answer: Use the constraint X_{j }= Uy_{j}, where y_{j} is binary. Note that if
y_{j} = 0 then X_{j} = 0, and if y_{j} = 1 then X_{j} = U. A variation of this idea is: X_{j} can take only the value 0 or values not less than U. Two constraints are required: Uy_{j} X_{j} My_{j}, where M is the largest value X_{j} can get. Note that when y_{j} = 1 U X_{j} M (but M does not limit X_{j} being the largest value X_{j} can have), and when y_{j} = 0, X_{j} = 0.
Example 1: A buyer is planning to purchase and then stock a certain amount (X) of some product. Limited free space for storing the product limits the quantity purchased to 1000 units (X 1,000). The buyer may decide to either not buy the product at all (keep shopping), or to buy it at a discount unit price (if qualified). To qualify for the discount he needs to buy at least 500 units of the product. Express this situation using a binary variable.
Solution: Let X be the quantity purchased. Then the buyer may decide to not buy the product (X = 0) or purchase at least 500 units (X 500). Since the maximum quantity that may be purchased is 1000, we can use the two constraints X 500y and X 1000y where ‘y’ is binary.
If – then condition
Example 2: If project A is selected, then project B must be selected. This condition is formulated by y_{A} y_{B}, where y_{A} and y_{B} are binary (equal to 1 when a project is selected). A variation of this condition is: If project A is selected, then project B cannot be selected. This condition is formulated by y_{A}1y_{B}.
Selecting k out of m
Selecting k out of m activities is a condition formulated by y_{1}+y_{2}+…+y_{m} = k, where y_{i} are binary (equals to 1 when an activity is chosen).
Variations of this condition are:
(i) At most k activities should be chosen: y_{1}+y_{2}+…+y_{m} k
(ii) At least k activities should be chosen: y_{1}+y_{2}+…+y_{m} k
Example 3: Seven different R&D projects are considered by management. Only 5 will be executed. This situation is formulated by y_{1}+y_{2}+…+y_{7} = 5, y_{i} is binary.
k out of m constraints must be satisfied
In various decision situations the decision maker allows a certain number of constraints be violated, while the rest of them need to be met. For example, the city council might decide that out of 3 restrictions and requirements imposed on a budgeting plan, only 2 are to be met. The following is a general description of such a situation:
Example 4:
Minimize 4X_{1} + 3X_{2} + 5X_{3}
S.T. (1) X_{1}+ X_{2 } 100
(2) 2X_{1}+ 4X_{3} 200
(3) 3X_{1}+3X_{2}+ X_{3} 300
First convert the third constraint into two inequality type constraints as follows:
3X_{1}+3X_{2}+ X_{3} 300, and 3X_{1}+3X_{2}+ X_{3} 300. Then, for a “greater then” type constraint, subtract My and for a “less than” type constraint add My (where ‘M’ is a very large number). Complete the modifications as follows:
(1’) X_{1}+ X_{2 } 100 – My_{1}
(2’) 2X_{1}+ 4X_{3} 200 + My_{2}
(3’) 3X_{1}+3X_{2}+ X_{3} 300 – My_{3}
(3”) 3X_{1}+3X_{2}+ X_{3} 300 + My_{3}
(4’) y_{1 }+_{ }y_{2} + y_{3} = 1
Explanation:
A constraint is satisfied when y_{i }= 0 (check each constraint to verify this; especially for constraint 3 that is expressed by constraints (3’) and (3”) together), while it ceases to be a constraint when y_{i} = 1. Thus, constraint (4’) forces exactly one constrain to not be effective (that is, exactly two constraints will be satisfied).
The Set Covering, Set Packing, and Set Partitioning Problems
These types of problems seek to find the best set of members from set S_{1} to have certain relationships with members of set S_{2}. The following examples demonstrate the concept.
Example 5:
An emergency planning team has identified five sites for basing paramedic teams and has broken the area into six demand regions. Their goals are to have paramedics based at most 5 minutes from the center of each demand region, and to have at least two bases at most 10 minutes from the center of regions 2 and 4. Travel time in minutes and the costs of the proposed bases are shown in the table below.
Formulate an IP model to select the cities that will satisfy the team’s goals at a minimum cost.
Regions

Team Locations

A

B

C

D

E

1
2
3
4
5
6

5
11
7
8
4
1

14
4
6
15
9
6

7
6
4
5
11
15

4
5
15
6
5
10

8
12
5
4
8
3

Costs

100

90

85

110

95

Solution
This is a typical covering problem. One set of items (the demand regions) must be covered by at least one item from another set of items (the paramedic team locations) under given conditions of travel times. The problem is how to cover all the demand regions by a selected set of paramedic team locations.
Define binary variables A, B, …,E (equal to 1 if a paramedic team is located at a certain location carrying the same name). Observe the model.
The model:
Minimize 100A+90B+85C+110D+95E
S.T. A+D1 Only location A and D are not more than 5 minutes away from region center 1
B+C+D 2 Two bases are within 10 minutes of region 2
C+E1 Region 3
A+C+D+E 2 Two bases are within 10 minutes of region 4
A+D1 Region 5
A+E1 Region 6
Observation: Typical constraints in covering problems have the form y_{1}+y_{2}+…+y_{n} 1 (y_{i} are binary variables).
Example 6
A moving and storage company is allocating five longdistance moving trucks. One feasible combination covers loads 1 and 3 in a 4525 mile route; a second combines loads 2,3, and 4 in 2960 miles; a third hauls loads 2,4, and 5 in 3170 miles; and fourth covers loads 4 and 5 in 5230 miles. Form a set of partitioning model to decide the minimum distance combination of routes covering each load exactly once.
Solution
Partitioning problems typically have constraints of the form X_{i} +…+X_{j} = 1.
Define X_{i} as binary variables (=1 if route “i” is selected).
The model
Loads

Routs

1

2

3

4

1
2
3
4
5




 Minimize 4525X_{1}+2960X_{2}+3170X_{3}+5230X_{4}
S.T. X_{1 }+ X_{4} = 1 (Load 1)
X_{2} + X_{3} = 1 (Load 2)
X_{1} + X_{2} = 1 (Load 3)
X_{2 }+ X_{3} + X_{4} = 1 (Load 4)
X_{3} + X_{4 }= 1 (Load 5)
The “OR” condition
If either activities A or B or both is selected, then activity C must be selected, but if neither A nor B is selected, activity C is not selected. This condition is formulated by y_{A} y_{C}, y_{B} y_{C}, y_{A} + y_{B} y_{C} (y_{i} is binary, equals to 1 when the activity is selected.)
The “AND” condition
If both activities A and B are selected activity C must be selected. If not both activities A and B are selected then activity C must not be selected. This condition is formulated by y_{A}_{ } y_{C}_{, }y_{B }_{ } y_{C}, y_{A} + y_{B} y_{C} + 1.
The fixed cost problem
Many times fixed costs as well as variable costs are incurred when an activity is taking place. For example, producing a product on a certain production line requires the setup of the line regardless of the quantity produced. Setup activities may be very costly thus cannot be ignored. The total cost of the production of Q units is F + cQ, where F is the fixed setup cost, and c is the unit variable production cost. However, when no quantity is produced (Q = 0), the total cost is not equal to F (as one might obtain from F + c(0)). Rather, the total cost is zero, since no production takes place. This means that the total cost function does not apply at Q = 0, which makes the total cost function nonlinear.
To overcome this difficulty we use a binary variable. The following example demonstrates the idea.
Example 7
A fertilizer plant can make a product by any of 3 processes. The unit production cost for each process is $15, $8, and $11 respectively. One raw material whose availability is limited to 310 units is needed for the production process. The amount of raw material used in each process per unit product is 2, 4, and 2 respectively. Time available for production is 450 minutes, and the respective production time per unit is 4, 3, and 1 minutes. The total amount of production should be 150 units.
(a) Set up an integer programming model to determine how many units should be produced in each process such that the total variable production cost is minimized.
(b) Revise the original LP model implementing a fixed setup cost of $400 charged for each process, if used.
Solution
(a) Define X_{i} as the amount produced in each process.
Min 15X_{1} + 8X_{2} + 11X_{3}
S.T. 2X_{1} + 4X_{2} + 2X_{3} 310
4X_{1} + 3X_{2} + X_{3} 450
X_{1} + X_{2} + X_{3} = 150_{ }
X_{i} is nonnegative for i = 1, 2, 3.
(b) Define y_{i }as a binary variable taking the value 1 if process ‘i’ is used (i = 1, 2, 3).
Min 15X_{1} + 8X_{2} + 11X_{3} + 400y_{1} + 400y_{2} + 400y_{3}
S.T. 2X_{1} + 4X_{2} + 2X_{3} 310
4X_{1} + 3X_{2} + X_{3} 450
X_{1} + X_{2} + X_{3} = 150
X_{1}150y_{1},
X_{2} 150y_{2},
X_{3} 150y_{3},
X_{i} is nonnegative for i = 1, 2, 3.
y_{i} is binary for i = 1, 2, 3.
Explanation:
Observe the last three constraints, and note:

If X_{i} >0 then y_{i} must be 1. This causes the addition of 400 to the value of the objective function. So the fixed cost of 400 for the process in question is applied once a certain process is utilized.

Notice that if X_{i} = 0 then y_{i }could be equal either to 0 or 1 (see the last three constraints). This is an unwanted situation because we want y_{i } = 0 when X_{i} = 0. Fortunately, this requirement will indeed take place, because of the minimization mechanism that prefers y_{i} = 0 over y_{i} = 1, since this yields a lower total cost.
Stepwise linear objective function with quantity discounts
Consider a minimization problem, where a unit cost C depends on the value of X. More specifically, C_{ }decreases as X increases. This situation occurs, for example, when discounts on the unit price are offered for increased order size.
Example 8.1: Quantity discounts (the marginal discount case)
When ordering a product a fixed cost of K_{1}=500 and a unit cost of C are incurred. The unit cost C depends on the order size X. Specifically, C = 10 for the first 100 units, while C = 8 for every unit purchased beyond that amount. Assume a maximum amount of 175 units can be ordered (possibly because of limited space).The cost function is nonlinear, because the slope changes at X = 100 (such a function is called piecewise linear). In the interval 0
K
When solving such a problem we define a variable X_{1}100 and a variable 100X_{2}175. Both, represent the total amount purchased, only that X_{2} is the amount purchased at a discount price, and therefore exists only at the range above 100 (at X = 100 the two cost functions involved are equal to one another, therefore there will be no difficulty expressing the total cost associated with this point). Define for convenience F_{1}=500+10X_{1}, and F_{2} = K + 8X_{2}. To calculate the value of the intercept for F_{2} (denote by “K”) notice that at X=100 the two functions coincide. So, F_{1}=500+10(100) = F_{2}= K+8(100). From here we have K= 700 [i.e. F_{2}=700+ 8X_{2}]. To guarantee that only one cost function is used at the appropriate range of X we’ll use binary variables, and the optimization mechanism. Here are the constraints needed:
(1) X_{1}100y_{1; }
(2) X_{2}175y_{2};
(3) y_{1}+y_{2}1.
The total inventory cost function is written as F=500y_{1}+10X_{1}+700y_{2}+8X_{2.}
The quantity stocked is either X_{1 }or X_{2}.
Explanation:

By constraint (3) at most one of the binary variables y_{i} can be equal to 1.
If y_{1}=0 then…

X_{1}=0 and the intercept “500” does not apply (see the cost function F) as appropriate.

y_{2 }= 0 or y_{2} = 1. If y_{2}= 0 then X_{2}=0 and the intercept “700” does not apply (see the cost function F) as appropriate. If y_{2}=1, then 0X_{2}175, however, it is nonoptimal to have 0_{2}100 since we are better off having 0_{1}100 (observe the function F above). Since we presume y_{1}=0, X_{1 }cannot be positive and therefore it is guaranteed that 100_{2}175 as appropriate. Consequently, the cost function is now F=700+8X_{2}.

If y_{1}=1 then…
X_{1}100, y_{2}=0, and therefore X_{2}=0 and the cost function isF =500+10X_{1.
}
Comment: Note that if the optimal solution calls for X=100, then either X_{1} = 100 and X_{2}=0, or X_{1}=0 and X_{2}=100. Of these two solutions only the first one should be selected, because a discount was given for an order size above 100).
Example 8.2: Quantity Discounts (the all units discount case)
This case differs from the last case in that discounts are given to all the units purchased, provided the order size X qualifies for the discount. When ordering a product a fixed cost of F=500 and a unit cost of C are incurred. The unit cost C depends on the order size X. Specifically, C = 10 if X does not exceed 100, while C = 8 for each unit of the X units ordered if X falls above 100 (i.e., an order of 50 units costs $500, but an order of 110 units costs $880). The cost function is nonlinear and discontinuous at 100 (see the graph below).
When solving such a problem we define a variable X_{1} that represents the amounts ordered if it is not more than 100 units, and a variable X_{2} that represents the amount ordered if it is more than 100. Assume a maximum amount of 175 units can be ordered (possibly because of limited space).
The difficulty with solving such a problem stems from the minimization mechanism. A unit cost of $8 is more favorable than a unit cost of $10, and therefore the optimal solution will prefer positive values of X_{2} over those of X_{1} even when the quantity ordered is smaller than 100. We need to prevent this situation by making sure that the proper cost function is used. This is done using binary variables. Let y_{1} be a binary variable (equals to 1 if X_{1} 100). Also, let y_{2} be a binary variable (equals to 1 if X_{2} is positive. The following constraints are needed:
(1) X_{1 }100y_{1}
(2) X_{2 }175y_{2 }
(3) X_{2 } (100+y_{2, }where is a very small positive value.
(4) y_{1 }+y_{2} 1
The_{ }cost function is F = 500y_{1}+10X_{1}+500y_{2}+8X_{2}. The quantity purchased is either X_{1} or X_{2.}_{
}See explanation in the next page
Explanation:

By constraint (4) either y_{1} or y_{2} but not both can take on the value 1. Therefore, either X_{1} or X_{2} can take on a positive value (see constraints (1) and (2)). That is, either the order size is 100 or less (constraint 1), or the order size is greater than 100 (constraint 3) but less than 175 (constraint 2).

For the cost function F, if y_{1} = y_{2} = 0 there will be no order placed (X_{1} = X_{2} = 0), and thus no fixed cost incurred, as well as no purchase cost. On the other hand, when an order is placed either the cost function has the form 500y_{1}+10X_{1} or 500y_{2}+8X_{2} as appropriate.
Review Problems

Glueco produces three types of glue on two different production lines (line 1 and line 2). Up to seven workers can work on a line at a time. Workers are paid $500 per week on production line 1, and $900 per week on production line 2. For a week of production it costs $1000 to set up production line 1, and $2000 to set up production line 2. During the week on a production line, each worker produces the number of units of glue shown in the table below. Each week, at least 120 units of glue 1, at least 150 units of glue 2, and at least 200 units of glue 3 must be produced.


Production_line_1'>Glue 1

Glue 2

Glue 3

Production line 1

20

30

40

Production line 2

50

35

45
 
Formulate an integerprogramming model to minimize the total cost of meeting weekly demands.

Consider the following additional requirements, and add a constraint that includes binary variables as needed for each.

If glue 1 is produced on line 1, then glue 2 must be produced on line 1 too

Glue 3 is produced on line 1 only if glue 1 and 2 are both produced on line 1

Glue 1 must not be produced on line 1 if glue 2 and 3 are both produced on line 1
2. Fruit computer produces two types of computers: Pear computers, and Apricot computers. A total of 1200 hours of labor and 3000 chips are available. A Pear computer requires 1 hour and 2 chips, and an Apricot computer requires 2 hours and 5 chips. A ‘Pear’ sells for $400, and an ‘Apricot’ sells for $900. If ‘Pear’ is produced new equipment is required at a cost of $5,000; similarly, if ‘Apricot’ is produced new equipment is needed at a cost of $7,000. For the production of the ‘Pear’ computer to be economically viable, at least 100 computers must be produced. Formulate the IP model that maximizes “Fruit” profit, and then solve the model.
Challenge 1: Fruit can save $75 per unit on the production cost of the Pear model provided the quantity produced exceeds 110 computers. Make necessary changes in the model, and find the optimal solution.
Challenge 2: The original solution called for the production of 600 Apricot computers and no Pear Computer. Management feels that such a plan might cause marketing problems in the future, and therefore instructs you to provide a balanced solution. Particularly, two possible options should now be investigated. (i)A solution that minimizes the larger of the two quantities produced: min max (P,A) (ii)A solution that maximizes the smaller of the two revenues, one from selling Pear computer and one from selling Apricot computer. Formulate theses two models.

The Lotus Point Condo Project will contain homes and apartments. The site can accommodate up to 10,000 dwelling units. The condo project must contain the recreation project: either the swimmingtennis complex or a sailboat marina, but not both. If a marina is built the number of homes in the project must be at least triple the number of apartments in the project. A marina will cost $1.2 million, and a swimmingtennis complex will cost $2.8 million. The developers believe that each apartment will yield revenues with an NPV of $48,000, and each home will yield revenues with an NPV of $46,000. Each home or apartment costs $40,000 to build. Formulate an integerprogramming model to help Lotus Point maximize profits.

Consider the following puzzle. You are to pick out 4 threeletter “words” from the following list: DBA, DEG, ADI, FED, GHI, BCD, FDF, and BAI.
For each word you earn a score equal to the position that the word’s third letter appears in the alphabet. For example, for the word DBA you earn a score of 1.

Formulate an integerprogramming model that maximizes the total score, subject to the constraint: the sum of alphabet positions for the first letter of each word chosen must be at least as large as the sum of alphabet positions for the second letter of each word chosen.

Repeat the formulation, this time with the constraint: the sum of alphabet positions for the first letter of each word chosen must be at least as large as the sum of alphabet positions for the second letter of each word not chosen.

A Sunco oil delivery truck contains five compartments, holding up to 2700, 2800, 1100, 1800, and 3400 gallons of fuel, respectively. Sunco must deliver three types of fuel (super, regular, and unleaded) to a customer. The demands, penalty per gallon short, and the maximum allowed shortage are given in the table below. Each compartments of the truck can carry only one type of gasoline. Formulate an integer programming model whose solution will tell Sunco how to load the truck in a way that minimizes shortage costs.


Demand

Penalty/gal short

Max. Shortage allowed

Super

2900 gal

$10

500 gal

Regular

4000 gal

$8

500 gal

Unleaded

4900 gal

$6

500 gal


The R&D department of Little Trykes has developed six new prototype tricycle models that can go into production in the coming year. The amount of plastic and the number of big and small wheels for each model, the monthly availabilities, the fixed cost of beginning production, and the unit profit excluding fixed costs are given in the following table:

Product

Unit Profit ($)

Small wheels

Big Wheels

Plastic (lb.)

Setup costs ($)

Littltryke
Pinktryke
Herotryke
Robinhood
Jeeptryke
Monster

1.50
2.00
2.25
2.75
3.00
3.50

3
1
2
2
2
0

0
2
1
1
1
3

.8
1.2
1.5
2.1
1.8
3.0

16,500
18,000
17,500
18,000
20,000
17,000

Available Monthly: 10,000 small wheels; 8,000 big wheels; 9,000 lbs of plastic.

Formulate a MILP model for this problem to determine how many units of each product should be produced if Little Trykes wishes to keep the amount of money spent on annual setups to a maximum of $70,000. (Hint: convert all production data to yearly figures.)

Assume that the maximum expenditure of $70,000 for new setups is just one of five other constraints (called goals). The other four are:

If the Herotryke is produced the Robinhood will not be produced.

At least 4 new models ought to be produced.

At least 1500 pounds of plastic should be left over each month for use in the companies other products.

If the Jeeptryke is produced, the Monster will also be produced.
Formulate each one of these goals as a constraint using binary variables as needed.

Now assume management wishes to meet at least four of the five goals mentioned above. Make the necessary changes to accommodate this requirement (you will need to add variables and a constraint).
7. The manager of a State University wants to be able to access five different files. These files are scattered on ten disks as shown in the table below. The amount of storage required by each disk is as follows: disk 1, 3K disk 2, 5K, disk 3, 1K, disk 4, 2K: disk 5, 1K, disk 6, 4K, disk 7, 3K, disk 8, 1K: disk 9, 2K: disk 10, 2K.
(a) Formulate an IP that determines a set of disks requiring the minimum amount of storage such that each file is on at least one of the disks. For a given disk, we must either store the entire disk or store none of the disk; we cannot store part of a disk.
(b) Modify your formulation so that only if disk 3 or disk 5 or both are used, then disk 2 is used.


1

2

3

4

5

6

7

8

9

10

File 1
File 2
File 3
File 4
File 5

X
X
X

X
X
X

X
X

X
X

X
X

X
X

X
X

X
X

X
X

X
X

8. You have been assigned to arrange the songs on the cassette version of Rocky Rock latest album. A cassette tape has two sides (1 and 2). The songs on each side of the cassette must total between 14 and 16 minutes in length. The length and type of each song are given in the table below. The assignment of songs to the tape must satisfy the following conditions:
a. Each side must have exactly two ballads
b. Side 1 must have at least 3 hit songs
c. Either song 5 or song 6 must be on side 1
d. If song 2 and 4 are on side 1, then song 5 must be on side 2.

Write the constraints that describe the above restrictions and requirements.

Only 3 of the 4 conditions mentioned above really need to be met. Make the necessary changes in the model.
B = Ballad; H = Hit
Song: 1 2 3 4 5 6 7 8
TYPE B H B H B H B&H H
Length 4 5 3 2 4 5 3 4
9. A product can be produced on four different machines. Each machine has a fixed setup cost (incurred only if the machine is used), a variable production cost per unit processed, and a production capacity (see the table below). A total of 2000 units of the product must be produced.
(a) Formulate an IP whose solution will tell us how to minimize total costs.

Assume there are two products that must be produced on the same four machines. The fixed costs and the capacities on the machines are the same as before, but unit production costs are 25, 15, 20, 22 dollars respectively. A machine can be dedicated to one product only. If 1000 units of the second product must be produced, reformulate your IP model.

Machine

Fixed Cost

Variable cost/unit

Capacity

1
2
3
4

$1000
920
800
700

$20
24
16
28

900
1000
1200
1600

10. WSP Publishing sells textbooks to college students. WSP has two sales reps available to assign to the AG state area. The number of college students (in thousands) in each state is given in the figure below. Each sales rep must be assigned to two adjacent states. For example, a sales rep could be assigned to A and B but not to A and D. WSP’s goal is to maximize the number of total students in the states assigned to the sales reps. Formulate an IP model whose solution will tell you where to assign sales reps.
E 56
C 42
Product

Requirement

Vendor A

Vendor B

Unit
Price

Volume Required

Unit
Price

Volume Required

1
2
3

500
1,000
2,500

$225
$220
$124
$115
$60
$56
$51

1250
251500
1600
6011000
11,000
1,0012,000
2,0012,500

$224
$214
$120
No
$54
$52

1300
301500
11,000
discount
11,500
1,5012,500

Total Capacity

2,800 units

2,400 units
 11. Universal_Technology'>Universal Technology has identified two qualified vendors with the capability to supply certain of its electronic components. For the coming year, Universal has estimated its volume requirements and has obtained all units price discounts (summarized in the table below). Universal engineers also estimated each vendor’s maximum capacity for producing these components, on the basis of available information about equipment in use and labor policies in effect. Finally, because of its limited history with vendor A, Universal has adopted a policy that permits no more than 60% of its total unit purchase on these components to come from vendor A.
(a) Find the minimum cost purchase plan for Universal.
(b) Suppose vendor A provides a new discount schedule for component 3. This one is a marginal discount as follows: Unit price = $60 on all units up to 1,000.
Unit price = $56 on the next 1,000 units.
Unit price = $51 on the next 1,000 units.
Resolve this problem with this new information.
Share with your friends: 