CO 250 Spring 2024: Practice Problems 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CO 250 Spring 2024: Practice Problems 2

These are practice problems, no solutions will be provided. You are welcome to discuss solutions to these problems on Piazza and during office hours.

P2-1.  Suppose we are formulating a certain integer program problem, which includes these five variables x1 , x2 , x3 , x4 , x5 . We already have the following constraints in the IP:

0 ≤ x1 , x2 , x3  ≤ 1,    x4 , x5  ≥ 0,    x4 , x5  ≤ 100,    x1 , x2 , x3 , x4 , x5  ∈ Z

Each of the following is a condition that we want to implement for our IP. Write down constraints that formulate each condition.

(a)  Exactly one of x1 , x2 , x3  is equal to 1.

(b) If x2  is 0, then x4  is also 0.

(c) x5  is odd or x4  < x5 .

(d) Exactly one of the following holds:

• x4 + x5  ≥ 50.

• x2  = x3 .

P2-2.  A company with 100 employees had record profits in 2022, and it is paying all employees to go on some tours.  There are five possible destinations:  Australia, Bahamas, Cuba, Denmark and Egypt.  The company wants to select at most 3 of these destinations for its employees. For each destination, if it is chosen, then there is a fixed cost (the cost to run a tour regardless of the number of participants) and a per person cost (the additional cost of having each person in the tour).  There is a limit on the number of participants in a tour, and every employee must join a tour of one of the selected destinations.  The data is recorded in the following table.

Destinations               Australia        Bahamas        Cuba        Denmark       Egypt

Fixed cost                    20,000            7,000           5,000        12,000        10,000

Per person cost             2,000             1,500           1,000         3,000         1,200

Maximum # of people      30                 50               25              40              35

In addition, if Cuba and Egypt are both selected, then Bahamas cannot be selected.  The company wants to minimize the total cost of these tours.

Formulate this problem as an integer program.

P2-3.  Coach Stephen of the  WatPivots  basketball team must choose this year’s starting line-up. There are ten candidates who can play the positions Center (C), Guard (G), and/or Forward (F). Their skill levels (0 = bad to 3 = great) of shooting, rebounding and defense, and the positions that they can play are listed in the following table:

(a)  Formulate an IP that selects 5 candidates for the starting line-up that maximizes the total defensive skill level (i.e., the sum of the defensive skill levels of the candidates on the starting line-up).  In addition, at least two candidates must be able to play guard, at least two candidates must be able to play forward, and at least one candidate must be able to play center.

Coach Stephen also has additional personnel requirements.  For each of the following conditions,  state the constraints and/or variables that must be added to the IP in part (a) to satisfy that condition.

(b)  Both the average shooting skill level and the average rebounding skill level of the starting line-up must be at least 2 each.

(c) The absolute value of the difference between the total shooting skill level (of the starting line-up) and the total rebounding skill level (of the starting line-up) must be at least two.

(d) Either Bill and Hillary start, or Donald and Feridun start, or all four start. (e) Either all three of Guang, Hillary, and Justin start or none of them start.

P2-4.  For each of the following parts, explain how to use additional integer variables and linear constraints to ensure that the described conditions are satisfied.

(a)  How can one ensure that the variable w1  assumes only one of the five values

2017,  2027,  2029,  2039,  2053, i.e., ensure that w1  ∈ {2017, 2027, 2029, 2039, 2053}. (b)  Let α , β , δ , γ , θ, and λ be non-negative real-valued constants.

How can one ensure that the non-negative real-valued variables x and y satisfy either

αx + βy ≥ θ,

or

γx + δy ≥ λ    (or both)?

P2-5. WatWagen (a subsidiary of Volkswagen) manufactures three types of automobiles:  compact, midsize, and large.  The resources required for each type and the profits yielded by each type are given in the following table.

Compact    Midsize      Large

Steel required            1.5 tons      3 tons    5 tons

Labor required          30 hours   25 hours   40 hours

Profit                 $4000        $6000        $8000

WatWagen has 30,000 tons of steel and 300,000 hours of labor available.  If the firm decides to produce a type of auto, then for it to be economically feasible at least 1,000 cars of that type much be produced.

(a)  Formulate an integer programming model to maximize WatWagen’s profit.

(b) Modify your model to handle the following additional condition.   Due to marketing considerations, WatWagen can only produce the large model if it also produces either the compact or the midsize model, that is, it cannot choose to use its entire production capacity for the large model.

P2-6.  This question is inspired by the board game Power Grid.  Suppose you want to build some power plants, and buy enough fuel to power a certain number of cities.  We give a list of available power plants and their information in this table.

The goal is to build enough power plants to power at least 17 cities, while minimizing the total cost of building the plants and buying fuel.

