Description

5/5 - (1 vote)

ISYE524 Homework 1

Problem 1 – Getting Started with Julia/JuMP

Model the following problem in JuMP:

Solve this problem using Clp, ECOS, and SCS solvers.

$\begin{align*}$

max s.t. 3 x 1 2 x 1 x 1 x 1 x 1 + + + 2 x 2 x 2 x 2 x 2 \leq \leq \leq \geq \geq 100804000

\end{align*}$

Which solver is most accurate (gets closest to the “right” answer)?
Which is fastest (use the @time macro)? NOTE: you should notice it takes longer to solve the problem the first time you run your code, and goes much faster if you re-sovle subsequent times. The first time you run the code, the solver takes extra time to compile/”load” the model (it doesn’t repeat the compilation step in future re-solves).
- Can you speculate as to why?
If there is no clear difference between the solvers, can you think of some factors that might contribute to solver speed differences?

Problem 2 – Honest Work

Farmer Brandt must determine how many acres of corn and hay to plant this year. An acre of hay yields 25 bushels of hay and requires 10 hours of labor per week. An acre of corn yields 10 bushels of corn and requires 4 hours of labor per week. All hay can be sold at $4 a bushel, and all corn can be sold at $3 a bushel. Seven acres of land and 40 hours per week of labor are available. Government regulations require that at least 30 bushels of corn be produced during the current year.

(a) Formulate a linear program to help Famer Brandt plan his crops for the upcoming season to maximize his revenue. State the math model, then code and solve the model using Julia. (Hint: you should have two decision variables).

(b) Code the same model once again, this time separating the parameters from the solution as we did in class (see Top Brass examples). Confirm that you obtain the same solution as in part (a).

(c) Solve the problem graphically by plotting the feasible set and at least two isocost lines for the objective function. Confirm that you obtain the same solution as in the previous parts.

Problem 3 – OptiMine

A mining company (“OptiMine”) is planning mine operations for the next week. There are 10 different mine locations available for ore extraction. OptiMine needs to mine 3,000 tons of ore to meet demand. Each mine location has a total number of tons of ore available. Mining at each location has an associated cost per ton. Finally, ore extracted from each mine contains a different percentage of different elements (e.g., carbon, gold). The cost, ore available, and percentage of elements in the ore at each mining location are given in the .csv file “mine.csv.” A sample of the data is given in the table below. There is a minimum percentage of each element required across the total ore extracted, also given in the .csv file.

The data is provided in “mine.csv” on Canvas. You can use the code snippet provided below to read the .csv files and load them into Julia.

Mine	Cu %	Su %	C %	Ar %	Au %	Cost per ton	Max tons avail
Min %	11	12	13	10	9
1	10	8	8	13	10	20	500
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋱$

(a) Formulate a linear program to help OptiMine plan mining operations to meet requriments at a minimal cost. Give a general form (parameters only — no numbers) of the math model.

(b) Implement and solve this instance of the model in Julia/JuMP. Display the optimal objective value and the optimal variable values.

#You might need to run "Pkg.add(...)" before using these packages
using DataFrames, CSV, NamedArrays

#Load the data file
df = CSV.read("mine.csv",DataFrame,delim=',');

# create a list of mines
mines = convert(Array,df[2:end,1])

# create a list of elements
elements = 1:5

# create a dictionary of the total cost of mining at each location
cost_to_mine = Dict(zip(mines,df[2:end,7]))

# create a dictionary of the max tons available at each location
max_avail = Dict(zip(mines,df[2:end,8]))

# create a dictionary of the min % of each element
min_req = Dict(zip(elements,df[1,2:6]))

# create a matrix of the % of each element at each loation
mine_element_matrix = Matrix(df[2:end,2:6])

# rows are mines, columns are elements
mine_element_array = NamedArray(mine_element_matrix, (mines, elements),("mines","elements"))
;

Problem 4 – Standard Form

Consider the following LP:

min 2 x 1 - x 2 + 3 x 3 - 2 x 4 s.t. 3 x 2 - x 3 + 4 x 4 4 x 1 - 7 x 2 + x 3 - x 4 x 1 - 3 x 3 + 8 x 4 x 1, x 4 \geq 0 x 2, x 3 \geq 10 = 5 \leq 3 Unrestricted in Sign (Free)

(a) Convert the problem to standard form.

(b) What are $A$ , $b$ , $c$ ,and $x$ in this problem? Clearly indicate how the decision variables of your transformed LP relate to those of the original LP.

(c) Solve the standard-form LP in Julia and report the objective value and the value of each decision variable in an optimal solution to the original LP.

ISYE524 Homework 2

Submission requirements

Upload a single PDF or HTML file of your IJulia notebook for this entire assigment. Clearly denote which question each section of your file corresponds to.

Problem 1 – The Spice Must Flow

House Atreides mines spice at a set of locations $M$ on Arrakis and ships it to a set of Houses $H$ . The cost per ton of producing spice at mine $m \in M$ is $p_{m}$ . The sand content (in percent) of the spice at mine $m \in M$ is $a_{m}$ , the sulfur content of the spice at mine $m \in M$ is $s_{m}$ , and the total tons of spice available at mine $m \in M$ is $u_{m}$ . Each House $h \in H$ requires $d_{h}$ tons of spice. The cost (in Solari) of shipping a ton of spice from mine $m \in M$ to House $h \in H$ is $c_{m h}$ . It is required that the spice shipped to each House contain at most $α$ % sand and at most $γ$ % sulfur in total.

Formulate a linear programming model that minimizes the cost of meeting demands of the Houses. Be sure to clearly define the decision variables. (Hint: you will need variables representing the amount of spice shipped from each mine to each house.) Implement this general model in Julia and use it to solve the instance with data that is given along with this homework assignment in the file “spice-data.ipnyb.”

Problem 2 – Spice Refineries

In the distant future, spice is one of the most valuable commodities that exists. However, it must be properly refined by House Atreides before leaving Arrakis to be sold across the galaxy. In order to refine the spice, House Atreides must operate its many refineries, which require water. In order to increase the output of spice at a refinery, there is a “cost” of 120 gallons of water per ton to operate the refinery at the higher output level. If instead the refinery decreases production level of spice by 1 ton/day, the cost per ton is only 50 gallons of water. (E.g., if current production level is 10 tons and the refinery wants to increase output to 12 tons, the cost is 2 tons * 120 gallons/ton = 240 gallons.)

Demand for spice in the next week is given in the following table:

Day ( $t$ )	Demand (tons)
1	40
2	80
3	200
4	250
5	120
6	60
7	30

The refinery is currently operating at an output level of 40 tons of spice per day. There are 10 tons of refined spice in inventory right now (day “0”). It costs 20 gallons of water per ton of spice to store up to 80 tons of spice in inventory. To operate a larger storage unit, additional tons (above 80) can be stored at a cost of 50 gallons of water per ton of spice. (Inventory is checked at the end of each day.) If the refinery is unable to meet demand for a given day, House Atreides will be penalized by the Empire and must pay 100 gallons of water per ton of spice short.

Formulate and solve a linear program to determine the optimal production schedule to help House Atreides minimize the amount of water needed to operate the refineries. Give a mathematical formulation of the model as well as your Julia code and solution values.

Problem 3 – Dice Delivery

You recently discovered you can make some extra money by leasing polyhedral dice to a group of friends playing Dungeons and Dragons. You recently lent 85 dice to 10 different people. Unforuntately, you made some mistakes and gave some people the wrong number of dice. The players have agreed to help with redistributing the dice, as long as they don’t have to drive very far. Suppose that the time to drive between each pair of people is 1.5 times the Euclidean distance to travel between each location given in the table below. The cost of gas is $0.40 per minute of driving. Although it is a bad strategy, also assume that the cost of traveling is per die (so transporting 2 dice a given distance costs 2 $\times$ 1.5 $\times$ 0.4 $\times$ distance).

