IE 342

Instructor: O. Örsan Özener

Recitation 2

1 Integer Programming - Modeling

Question 1
A small company produces pallet both skilled workers and unskilled workers. The workforce of the
company must not exceed 25 people and the company must make at least 600 pallets per day to satisfy
customer demand. On an average, a skilled person can make 35 pallets per day and an unskilled worker
20 per day. Because of the regulations, number of the apprentices must be less than number of the
skilled workers but more than half of the number of skilled workers. Skilled workers are employed with
1500TL per month and apprentices are employed 700TL per month. What is the optimum number of
workers to minimize the cost?
Question 2
A library must build shelving to shelve 200 4-inch high books, 100 8-inch high books, 80 12-inch high
books. Each book is 0.5 inch thick. The library has several ways to store the books. For example, an
8-inch high shelf may be built to store all books of height less than or equal to 8 inches, and a 12-inch
high shelf may be built for the 12-inch books. Alternatively, a 12-inch high shelf might be built to store
all books. The library believes it costs $2300 to build a shelf and that a cost of $5 per square inch is
incurred for book storage. (Assume that the area required to store a book is given by height of storage
area times book’s thickness). Formulate the problem as an IP to find how should the library shelve the
books at minimum cost.
Question 3
A young couple, Sirin and Ferhat, wants to divide their main household chores (shopping, cooking,
dishwashing, and laundering) between them so that each has two tasks but the total time they spend
on household duties is kept to a minimum. Their efficiencies on these tasks differ, where the time each
would need to perform the task is given in Table 1:

Table 1: Hours per week needed

Shopping Cooking Dishwashing Laundering
Sirin 4.5 7.8 3.6 2.9
Ferhat 4.9 7.2 4.3 3.1

Formulate an IP for this couple’s problem.

Question 4
I have the following clothes options available to me:
I have $200 to spend, and I want to buy as many articles of clothing as possible. But I have the following
constraints:
• I can buy at most one red item
• I must buy exactly two ugly items
• The number of shirts must equal the number of pants.
• I must buy at least one nice item.
Formulate an integer program.
Question 5
In a product-mix problem, two products, A and B consume kA and kB of some resource per unit finished,
respectively. The scarce resource availability is K. Suppose, also that A and B can be produced either
IE 342
Recitation 2

Clothing Cost
nice red shirt $ 30
nice blue shirt $ 25
nice black shirt $ 35
nice red pants $ 50
nice blue pants $ 55
nice black pants $ 75
ugly red shirt $ 30
ugly blue shirt $ 25
ugly black shirt $ 35
ugly red pants $ 50
ugly blue pants $ 55
ugly lack pants $ 75

at a level of more than lA and lB , respectively, or not at all. Unit profits are PA and PB . Formulate a
mathematical programming model to maximize total profit.
Question 6
I have n integers: a1 , a2 , a3 , , an . Suppose I wish to assign some numbers to Set 1, and some numbers to
Set 2, in order to minimize the difference in the sum of numbers in each set. Write an integer program
to solve this problem. For instance, if n = 4, a1 = 2, a2 = 3, a3 = 6, a4 = 10, then I could assign numbers
a1 , a2 , and a3 to Set 1, and a4 to Set 2, with a difference of 11 − 10 = 1.
Question 7
Truck deliveries are made to five locations. A total of six routes are available. The following information
summarizes the location that can be reached by each route:

• Route 1: 1, 2, 3, 4
• Route 2: 1, 3, 4, 5
• Route 3: 1, 2, 5
• Route 4: 2, 3, 5
• Route 5: 1, 3, 5
• Route 6: 3, 4
The delivery distances of the routes are 10, 5, 9, 13, 8, and 6 miles, respectively. It is desired to make
exactly one delivery to each location. Formulate an IP model that will result in the shortest total
distance routing.

Table 2: Cost Information

12 13 6 0 1
8 4 9 1 2
2 6 6 0 1
3 5 2 1 8
8 0 5 10 8
2 0 3 4 1

Page 2
IE 342
Recitation 2

Question 8
Using a mixed integer programming system, solve an instance of the uncapacitated facility location
problem with 5 depots and 6 clients, where fj is the cost of opening depot j, and cij is the cost of
satisfying all of client i’s demand from depot j, with f = (4,3,4,4,7) and the cost information is given in
Table 2.
Question 9
The R&D Division of a company has been developing four possible new product lines. Management
must now make a decision as to which of these four products actually will be produced and at what
levels. Therefore, they have asked the OR Department to formulate a mathematical programming model
to find the most profitable product mix. A substantial cost is associated with beginning the production
of any product. The marginal net revenue from each unit produced is shown on Table 3 (in $):

Table 3: Product Information

Product 1 2 3 4
Startup cost 50,000 40,000 70,000 60,000
Marginal revenue 70 60 90 80

The following policy constraints are imposed by the management:

