Computational Optimization
Assignment #2
Problem 1
a) Show that the number of nodes in a tree where we represent all possible combinations of m 0-1 binary variables is
2m+1 - 1
b) If a complete enumeration of all the nodes in the tree were required, by what factor would this enumeration increase with respect to the direct enumeration of all 0-1 combinations.
Problem 2
Given is the integer programming problem
max y1 + 1.2y2
s.t. y1 + y2 ≤ 1
0.8y1 + 1.1y2 ≤ 1
y1, y2 ∈ {0, 1}
a) Plot the contours of the objective and the feasible region for the case when the binary variables are relaxed as continuous variables y1, y2 ∈ [0, 1].
b) Determine from inspection the solution of the relaxed problem (i.e. finding the solution by inspecting each feasible solution in the plot).
c) Enumerate the four 0-1 combinations in your plot (for all possible values of y1, y2) to find the optimal solution.
d) Solve the above problem with the branch and bound method by enumerating the nodes in the tree and solving the LP subproblems with GAMS/Pyomo.
Problem 3
A company is considering to produce a chemical C which can be manufactured with either process II or process III, both of which use as raw material chemical B. B can be purchased from another company or else manufactured with process I which uses A as a raw material. Given the specifications below, formulate an MILP model and solve it with GAMS/Pyomo to determine:
a) Which process to build (II and III are exclusive)?
b) How to obtain chemical B?
c) How much should be produced of product C? The objective is to maximize profit.
Consider the two following cases:
1. Maximum demand of C is 10 tons/hr with a selling price of $1800/ton.
2. Maximum demand of C is 15 tons/hr; the selling price for the first 10 ton/hr is $1800/ton, and $1500/ton for the excess.
Data:
Investment and Operating Costs
Fixed ($/hr) Variable($/ton raw mat)
|
Process I
|
1000
|
250
|
|
Process II
|
1500
|
400
|
|
Process III
|
2000
|
550
|
Prices: A: $500/ton
B: $950/ton
Conversions:
Process I 90% of A to B
Process II 82% of B to C
Process III 95% of B to C
Maximum supply of A: 16 tons/hr
NOTE: You may want to scale your cost coefficients (e.g. divide them by 100). Please avoid using any nonlinear term in the model formulation, because the model should an MILP. Please make sure to add ‘option ptcr = 0’ in your GAMS code. Please submit your source code file as well.
Problem 4
[Note: This is a bonus problem and not required – those students may work on it to earn an extra credit of at most 2 points that will be used to offset any possible loss of points from other problems, which are worth 10 points in total.]
Given are the following two optimization problems:
min z1 = f (x)
s.t. g (x ) ≤ 0
P1: h (x) ≤ 0
x ∈ Rn
min z2 = f (x)
P2: s.t. g (x) + h(x) ≤ 0
x ∈ Rn
where g(x) and h(x) are continuous and differentiable functions.
a) Show that the optimal objective function values of the above problem obey the following inequality: (z ) ≥ (z )
b) Does the above inequality rely on the assumption that the functions g(x) and h(x) are convex?
Problem 5
Prove that y2 + y3 + 2y4 ≤ 6 is a valid Gomory cut for the following feasible region.
X = {y ∈ Z4+ 1 + 5y2 + 9y3 +12y4 ≤ 34} .
Problem 6
The nonlinear term, Z = x . y, where x, y ∈ {0,1} and Z ∈ ℝ . Please reformulate this mixed- integer nonlinear equation into a set of mixed-integer linear inequalities with exactly the same feasible region.
Problem 7
[Note: This is a bonus problem and not required – those students may work on it to earn an extra credit of at most 2 points that will be used to offset any possible loss of points from other problems, which are worth 10 points in total.]
Consider the following optimization problem:
min |x1| + 2|x2| − |x3|
st x + x − x ≤ 10
x1 − 3x2 + 2x3 = 12
− 50 ≤ x1 ≤ 20
(a) Please reformulate it into a mixed-integer linear program, and solve this MILP with GAMS/Pyomo.
(b) Please solve the original problem with absolute value terms with a deterministic global optimization solver BARON or Couenne, and compare the resulting optimal solution with the one from (a).