Player	1	2	3	4	5	6	7	8	9	10
X coord	20	18	0	35	2	11	33	2	4	12
Y coord	8	13	5	7	11	15	22	7	10	0
Dice requested	5	7	16	4	7	15	8	10	1	12
Current dice	15	6	10	1	17	9	9	3	10	5

How should the dice be redistributed to minimize total travel cost?

Problem 4 – Shortest path modeling

A company sells six types of boxes, ranging in volume from 17 to 35 cubic feet. The demand and size (volume) of each box are given in the table below.

Box	1	2	3	4	5	6
Size	35	29	28	25	19	17
Demand	40	35	55	70	15	40

The variable cost per unit of producing each box is equal to its size divided by 10. In addition, if any positive number of a particular box is produced, a fixed cost of $10 is incurred. For example, the variable cost to produce one type 1 box is \$35 / 10 = 3.5, and so the total cost to produce 40 type 1 boxes would be $10 for the fixed cost, and 40*3.5=140 for variable costs, for a total cost of \$150. If the company desires, demand for a box may be satisfied by a box of larger size.

Formulate the problem of finding the amount of each box to produce in order to minimize the total cost to meet the customer demands as a shortest path problem. Solve the problem in Julia and report your solution.

ISYE524 Homework 3

Submission requirements

Upload a single PDF or HTML file of your IJulia notebook for this entire assigment. Clearly denote which question each section of your file corresponds to.

Problem 1 – Max Flow Modeling

A Dungeon Master (DM) is trying to plan for the next three campaigns she is running. She runs campaigns for four different groups, and she is hoping to finish the groups’ campaigns in the next six months.

Group 1’s campaign must be completed no later than 4 months from now and will require 20 total hours of play-time
Group 2’s campaign must be completed no later than 5 months from now and will require 18 total hours of play-time
Group 3’s campaign must be completed no later than 6 months from now and will require 13 total hours of play-time
Group 4’s campaign must be completed no later than 3 months from now and will require 14 total hours of play-time

Each month, 12 hours are available for playing games. During a given month, no more than 8 hours can be spent on the same campaign.

Formulate a maximum flow problem whose solution will determine whether or not all four campaigns can be completed on time. Your answer should clearly draw the network, the source node, the sink node, and capacity on each arc in the network. Upload a picture of the network with your solution.

Problem 2 – The Duality of Plushies

Assemble-an-Animal is currently producing four plushies: pandas, panthers, pangolins, and penguins.

A pangolin for reference: pangolins

The profit contribution, labor hours, and raw material usage (in square feet) per plushie for each type of animal are given below:

| Plushie| Profit ( $) | L a b o r (H r .) | R a w M a t e r i a l (f t$ ^2$)| |:—|:—|:—|:—| |Panda| 70 | 2 | 5| |Panther |110 |3 | 5| |Pangolin | 300 | 3 | 10| |Penguin | 250 | 5 | 15|

A maximum of 10,000 labor hours and 35,000 square feet of raw material are available annually. Each panda plushie spends an average of 0.25 year in storage; panther plushies an average of 1 year; pangolin plushies, an average of 2 years; penguin plushies, an average of 3.5 years. The warehouse can handle an average inventory level of 5,000 total plushies. Determine how much of each type of plushie should be produced annually to maximize Assemble-an-Animal’s profit.

A linear program model for this problem is:

$\begin{aligned} max & z = & 70 x_{1} & + & 110 x_{2} & + & 300 x_{3} & + & 250 x_{4} \\ s.t. & 2 x_{1} & + & 3 x_{2} & + & 3 x_{3} & + & 5 x_{4} & \leq 10000 \\ 5 x_{1} & + & 5 x_{2} & + & 10 x_{3} & + & 15 x_{4} & \leq 35000 \\ 0.25 x_{1} & + & x_{2} & + & 2 x_{3} & + & 3.5 x_{4} & \leq 5000 \\ x_{1} \geq 0, & x_{2} \geq 0, & x_{3} \geq 0, & x_{4} \geq 0 \end{aligned}$