• No more than two products can be produced.
• Either product 3 or 4 can be produced only if either product 1 or 2 is produced.
• Either 5x1 + 3x2 + 6x3 + 4x4 ≤ 6000 or 4x1 + 6x2 + 3x3 + 5x4 ≤ 6000.
• If product 2 is produced more than 300 units and product 1 is not produced, product 3 can be
produced at most 500 units.
• If product 1 is produced more than 500 units, then product 2 cannot be produced or should be
produced more than 400 units
Formulate an IP for this problem.
Question 10
Suppose that you are interested in choosing a set of investments 1, 2, ...7 using 0-1 variables. Model the
following constraints:
• You cannot invest in all of them.
• You must choose at least one of them.
• Investment 1 cannot be chosen if investment 3 is chosen.
• Investment 4 can be chosen only if investment 2 is also chosen.
• You must choose either both investments 1 and 5 or else neither.
• You must choose either at least one of the investments in set 1,2,3 or at least two investments from
set 2,4,5,6.
Question 11
A toy manufacturer is planning to produce new toys. The setup cost of the production facilities and the
unit profit for each toy are given below:
The company has two factories that are capable of producing these toys. In order to avoid doubling
the setup cost only one factory could be used. The production rates of each toy are given below (in
units/hour):

Page 3
IE 342
Recitation 2

Toy Setup cost Profit

1 45000 12
2 76000 16

Toy 1 Toy 2
Factory 1 52 38
Factory 2 42 23

Factories 1 and 2, respectively, have 480 and 720 hours of production time available for the production
of these toys. The manufacturer wants to know which of the new toys to produce, where and how many
of each (if any) should be produced so as to maximize the total profit. Formulate the problem as an
integer program.
Question 12
Jason, as always, has a busy schedule over the weekend. He has to schedule a four hour brunch (yes,
a four hour brunch), a three hour dinner, a four hour dinner, a three hour coffee break (at Starbucks
Bebek), and two one hour spinning sessions. Obviously, these activities should be scheduled on either
Saturday and Sunday (assume that each day has 8 hours). Also, the brunch should be the first activity
of the day and the dinners should be the last activities of the corresponding days. Again, both dinners
cannot be scheduled on the same day. Formulate an IP to help Jason to schedule these activities or
convince him that this is too much for a given weekend (not feasible).
Question 13
In a container terminal, five container carrier vessels are waiting for the unloading their cargo to the
dock. The unloading time of a vessel is based on the total capacity and the current load on its deck and
storage areas. The unloading times of the vessels and the due dates of their cargo are given in the table
below.
(a) Formulate an IP that determine the best sequence of vessels that minimizes the average tardiness.
(b) Formulate an IP that determine the best sequence of vessels that minimizes the maximum tardiness.

Vessel Number Unloading Time (in hours) Due Date (in hours)
1 9 17
2 17 33
3 5 41
4 11 21
5 14 40

Question 14
A software company is planning to release an anti virus software for home and professional users. Before
the final release to the market, the company wants test the software using beta testers. First 1000 beta
testers cost the company $10 each and the next 1000 beta testers cost $8 each and finally last 1000 beta
testers cost $5 each. The company may sell this product to the home users if the number of beta testers
is at least 1500 and to the professional users if the number of beta testers is at least 2500. The selling
price of the software for home and professional users will be $45 and $100 respectively. The expected
market demand is 10,000 for the home users and 5,000 for the professional users. The company has
enough employees to give after sales support to 12,000 home users and professional users require %50
more support hours compared to home users.

Page 4
IE 342
Recitation 2

(a) Assuming that the company can hire beta testers only at the integer multiples of 1000, formulate
an IP to maximize the profits of the company.
(b) Assuming that the company may hire any integer number of beta tester, formulate an IP to maximize
the profits of the company.
Question 15
Suppose a Constructor Company is employed to restore the residence of the government and they
need a scheduling to assign the workers appropriate tasks depends on their skills. The restoration of
the residence is divided into a number of tasks and each task requires number of skills. (gardening,
plumbing). Depending on skills, a worker might or might not perform a task. In addition to, each
worker can be hired for a cost that depends on his qualifications and the problem includes selecting a set
of workers in order to perform tasks, while minimizing the total cost. Formulate the mathematical model
to make sure all the tasks are performed. Assume there are available 15 workers and the information is
on Table 15.

Number of Workers
Tasks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Carpentry x x x x x
Plumbing x x x x x
Ceiling x x x x x
Electricity x x x x x
Heating x x x x x
Insulation x x x x
Roofing x x x x x
Painting x x x x x
Windows x x x x
Face x x x x
Cost ($1000) 1 1 2 3 2 1 2 1 4 3 2 3 1 1 2

