Homework 1: Linear Programming

    0. [2 points] Warm-up. Model the following problem in JuMP.

maximize
5x1   x2 + 15x3
x1;x2;x3
2x1    x2 + x3
subject to:


0   xj   3; j 2 f1; 2; 3g

        (a) Write Julia code to solve this problem using Clp, ECOS, and SCS solvers. Do all give the same result?

        (b) Which solver is fastest (use the @time macro in front of the optimize!() statement to check)? Can you say why?

        (c) Consider changing the rst constraint to 2x1 x2 + x3 + , where is some real number. For all values of larger than a certain threshold value, the problem with become infeasible. (In Julia, the solver will terminate with status INFEASIBLE.) What is this threshold value of ? Can you explain by examining the constraints why this value makes the problem infeasible?


    2. [2 points] Standard Form Recall that in class we de ned the \standard form" of a linear program to be
min cT x    subject to Ax    b; x    0:

Consider the following linear program which is NOT in standard form:

min 3z1
+ 2z2
z3
subject to 2z1   z2
+ 3z3
= 10;
0   z2    5;
5   z3    20:

    a) Transform the given LP into our standard form. How are the components of x related to the components of z = (z1; z2; z3)? Write out explicity the quantities A, b, c.

    b) Solve both versions of the LP using JuMP and show that you can recover the optimal z and objective value by solving your transformed version of the LP.








1 of 2
CS/ECE/ISyE 524    Introduction to Optimization    Steve Wright,    Spring 2021


    3. [2 points] Polyhedron modeling. We saw that the set of x such that Ax b where A 2 Rm n and b 2 Rm describes a polyhedron. Find A and b such that Ax b describes the diamond-shaped polyhedron in three dimensions (that is, x 2 R3) that is de ned by the following six vertices:

(1; 1; 0); (1;    1; 0); (  1;    1; 0); (  1; 1; 0); (0; 0; 1); (0; 0;    1):

(It might help to sketch this    gure!)


    4. [3 points] Manufacturing transistors. Silicon Valley Corporation (Silvco) manufactures transis-tors. An important aspect of the manufacturing process is the melting of the element germanium in a furnace. Unfortunately, the melting process yields germanium of highly variable quality. The results of the process can be classi ed into ve grades: \grade A", \grade B", \grade C", \grade D", and \defective". Two methods can be used for the melting. Method 1 costs $50 per transistor, and Method 2 costs $70 per transistor. The qualities of germanium produced by the melting are shown in the following table (as percentage yields).


Method 1
Method 2



defective
30
20
grade D
30
20
grade C
20
25
grade B
15
20
grade A
5
15




Silvco can re re melted germanium in an attempt to improve its quality. It costs $25 to re re the melted germanium for one transistor. The results of the re ring process are shown in the table below. For example, if grade B germanium is re red, 50% of the resulting germanium will still be grade B and 50% will be grade A.


defective
grade D
grade C
grade B
grade A






defective
30
25
15
20
10
grade D

30
30
20
20
grade C


40
30
30
grade B



50
50







Silvco has su cient furnace capacity to melt or re re germanium for at most 20,000 transistors per month. Silvco’s monthly demands are for 1000 grade A transistors, 2000 grade B transistors, 3000 grade C transistors, and 3000 grade D transistors.

Assuming that just one stage of re ring is allowed, model the melting/re ring process and determine the minimum cost of germanium processing required to meet the demands.

Hint: Remember to start by asking: What are the decision variables? Then work through how the decision variables relate to the data in the tables and the text. In particular, you will need to de ne how the objective (total cost) is related to the decision variables.















2 of 2