Isds 440 Dr. Z. Goldstein Notes on Integer Linear Programming with Binary Variables Introduction



Download 106.82 Kb.
Date31.07.2017
Size106.82 Kb.
#25248
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 non-optimal 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 Xi can get either the value 0 or some U>0? Answer: Use the constraint Xj = Uyj, where yj is binary. Note that if


yj = 0 then Xj = 0, and if yj = 1 then Xj = U. A variation of this idea is: Xj can take only the value 0 or values not less than U. Two constraints are required: Uyj  Xj Myj, where M is the largest value Xj can get. Note that when yj = 1 U  Xj  M (but M does not limit Xj being the largest value Xj can have), and when yj = 0, Xj = 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 yA yB, where yA and yB 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 yA1yB.
Selecting k out of m

Selecting k out of m activities is a condition formulated by y1+y2+…+ym = k, where yi are binary (equals to 1 when an activity is chosen).


Variations of this condition are:

(i) At most k activities should be chosen: y1+y2+…+ym  k

(ii) At least k activities should be chosen: y1+y2+…+ym  k
Example 3: Seven different R&D projects are considered by management. Only 5 will be executed. This situation is formulated by y1+y2+…+y7 = 5, yi 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 4X1 + 3X2 + 5X3

S.T. (1) X1+ X2  100

(2) 2X1+ 4X3 200

(3) 3X1+3X2+ X3 300

First convert the third constraint into two inequality type constraints as follows:

3X1+3X2+ X3 300, and 3X1+3X2+ X3 300. Then, for a “greater then” type constraint, subtract My and for a “less than” type constraint add My (where ‘M’ is a very large number). Complete the modifications as follows:

(1’) X1+ X2   100 – My1

(2’) 2X1+ 4X3  200 + My2

(3’) 3X1+3X2+ X3 300 – My3

(3”) 3X1+3X2+ X3 300 + My3

(4’) y1 + y2 + y3 = 1

Explanation:


A constraint is satisfied when yi = 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 yi = 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 S1 to have certain relationships with members of set S2. 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+D1 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+E1 Region 3

A+C+D+E 2 Two bases are within 10 minutes of region 4

A+D1 Region 5

A+E1 Region 6


Observation: Typical constraints in covering problems have the form y1+y2+…+yn 1 (yi are binary variables).

Example 6

A moving and storage company is allocating five long-distance 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 Xi +…+Xj = 1.

Define Xi as binary variables (=1 if route “i” is selected).
The model

Loads
Routs

1

2

3

4

1

2

3



4

5













Minimize 4525X1+2960X2+3170X3+5230X4

S.T. X1 + X4 = 1 (Load 1)

X2 + X3 = 1 (Load 2)

X1 + X2 = 1 (Load 3)

X2 + X3 + X4 = 1 (Load 4)

X3 + X4 = 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 yA  yC, yB  yC, yA + yB  yC (yi 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 yA  yC, yB  yC, yA + yB  yC + 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 non-linear.


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 Xi as the amount produced in each process.


Min 15X1 + 8X2 + 11X3

S.T. 2X1 + 4X2 + 2X3  310

4X1 + 3X2 + X3  450

X1 + X2 + X3 = 150

Xi is non-negative for i = 1, 2, 3.
(b) Define yi as a binary variable taking the value 1 if process ‘i’ is used (i = 1, 2, 3).
Min 15X1 + 8X2 + 11X3 + 400y1 + 400y2 + 400y3

S.T. 2X1 + 4X2 + 2X3  310

4X1 + 3X2 + X3  450

X1 + X2 + X3 = 150


X1150y1,
X2 150y2,

X3 150y3,

Xi is non-negative for i = 1, 2, 3.

yi is binary for i = 1, 2, 3.


Explanation:

Observe the last three constraints, and note:

  1. If Xi >0 then yi 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.

  2. Notice that if Xi = 0 then yi could be equal either to 0 or 1 (see the last three constraints). This is an unwanted situation because we want yi = 0 when Xi = 0. Fortunately, this requirement will indeed take place, because of the minimization mechanism that prefers yi = 0 over yi = 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 K1=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 non-linear, 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 X1100 and a variable 100X2175. Both, represent the total amount purchased, only that X2 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 F1=500+10X1, and F2 = K + 8X2. To calculate the value of the intercept for F2 (denote by “K”) notice that at X=100 the two functions coincide. So, F1=500+10(100) = F2= K+8(100). From here we have K= 700 [i.e. F2=700+ 8X2]. 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) X1100y1;

(2) X2175y2;

(3) y1+y21.

The total inventory cost function is written as F=500y1+10X1+700y2+8X2.

The quantity stocked is either X1 or X2.
Explanation:


  1. By constraint (3) at most one of the binary variables yi can be equal to 1.
    If y1=0 then…

  • X1=0 and the intercept “500” does not apply (see the cost function F) as appropriate.

  • y2 = 0 or y2 = 1. If y2= 0 then X2=0 and the intercept “700” does not apply (see the cost function F) as appropriate. If y2=1, then 0X2175, however, it is non-optimal to have 02100 since we are better off having 01100 (observe the function F above). Since we presume y1=0, X1 cannot be positive and therefore it is guaranteed that 1002175 as appropriate. Consequently, the cost function is now F=700+8X2.

  1. If y1=1 then…
    X1100, y2=0, and therefore X2=0 and the cost function isF =500+10X1.



Comment: Note that if the optimal solution calls for X=100, then either X1 = 100 and X2=0, or X1=0 and X2=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 non-linear and discontinuous at 100 (see the graph below).

When solving such a problem we define a variable X1 that represents the amounts ordered if it is not more than 100 units, and a variable X2 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 X2 over those of X1 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 y1 be a binary variable (equals to 1 if X1  100). Also, let y2 be a binary variable (equals to 1 if X2 is positive. The following constraints are needed:


(1) X1 100y1

(2) X2 175y2

(3) X2  (100+y2, where is a very small positive value.



(4) y1 +y2  1
The cost function is F = 500y1+10X1+500y2+8X2. The quantity purchased is either X­1 or X2.
See explanation in the next page

Explanation:

  1. By constraint (4) either y1 or y2 but not both can take on the value 1. Therefore, either X1 or X2 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).

  2. For the cost function F, if y1 = y2 = 0 there will be no order placed (X1 = X2 = 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 500y1+10X1 or 500y2+8X2 as appropriate.

Review Problems


  1. 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

  1. Formulate an integer-programming model to minimize the total cost of meeting weekly demands.

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

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

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

      3. 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.



      1. 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 swimming-tennis 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 swimming-tennis 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 integer-programming model to help Lotus Point maximize profits.




      1. Consider the following puzzle. You are to pick out 4 three-letter “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.

      1. Formulate an integer-programming 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.

      2. 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.




      1. 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




    1. 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.


  1. 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.)

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

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

      2. At least 4 new models ought to be produced.

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

      4. 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.

  1. 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.


  1. Write the constraints that describe the above restrictions and requirements.

  2. 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.



  1. 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 A-G 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

1-250

251-500
1-600

601-1000
1-1,000

1,001-2,000

2,001-2,500


$224

$214
$120

No
$54

$52


1-300

301-500
1-1,000

discount
1-1,500

1,501-2,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.
Re-solve this problem with this new information.





Download 106.82 Kb.

Share with your friends:



The database is protected by copyright ©ininet.org 2024
send message
    Main page
total amount
total cost