Question 16
Marks and Spencer is considering to build warehouses in a number of locations to supply its stores . Each
possible warehouse includes a fixed cost and has a maximum capacity to define how many stores it may
support. In addition to, each store must be supplied by exactly one warehouse and the transportation
cost to supply a store can be changed depends on the selected warehouse. Assume there are 5 possible
warehouses to build and 10 stores to be supplied. Formulate an integer programming to decide which
warehouses to build and which warehouse assigns to which store in order to minimize the total cost.
Assume that fixed maintenance cost to open a warehouse is same for each warehouse and it is $100000.
The required information is on Table 16.
Question 17
A wood company has four machines to assign four tasks. Any task can be assigned on any machine and
each task requires some processing time on any machine. The requirement time for the each task to be
assigned on each machine is shown on the Table 17.
Formulate the mathematical model to minimize the total setup time needed to process of all four tasks
Question 18
A local football team Ozu United wants to join a futsal World Cup. Sir Alex Ferguson is the coach of

Page 5
IE 342
Recitation 2

Bursa Istanbul Ankara Konya Izmir

Capacity 1 4 2 1 3
Store 1 20 24 11 25 30
Store 2 28 27 82 83 74
Store 3 74 97 71 96 70
Store 4 2 55 73 69 61
Store 5 46 96 59 83 4
Store 6 42 22 29 67 59
Store 7 1 5 73 59 56
Store 8 10 73 13 43 96
Store 9 93 35 63 85 46
Store 10 47 65 55 71 95

Machine Number Task 1 Task 2 Task 3 Task 4

1 13 4 7 6
2 1 11 5 4
3 6 7 2 8
4 1 3 5 9

Player Number Goal Rate Performance Position

Dino Zoff 1 20 70 Goalkeeper
Zubizeretta 2 15 75 Goalkeeper
Beckenbauer 3 50 90 Defender/Midfielder
Paulo Maldini 4 35 85 Defender
Laurent Blanc 5 40 70 Defender
Michel Platini 6 80 80 Midfielder
Zico 7 75 85 Midfielder/Forward
Rivaldo 8 85 80 Midfielder/forward
Maradona 9 95 90 Midfielder/Forward
Pele 10 99 90 Forward

Page 6
IE 342
Recitation 2

the team and he is trying to choose its starting line-up six players from ten players so as the maximize
goal rate. The table includes some information about the footballers’ skills to choose them.
The starting line-up must satisfy the following constraints:
• At least one goalkeeper must start.
• Either Zico or Platini must be held in reserve.
• Only one forward can start.
• If Pele or Maradona starts, then Rivaldo cannot start.
• If Beckenbauer starts, then Blanc and Zico cannot start.
• At least two of Maldini, Zico, Pele and Platini must start.

Formulate a mathematical model to help Sir Alex Ferguson.

Question 19
IsPark is deciding to divide into two spaces its available park space (7200 sq .ft) in Cekmekoy. Some
spaces are for small cars and the rest of the spaces are for large cars. It is allowed 90 sq. Ft for each
small car and 120 sq. Ft for each large car. Every car must occupy a space of the appropriate size. It
is estimated that the cars can park at any given time and the ratio of the small cars to large cars will
be neither less than 2:3 or greater than 2:1. Find the number of spaces of each type to maximize the
number of cars that may be parked.
Question 20
A combinatorial auction is an auction in which participants can place bids on sets of items, instead of
placing bids on individual items. A combinatorial auction is useful in many situations. For example,
consider the problem of an airline company buying takeoff and landing slots at an airport: clearly, the
value of a single slot may be small if the slot is taken by itself, but the value may be much larger if
several slots can be bought at the same time, allowing the company to setup flight routes according to
the desired timetable. Thus, the airport wants to sell its available slots to airline companies maximizing
its own profit (i.e. the total value at which the slots are sold), allowing airlines to bid on sets of items
and choosing the most profitable combination of bids among the received ones. Many other examples
exist. In this problem, we study a simple formulation for a combinatorial auction.
Consider a set composed by 6 items, labeled for simplicity: {1, 2, 3, 4, 5, 6}. We auction off these items
and receive the following bids, where each bid is placed on a subset of the items and assigns a value to
the whole subset:

• Bid 1: subset {1, 5} valued at 10.

• Bid 2: subset {1, 2, 4} valued at 20.
• Bid 3: subset {3} valued at 8.
• Bid 4: subset {5} valued at 4.
• Bid 5: subset {2, 4} valued at 15.
• Bid 6: subset {2, 3, 4, 5} valued at 30.
• Bid 7: subset {1, 2, 3} valued at 18.
• Bid 8: subset {2, 4, 6} valued at 25.
• Bid 9: subset {3, 5, 6} valued at 16.

Page 7
IE 342
Recitation 2

(a) Formulate an integer program to choose the subset of bids that maximizes profit for the auctioneer,
i.e. the total value for which the items are sold is maximum. We remark that each item can be sold
at most once, and that bids cannot be split, that is: a bid for items {1, 2} can only be accepted if
both item 1 and 2 are available.
(b) Suppose now that we are still auctioning off the set of items {1, 2, 3, 4, 5}, but now we have two
copies each of items 1, 2, 3. In other words, the set of items for auctions looks like this: {1, 1, 2,
2, 3, 3, 4, 5, 6}. The set of received bids does not change, and each bid can only be accepted at
most once. Modify your answer to the previous question to take into account the new availability
of items.

Page 8