This assignment consists of eight problems that require you to submit a written response and a coding component.

(1) When a problem asks you to formulate you need to provide your mathematical formulation of the LP with a clear justification of variables, constraints and objective function.  You should submit your written response as a PDF to GradeScope and match the page number with the questions that you answered.  You can find detailed instructions on how to scan and submit your assignments on Canvas. If you fail to match the page to the corresponding question, the marker will not be able to view your response, and thus you will be awarded a 0 mark for the question.

(2) When a problem involves computation you must give the Python source code that produces the result, the final numerical results and an interpretation of your numerical results. The Python code and numerical results go into a Jupyter Notebook file QBUS2310-2022S2-Assignment1-code .ipynb.  You should download the file from Canvas and enter your code in the space provided.  You should submit your code as a Jupyter notebook file via Canvas.   In addition, the final numerical results and your interpretation of the results should appear in the PDF of your written response, described in (1).

Note: only problems 1 and 2 do not involve computation.

The  assignment is due by Monday,  the  5th of September,  5pm.   Late  assignments  will  not  be accepted unless a special consideration was granted.

The problems have unequal weight. Some are easy. Others, not so much.

1.  (10 points)  Formulate the following problem as LP: Given A ∈ Rm ×n , b ∈ Rm ,

m

minimize    工 max{0,ai(T)x + bi }.

i=1

The variable is x ∈ Rn .

2.  (10 points) In linear classification problems we are given two sets of points in Rn ,  {x1 , . . . ,xN } and {y1 , . . . ,yM }, and wish to find an affine function f : Rn  → R that is positive on the first set and negative on the second.  When the two sets of points cannot be linearly separated, we might seek an affine function that approximately classifies the points, for example, one that minimizes the number of points misclassified. Unfortunately, this is in general a difficult combinatorial optimization problem. One heuristic for approximate linear separation is based on support vector classifiers, which

we discussed in class (see Topic 4: Piecewise-linear optimization).

We start with the basic feasibility problem:

aT xi + b ≥ 1,    i = 1, . . . ,N,        aT yi + b ≤ −1,    i = 1, . . . ,M.

We then relax the constraints by introducing nonnegative variables u1 , . . . ,uN  and v1 , . . . ,vM , and forming the inequalities

aT xi + b ≥ 1 − ui ,    i = 1, . . . ,N,        aT yi + b ≤ −(1 − vi ),    i = 1, . . . ,M.               (1)

When u  = v  = 0, we recover the original constraints.   By making u and v large enough, these inequalities can always be made feasible. We can think of ui as a measure of how much the constraint aT xi − b ≥ 1 is violated, and similarly for vi . Our goal is to find a, b, and sparse nonnegative u and v that satisfy the inequalities (1). Formulate this problem as an LP.

3. We consider an illumination system of m lamps, at positions l1 , . . . ,lm   ∈ R2 , illuminating n flat patches. 

lamp j    lj                

rij

θij

vi+1

vi

patch i

Figure 1: Illumination system

The patches are line segments; the i-th patch is given by [vi ,vi+1] where v1 , . . . ,vn+1  ∈ R2 .  The variables in the problem are the lamp powers p1 , . . . ,pm , which can vary between 0 and 1.               The illumination at (the midpoint of) patch i is denoted Ii .  We will use a simple model for the

illumination:

Ii  = 工 aijpj ,        aij  = rij(−)2 max{cosθij , 0},                                         (2)

j=1

where rij   denotes the distance between lamp j and the midpoint of patch i, and θij   denotes the angle between the upward normal of patch i and the vector from the midpoint of patch i to lamp j , as shown in the figure.  This model takes into account “self-shading” (i.e., the fact that a patch is illuminated only by lamps in the halfspace it faces) but not shading of one patch caused by another. Of course we could use a more complex illumination model, including shading and even reflections.

This just changes the matrix relating the lamp powers to the patch illumination levels.                    The problem is to determine lamp powers that make the illumination levels close to a given desired illumination level Ides , subject to the power limits 0 ≤ pi  ≤ 1.

(a)  (8 points)  Suppose we use the maximum deviation

ϕ(p) = k a,x.,n |Ik  − Ides |

as a measure for the deviation from the desired illumination level.  Formulate the illumination problem using this criterion as a linear programming problem.