where $x_{j}$ is the number of plushies of type $j$ to produce each year.

In the sensitivity analysis questions below, answer each question independently (e.g., when answering part (c), consider only the changes suggested in part (c), not those in addition to the ones considered in part (b)).

(a) Solve this model in Julia/JuMP and give the optimal primal and dual solutions, and the optimal objective function value.

(b) What is the maximum amount Assemble-an-Animal should be willing to pay for an additional hour of labor?

(c) The marketing department is considering running an advertising campaign that would increase the profit per panther plushie by $10 and panda plushie by \$15. Provide an estimate of the new optimal profit ( $z_{N E W}^{*}$ ) after this change and indicate if your estimate is a lower or upper bound on the new optimal profit. Your answer should be of the form $z_{N E W}^{*} \geq \underline{}$ or $z_{N E W}^{*} \leq \underline{}$ , where you fill in a number in the blank.

(d) Assemble-an-Animal is considering a facility redesign that would decrease the labor availability by 1000 hours, but increase the raw material availability by 4000 square feet. Provide an estimate of the new optimal profit ( $z_{N E W}^{*}$ ) after this change and indicate if your estimate is a lower or upper bound on the new optimal profit. Your answer should be of the form $z_{N E W}^{*} \geq \underline{}$ or $z_{N E W}^{*} \leq \underline{}$ , where you fill in a number in the blank.

Problem 3 – Duality and complementarity

Consider the following linear program:

min z = 2 x 1 + x 3 s.t. x 1 + x 2 - x 3 x 1 - 2 x 2 + 4 x 3 x 1, x 2, x 3 \geq 5 \geq 8 \geq 0

(1) Give the dual of this linear program.

(2) Find a complementary dual solution to the primal solution: $\hat{x} := ({\hat{x}}_{1}, {\hat{x}}_{2}, {\hat{x}}_{3}) = (\frac{28}{5}, 0, \frac{3}{5})$

(3) Is your dual solution feasible? What can you conclude about $\hat{x}$ ?

(4) Draw the feasible region to the dual you derived in (1). Find the optimal dual solution by the graphical method.

(5) Use complementary slackness and your dual solution from (4) to fimd the optimal primal solution.

ISYE524 Homework 4

Problem 1 — Tradeoffs and Regularization

A hobbyist pilot is planning her next flight. She is concerned about minimizing fuel usage so she can fly as long as possible. The flight plan includes numerous altitude changes. Each increase or decrease of 1 foot of altitude consumes 0.05 gallons of fuel. There are 100 discrete points where the pilot will need to change altitude. The desired altitudes are shown in the graph produced by the code snippet below.

Abrupt changes in altitude are risky and could potentially cause a loss of control of the aircraft, potentially inducing a stall or even resulting in structural damage. The pilot would like to find an alternative sequence of altitudes that gives her a tradeoff between matching the desired altitudes in the graph below and smoother transitions between successive altitudes. Denote the aircraft’s altitude at each discrete time by $u_{1}, u_{2}, . . ., u_{100}$ . We can characterize smoothness by using the sum of the squared differences between each successive altitude:

R (u) = (u 2 - u 1) 2 + (u 3 - u 2) 2 + \dots + (u 100 - u 99) 2

Of course, the smaller we make $R (u)$ the smoother the transitions will be. Find a set of optimal sequences of altitudes that explores the tradeoff between matching the desired seuqence given in the graph below and keeping the transitions smooth. Include a plot comparing the desired altitudes to at least 4 different smoothed versions. Use regularization weights of 0.1, 1, 10, and at least one other weight of your choice. Also plot your solutions on a Pareto curve. Either graph a curve or describe in a few words what you think the Pareto curve would look like if you filled in all the points.

Use the code provided below to generate data for your model.