For each plant i ∈ {1, . . . , 12}, it costs $αi to build it (the currency is called “elektro”).  Each power plant can be built at most once. There are 4 types of power plants:  coal, oil, hybrid, and renewable. In order to run plant i, you need to buy exactly βi  units of the fuel required for that plant.  (For example, plant #6 requires 3 units of coal.)  And the result is that you are able to power γi  cities.  For a hybrid power plant, the fuel can be any combination of coal and oil.  (For example, plant #11 can run using 1 unit of coal and 2 units of oil.)  For a renewable energy plant, no fuel is required.

The cost of one unit of coal is dependent on the number of units needed.  The first 3 units of coal costs $3 each, the next 3 units of coal costs $5 each, and any further units of coal costs $7 each.  Similarly for oil, the first 3 units of oil costs $4 each, the next 3 units of oil costs $6 each, and any further units of oil costs $8 each.

As an example, one possible way of powering at least 17 cities is to build plant #9, #10, and #11, for a total building cost of $132.  We need 2 units of coal for #9.  No fuel is required for #10. We decide to buy 2 units of coal and 1 unit of oil for #11.  In total, the 4 units of coal cost $14, and the 1 unit of oil cost $4.  The total cost is $150, and we are able to power 18 cities.

Model this problem as an integer program.

P2-7. A certain Canadian company is hiring agents for its call centre that responds to calls 24 hours a day.  The company divides the time into 4-hour shifts,  and each hired agent will work 2 consecutive shifts.  There are 3 types of agents that they can hire:  English-only, French-only, or bilingual.  Based on historical data, the company sets the minimum number of agents speaking English or French for each shift in the table here.

Shift                       English               French

1am - 5am (*)             5                       7

5am - 9am (*)            15                     17

9am - 1pm                 35                     37

1pm - 5pm                 55                     47

5pm - 9pm (*)            45                     27

9pm - 1am (*)            25                     17

A bilingual agent counts as both an English agent and a French agent for this table.  For example, the  1am - 5am shift can be completed by 3 English-only,  5 French-only,  and 2 bilingual agents.

The base salary for any hired agent is $20/hour (or $80 per shift).  French-only agents will have their salaries multiplied by 1.3, and bilingual agents will have their salaries multiplied by 1.7. In addition, any agent that works during shifts marked by (*) will have their salaries multiplied by 1.5 for that shift. For example, a bilingual agent working the 5pm - 9pm shift will receive $20 · 1.7 · 1.5 = $51 per hour.

The goal is find a way of hiring agents that satisfies all the constraints while minimizing the total salary paid to all agents. Use an integer program to model this problem.

P2-8. A miniatures enthusiast has rented out a 3D printer for the day to print out some of their favourite miniature figures.   The  printer  can be used from  8am to  12pm,  and  also from 12:30pm to 5pm. There are 500 grams of filament available (the filament is like the  “ink” for the printer). The printer can only print one figure at a time. For each figure that you print, it is either printed completely before 12, or it is printed completely after 12:30.

There are 7 possible figures that can be printed, say the figures are labeled 1, . . . , 7.  For each figure i, it takes ti  hours to print it on the 3D printer, and uses fi  grams of filament.  Once the figure is produced, it can be sold for a profit of $pi.  Also, each figure can only be printed at most once. The data are recorded here.

Figure i             1              2                3                4                  5               6               7

Time ti             0.5           1.2               3              1.7               2.5             1.5             2.1

Filament fi         35            75             200            120              180              95            140

Profit pi             25            30             110             70               100              45             75

Write an integer program that satisfies all the constraints while maximizing the total profit.

P2-9. A company wants to form three different teams A,B,C from a pool of 7 employees, which we represent as the set E = {1, . . . , 7}.  Each employee i has a certain number of years αi of experience at the company, and has βi  as their current annual salary.  Note that αi ,βi  are constants, but you may assume that 0 ≤ αi  ≤ 10 and 0 ≤ βi  ≤ 100000.

We define binary variables xij  for all i ∈ E and j ∈ {A,B, C} to represent

xij = { 1 employee i is on team j

           0 otherwise

Suppose we are writing an integer program, and we have already defined the constraints which ensure that each xij  is a binary variable.

For each of the following conditions, give constraints that correctly formulate it. You may use additional variables. You need to explain why your constrains work.  (Note: Each condition is independent of each other.)

(a)  Each employee is in either 1 or 2 teams.

(b)  The average salary for team A is at least 50000.

(c)  The difference between the total experience of any two teams is at most 2 years.

(d) At least 2 of these 3 conditions hold:

•  Team A has at least 5 years of experience.

•  Team B has at most 250000 in combined annual salary.

•  Teams B and C have the same number of employees.