(b)  There are several suboptimal approaches based on weighted least-squares.  We consider two examples.

i.  (2 points)  Saturated least-squares .  We can solve the least-squares problem

n

minimize    工(Ik  − Ides )2

k=1

ignoring the constraints.  If the solution is not feasible, we saturate it, i.e., set pj   := 0 if pj  ≤ 0 and pj  := 1 if pj  ≥ 1.

Download the Jupyter Notebook file QBUS2310-2022S2-Assignment1-code .ipynb from the unit Canvas site with the problem data.  (The elements of A are the coefficients aij  in (2).) Compute a feasible p using this first method, and calculate ϕ(p).

ii.  (6 points)  Weighted least-squares .  We consider another least-squares problem:

n                                           m

minimize    工(Ik  − Ides )2 + µ 工(pi − 0.5)2 ,

k=1                                       i=1

where µ ≥ 0 is used to attach a cost to a deviation of the powers from the value 0.5, which lies in the middle of the power limits. For large enough µ, the solution of this problem will satisfy 0 ≤ pi  ≤ 1, i.e., be feasible for the original problem. Explain how you solve this problem in Python.  For the problem data provided in QBUS2310-2022S2-Assignment1-code .ipynb, find the smallest µ such that p becomes feasible, and calculate ϕ(p).

(c)  (4 points)  Using the same data as in part (b), solve the LP you derived in part (a).  Compare the solution with the solutions you obtained using the (weighted) least-squares methods of part (b). Explain the differences in values of ϕ(p).

4.  (10 points)  Coolbike Industries manufactures boys and girls bicycles in both 20-inch and 26-inch models.  Each week it must produce at least 200 girl models and 200 boys models.  The following table gives the unit profit and the amount of time (in minutes) required for production and assembly for each model. The production and assembly areas run two (eight-hour) shifts per day, five days per

Table 1: Bicycle manufacturing data

week.  This week there are 500 tires available for 20-inch models and 800 tires available for 26-inch models. Formulate an LP and determine Coolbike’s optimal schedule for the week. What profit will it realise for the week?

5.  (10 points)  One of the current diets that seems to produce substantial weight loss in some persons is the high protein/low carbohydrate diet advocated by such authors as Atkins in his book, Diet Revolution, and Eades and Eades in their book, Protein Power.  Although many nutritionists are concerned about the side effects of these diets, others feel the potential risks are outweighed (no pun intended) by the weight loss.

The following table gives the grams of fat, carbohydrates, and protein as well as the calorie count in four potential foods: steak (8 oz. portion), cheese (1 oz.), apples (1 medium), and whole milk (8 oz.).  Jim Blount, a 45-year-old male, has done the calculations suggested in these books and has determined that he should have a calorie intake of between 1800 and 2000 calories and protein intake of at least 100 grams, but he should not consume more than 45 grams of carbohydrates daily.  For breakfast Jim had two eggs and three strips of bacon, one piece of buttered high protein toast, and water.  This breakfast contained 390 calories, 15 grams of carbohydrates, 20 grams of protein, and 29 grams of fat.  Although these diets do not limit fat intake, Jim wishes to minimise his total fat consumed by constructing a diet for lunch and dinner consisting of only the four foods listed in the table. Formulate and solve an LP in order to recommend a diet.

Table 2: Diet problem data

6.  (10 points)  Gladstone and Associates is conducting a survey of 2000 investors for the financial ad- vising firm of William and Ryde to determine satisfaction with their services.  The investors are to be divided into four groups:

•  Group I: Large investors with William and Ryde

•  Group II: Small investors with William and Ryde

•  Group III: Large investors with other firms

•  Group IV: Small investors with other firms

The groups are further subdivided into those that will be contacted by telephone and those that will be visited in person.  Due to the different times involved in soliciting information from the various groups, the estimated cost of taking a survey depends on the group and method of survey collection. These are detailed in the following table.

Table 3: Survey costs

Formulate an LP to determine the number of investors that should be surveyed from each group by telephone and in person to minimise Gladstone and Associates’ overall total estimated cost if:

•  At least half of those surveyed invest with William and Ryde.

•  At least one-fourth are surveyed in person.

•  At least one-half of the large William and Ryde investors surveyed are contacted in person.

•  At most 40% of those surveyed are small investors.