using Random
# set a seed so we get the same output every time
seed = 787439
Random.seed!(seed)
# initialize the vector of altitudes
val = 0; u = zeros(100); u[1] = val
# set a density that determines how often the speed changes
# low density corresponds to infrequent speed changes
dens = 0.3
# build speed vector for all times between now and time 99
for i in 2:99
    # if a uniform(0,1) variable is < density
    if rand() < dens
        # increase the altitude
        val = val + 1
        u[i] = val
        # if a uniform(0,1) variable is >= 1 - density
    elseif rand() >= 1.0-dens
        # decrease the altitude
        val = val - 1
        u[i] = val
    else# otherwise the altitude stays the same
        u[i] = val
    end
end
# the final altitude must be 0
u[100] = 0
T = length(u)
# plot the altitudes (your figure should match the one in the assignment!)
using PyPlot
figure(figsize=(12,4))
plot(u,"-");

Problem 2 — Plotting Polynomials

While out on a hike one day, you stumble upon a mysterious looking map with 20 “x” marks scattered all over. On the back of the map is a note:

“As you hunt for the buried treasure, you should use the markings on this map as your guide. The final location you visit will require you to enter a series of numerical codes to open the treasure chest. The codes are the optimal coefficients of a polynomial function of the form $y = a_{1} x^{3} + a_{2} x^{2} + a_{3} x + a_{4}$ . How do you know you’ve found the optimal function? It will be the one that most closely fits the data shown on this treasure map!”

What values of $a$ give the best match between your polynomial model and the given data?

You can use the following code snippet to initialize your model and view the given data points.

using Random

# set a seed so we get the same output every time
seed = 43539
Random.seed!(seed)

# create 200 random (x,y) pairs
x = [Random.rand(0:100) for i in 1:20]
y = [Random.rand(-120:120) for i in 1:20]

using PyPlot

plot(x,y,"x");

ISYE524 Homework 5

Problem 1 — Nonconvex Quadratics

Suppose you have the constraint:

$2 x^{2} + y^{2} + z^{2} + 3 x y - x z + 2 y z \leq 0$ (1)

(a) Write constraint (1) in the standard form $v^{T} Q v \leq 0$ where $Q$ is a symmetric matrix. What is $Q$ and what is $v$ ?

v = $(\begin{matrix} x \\ y \\ z \end{matrix})$ , Q = $(\begin{matrix} 2 & 1.5 & - 0.5 \\ 1.5 & 1 & 1 \\ - 0.5 & 1 & 1 \end{matrix})$

(b) This constraint is not convex (i.e., the set of points satisfying the constraint is not an ellipsoid). Explain why this is the case. Hint: You can perform an orthogonal decomposition of a symmetric matrix $Q$ in Julia like this:

using LinearAlgebra
Q = [2 1.5 -0.5;1.5 1 1; -0.5 1 1]
(L,U) = (eigvals(Q),eigvecs(Q)) # L is the vector of eigenvalues and U is orthogonal
U * Diagonal(L) * U' # this is equal to Q (as long as Q was symmetric to begin with)
(L,U)

([-0.7717848741953769, 1.671965737371683, 3.099819136823694], [0.4755037916822413 -0.396463343135491 0.7853107420923526; -0.701884978187095 0.3671776439352714 0.6103589560164115; 0.5303335002534842 0.8414258109566005 0.10367730303646348])

As seen above, the constraint is not positive semidefinite by orthogonal decomposition, as some eigenvalues are nonpositive.

$‖ A v ‖_{2}^{2} - ‖ B v ‖_{2}^{2} \leq 0$ (2)

Find matrices $A$ and $B$ that make this constraint equivalent to (1).

$‖ A v ‖_{2}^{2} - ‖ B v ‖_{2}^{2} \leq 0$

$‖ A v ‖_{2}^{2} = (2 x)^{2} + y^{2} + z^{2}$

$‖ B v ‖_{2}^{2} = (3 x y - x z + 2 y z)^{2}$

A = $(\begin{matrix} 4 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})$ B = $(\begin{matrix} 0 & - 6 & - 4 \\ - 6 & 0 & 6 \\ - 4 & 6 & 0 \end{matrix})$

(d) Explain how to find $(x, y, z)$ that satisfy the above constraint but make $2 x^{2} + y^{2} + z^{2}$ arbitrarily large.

To find (x,y,z) such that the above constraint is satisfied and $2 x^{2} + y^{2} + z^{2}$ is arbitrarily large,

$v^{T} Q v = 𝜆_{1} w_{1}^{2} + . . . + 𝜆_{n} w_{n}^{2}$

must be proven, where $w = U^{T} v$ (or $v = U w$ ) and v is the same v defined in (a).

To do so, let $w_{i} = 0$ if $𝜆_{i} >= 0$ and $w_{i} = t$ for some positive $t$ if $𝜆_{i} < 0$

Thus, it stands to reason that $t$ should be arbitrarily large, as w is a vector of either 0 or $t$ , and therefore, $v = U w$ is arbitrarily large therefore $2 x^{2} + y^{2} + z^{2}$ is arbitrarily large

Problem 2 — Geometric Programming

Fizzy Water, Inc. is designing a pipe that disinfects their water before it is packaged. The pipe is designed to heat the water to $T$ (degrees above ambient temperature). The pipe has a fixed length and circular cross section with radius $r$ . The pipe is wrapped in a layer of material with thickenss $w$ (much smaller than $r$ ) for insulation to minimize heat loss. The design variables for the pipe are $T, r,$ and $w$ .

Heat loss can be converted to energy cost and is roughly equal to $(α_{1} T r) / w$ for some constant $α_{1}$ . The cost of the pipe is approximately proportional to the total material used: $α_{2} r$ for a constant $α_{2}$ . The insulation cost, similarly,is porportional to the total insulation material used, or roughly $α_{3} r w$ for a constant $α_{3}$ . The total cost of constructing and using the pipe is the sum of these three costs.

Fizzy Water wants to maximize the total heat flow through the pipe, which is proportional to the velocity of the water through the pipe. This value can be approximated by $α_{4} T r^{2}$ for a constant $α_{4}$ . All $α$ constants and all variables $T, r, w$ are strictly positive.

The problem Fizzy Water wants you to help them solve is to maximize the total heat flow through the pipe, subject to their budget $C_{max}$ which is an upper bound on total cost. They also have the following constraints:

$T_{min} \leq T \leq T_{max}$
$r_{min} \leq r \leq r_{max}$
$w_{min} \leq w \leq w_{max}$
$w \leq 0.1 r$

(a) Express this problem as a geometric program, and convert it into a convex optimization problem.

Geometric form:

min T, r, w > 0 a - 1 4 * T - 1 * (r 2) - 1 s.t. a 1 T r / w C m a x + a 2 r / C m a x + a 3 r w / C m a x T m i n / T T / T m a x r m i n / r r / r m a x w m i n / w w / w m a x w / 0.1 r \leq 1 \leq 1 \leq 1 \leq 1 \leq 1 \leq 1 \leq 1 \leq 1

Convex form:

min x, y, z - x - 2 y s.t. l o g (e l o g (a 1 / C m a x) + x + y - z + l o g (e l o g (a 2 / C m a x) + y + l o g (e l o g (a 3 / C m a x) + y + z l o g (T m i n) l o g (r m i n) l o g (w m i n) z - y \leq 0 \leq - x \leq l o g (T m a x) \leq - y \leq l o g (r m a x) \leq - z \leq l o g (w m a x) \leq 1

(b) Consider a simple instance of this problem where $C_{max} = 100$ and all $α_{i}$ values equal 1. Assume for simplicity that every variable ( $T, r, w$ ) has a lower bound of 1 and no upper bound. Solve this problem using JuMP. Use the Ipopt solver (or any other solver that can solve convex optimization problems) and the “@NLconstraint(…)” command to specify any nonlinear constraints. What are the optimal $T, r$ , and $w$ ?

cmax = 100
a1 = 1
a2 = 1
a3 = 1
a4 = 1

### MODEL ###

using JuMP, Ipopt

m = Model(Ipopt.Optimizer)

@variable(m, x)
@variable(m, y)
@variable(m, z)

@objective(m, Min, -x - 2y)

@NLconstraint(m,log(exp(log(a1/cmax)+ x + y - z))+log(exp(log(a2/cmax) + y)) + log(exp(log(a3/cmax) + y + z)) <= 0)
@constraint(m, -x >= 1)
@constraint(m, -y >= 1)
@constraint(m, -z >= 1)
@constraint(m, z-y <= 1)

optimize!(m)

println()
T = exp(value(x))
r = exp(value(y))
w = exp(value(z))
println("Temperature: ", T)
println("Radius: ", r)
println("Thickness: ", w)
println("Maximum heat flow: ", T*r^2)

This is Ipopt version 3.14.13, running with linear solver MUMPS 5.6.0.

Number of nonzeros in equality constraint Jacobian...:        0
Number of nonzeros in inequality constraint Jacobian.:        8
Number of nonzeros in Lagrangian Hessian.............:        6

Total number of variables............................:        3
                     variables with only lower bounds:        0
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        0
Total number of equality constraints.................:        0
Total number of inequality constraints...............:        5
        inequality constraints with only lower bounds:        3
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        2

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0  0.0000000e+00 1.00e+00 6.92e-01  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1  3.2571425e+00 0.00e+00 4.82e-01  -1.0 4.34e+00    -  7.58e-01 1.00e+00h  1
   2  3.0846593e+00 0.00e+00 4.31e-02  -1.7 2.28e-01    -  9.19e-01 1.00e+00f  1
   3  3.0065655e+00 0.00e+00 2.22e-03  -2.5 1.13e-01    -  9.42e-01 1.00e+00f  1
   4  3.0003081e+00 0.00e+00 4.60e-04  -3.8 3.11e-01    -  8.42e-01 1.00e+00f  1
   5  3.0000037e+00 0.00e+00 1.15e-06  -5.7 7.17e-03    -  9.97e-01 1.00e+00f  1
   6  3.0000000e+00 0.00e+00 4.10e-09  -8.6 7.94e-03    -  9.96e-01 1.00e+00f  1
   7  3.0000000e+00 0.00e+00 5.62e-10  -9.0 3.07e-01    -  8.79e-01 1.00e+00h  1

Number of Iterations....: 7

                                   (scaled)                 (unscaled)
Objective...............:   2.9999999718181813e+00    2.9999999718181813e+00
Dual infeasibility......:   5.6204110977765058e-10    5.6204110977765058e-10
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   3.1301266299467510e-09    3.1301266299467510e-09
Overall NLP error.......:   3.1301266299467510e-09    3.1301266299467510e-09


Number of objective function evaluations             = 8
Number of objective gradient evaluations             = 8
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 8
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 8
Number of Lagrangian Hessian evaluations             = 7
Total seconds in IPOPT                               = 0.005

EXIT: Optimal Solution Found.

Temperature: 0.3678794445158009
Radius: 0.36787944468301886
Thickness: 0.14594295986505196
Maximum heat flow: 0.04978706977095408

ISYE524 Homework 6

Problem 1 — Vehicle Routing

A local bakeshop wants determine the minimum cost plan for picking up its daily supply of milk, butter, and eggs from the four farms that supply the bakeshop. The distance (in miles) between the bakeshop (B) and each farm, and also between each pair of farms, is given in the table below. The table also gives the volume of milk, butter, and eggs (total, in ft $^{3}$ ) to be collected from each farm each day. (The distance between locations is the same in both directions, so for each pair of locations the distance is only reported once.)

	B	F1	F2	F3	F4
B	–	5	12	7	15
F1	–	–	4	10	7
F2	–	–	–	14	20
F3	–	–	–	–	8
	F1	F2	F3	F4
Supply (ft $^{3}$ )	7	2	6	3

The bakeshop has one truck that can carry at most 10 ft $^{3}$ of supplies at a time. Because of the size limit, the truck will need to make multiple trips each day to collect the supplies from all the farms. Each trip may pick up supplies from one or more farms, provided the total collected in the trip does not exceed the truck limit.

Formulate an integer program to help the bakeshop assign farms to the trips so that the total number of trips required every day is minimized (Hint: model the problem as a set covering problem. The first step will be to list all possible routes a truck can take.)

Problem 2 — The Magical Baked Goods Machine

Suppose you are in charge of a magical baked goods machine that creates delicious baked goods of many varieties. Every day, the machine creates batches of 5 different baked goods. To produce a batch of a baked good, you must first clean the machine to remove the remnants of the previous batch of bakery treats (e.g., the workflow could be, “clean, make bread, clean, make donuts,…”). The durations of baking each of the 5 items (donuts, scones, cookies, bread, and coffee cake) are 40, 32, 50, 28, and 47 minutes respectively. The cleaning times depend on the item that was previously made in the machine. For example, a long cleaning period is required if bread is made after scones, since the scones leave a sticky residue from the dried fruit they contain that can ruin the bread. The times are given in minutes in the following table. Each pair $(i, j)$ is the cleaning time required if batch $j$ is baked after batch $i$ .

Baked good	Donut	Scone	Cookie	Bread	Coffee Cake
Donut	0	10	6	15	9
Scone	4	0	6	17	8
Cookie	10	11	0	20	14
Bread	7	15	6	0	2
Coffee Cake	5	8	7	7	0

We’d obviously like to spend as little time as possible baking and cleaning. What order should we produce the 5 bakery items in? How long do we spend baking and cleaning each day? The order is the same every day, so the cleaning time between the last batch of one week and the first of the following week needs to be accounted for in the total duration of cleaning.

Solve this problem as a TSP. You may use either MTZ reformulation or subtour elimination (or both, for fun!).

ISYE524 Homework 1 to 6 solutions

Download Details:

Description

ISYE524 Homework 1

Problem 1 – Getting Started with Julia/JuMP

Problem 2 – Honest Work

Problem 3 – OptiMine

Problem 4 – Standard Form

ISYE524 Homework 2

Submission requirements

Problem 1 – The Spice Must Flow

Problem 2 – Spice Refineries

Problem 3 – Dice Delivery

Problem 4 – Shortest path modeling

ISYE524 Homework 3

Submission requirements

Problem 1 – Max Flow Modeling

Problem 2 – The Duality of Plushies

Problem 3 – Duality and complementarity

ISYE524 Homework 4

Problem 2 — Plotting Polynomials

ISYE524 Homework 5

Problem 1 — Nonconvex Quadratics

Problem 2 — Geometric Programming

Problem 1 — Vehicle Routing

Problem 2 — The Magical Baked Goods Machine

ISYE524 Homework 1 to 6 solutions

Download Details:

Description

ISYE524 Homework 1

Problem 1 – Getting Started with Julia/JuMP

Problem 2 – Honest Work

Problem 3 – OptiMine

Problem 4 – Standard Form

ISYE524 Homework 2

Submission requirements

Problem 1 – The Spice Must Flow

Problem 2 – Spice Refineries

Problem 3 – Dice Delivery

Problem 4 – Shortest path modeling

ISYE524 Homework 3

Submission requirements

Problem 1 – Max Flow Modeling

Problem 2 – The Duality of Plushies

Problem 3 – Duality and complementarity

ISYE524 Homework 4

Problem 2 — Plotting Polynomials

ISYE524 Homework 5

Problem 1 — Nonconvex Quadratics

Problem 2 — Geometric Programming

Problem 1 — Vehicle Routing

Problem 2 — The Magical Baked Goods Machine

Related products

ISYE524 Homework 5 solution

ISYE524 Homework 1 solution

ISYE524 Homework 3 solution