Description
1 A warm-up for using Xpress
This exercise is an introduction to Xpress, the main modeling language that we will use in this class.
The best way to learn Xpress is to use it to model and solve optimization problems. We will solve
the following facility location problem using Xpress.
Suppose A = (x1, y1) and B = (x2, y2) are the coordinates of two new facilities you want to
locate. There are three existing facilities at C = (300, 1200), D = (0, 600), and E = (600, 0). You
want to minimize the sum of `1 distances between A and B, A and C, A and D, B and D, and B
and E. The two new facilities should be located within the rectangular region (0, 900) for the x-axis
and (0, 1500) for the y-axis.
1. Write down an optimization model for the above facility location problem using absolute-value
functions in the objective.
2. Write down a linear programming reformulation of the above problem.
3. We have implemented your LP model in Xpress (see hw1prob1Fac.mos). The code is quite selfexplanatory and I have added comments in the code to help you understand its key features.
Go over the code and make sure you understand how the variables are declared and how the
objective and constraints are modeled. Now run the code by clicking on the green button with
a right arrow on it. The optimal solution should be printed out in the “Output/Input” tab
on the right panel of the Xpress window. Write down the optimal solution in your homework
submission. Do the two facilities overlap each other?
4. Now suppose facility A needs to be located close to the facility C within a distance of 500,
and the facility B needs to be located close to the facility E within a distance of 700. First,
model these conditions by constraints involving absolute value functions. Write down these
constraints in your homework paper submission. Second, reformulate them as linear constraints. Also write down your reformulation in the paper submission. Third, modify the
hw1prob1Fac.mos code to implement the new linear constraints. Solve the new model and
write down the optimal solution. Do the two new facilities overlap? You need to submit all
your code on t-square.
2 Quadratic programming and piecewise linear approximation
Consider the following nonlinear optimization problem involving absolute value functions:
(P) min f(x) = (x1 − 1.5)2 + (x2 − 0.8)2
s.t. |x1| + |x2| ≤ 1. (1)
1
1. First, reformulate (P) by rewriting the constraints in (P) as linear constraints. This feasible
region is called the `1 unit ball, because it is defined by all the points with `1-distance being 1
from the origin. Such a program is called a quadratic program (QP) with linear constraints.
2. Suppose you are given 10 feasible points, denoted as x
i = (x
i
1
, xi
2
) for i = 1, …, 10. Form
a convex piecewise linear function ˆf(x) using these 10 points such that ˆf(x) ≤ f(x) for all
x ∈ R
2
, and ˆf(x
i
) = f(x
i
) for i = 1, . . . , 10, i.e. ˆf(x) is a supporting lower envelope of f(x).
3. Formulate a linear program of minimizing ˆf(x) over the `1 unit ball.
4. Generate 10 feasible points for (P), write down their numerical values. You can do this by a
computer or by hand. You need to make sure the 10 points are all feasible.
5. Implement the above linear program in question 3 with the 10 points you generate in question
4 using Xpress. You need to submit the mos file on t-square and write down the optimal
solution in your paper submission. NOTICE: Xpress assumes that all the mpvar variables
are constrained to be nonnegative! So there is no need to specify non-negativity on variables.
However, if you want to have a free variable, you need to specify it explicitly as “x(i) is free”.
6. Now, implement the quadratic program with linear constraints that you formulated in question
1 and solve it in Xpress. Use the code hw1prob2QP.mos as the template (notice the code calls
“mmquad” and uses “qexp”). Compare the optimal solution and objective values of the QP
and the LP approximation. Later in the course, you will implement an automatic cutting plane
algorithm that generates supporting linear cuts on-fly to approximate a nonlinear function.
3 Production planning by a computer manufacturer
This is a problem that Digital Equipment Corporation (DEC) had faced in 1988, which illustrates
the usefulness of mathematical modeling for making important strategic decisions. DEC was a
major US computer company in 1950s-1990s. It was acquired by Compaq in 1998, which was at
the time the largest merger in the computer industry. Compaq later merged with HP in 2002.
In the beginning of 1988, DEC introduced a new family of single CPU computer systems and
workstations: GP-1, GP-2, and GP-3, which are general purpose computer systems with different
memory, disk storage, and expansion capabilities, as well as WS-1 and WS-2, which are workstations.
In the following table, we list the models, the list prices, and the memory usage. For example, GP-1
uses four 256k memory boards, and sells at $60,000.
System Price #256K boards
GP-1 $60,000 4
GP-2 $40,000 2
GP-3 $30,000 2
WS-1 $30,000 2
WS-2 $15,000 1
The following difficulties were anticipated:
1. The in-house supplier of CPUs could provide at most 7,000 units, due to debugging problems.
2
2. The supply of 256K memory boards was limited to be no more than 8,000 units.
On the demand side, the marketing department established the following:
1. The maximum demand for the first quarter of 1989 would be 1,800 for GP-1 system, 300 for
GP-3 system, 3,800 for the whole GP family, and 3,200 for the whole WS family.
2. Included in these projects were 500 orders for GP-2 system, 500 orders for WS-1, and 400
orders for WS-2 that had already been received and had to be fulfilled in the first quarter of
1989.
DEC needed to make a production plan for the first quarter of 1989 to consider all the above
production limitations and demand projections and to maximize the revenue.
(a) In order to model the problem that DEC faced, we introduce variables x1, x2, x3, x4, x5 that
represent the number (in thousands) of GP-1, GP-2, GP-3, WS-1, and WS-2 systems, respectively, to be produced in the first quarter of 1989. Strictly speaking, the 1000xi should be an
integer to represent the number of units. But for now, we ignore the integrality constraint
on 1000xi
. Formulate the problem as a linear program. Fill in objective and constraints
according to the descriptions.
max (total revenue):
s.t. (CPU availability):
(256K availability):
(max demand for GP-1):
(max demand for GP-3):
(max demand for GP family):
(max demand for WS family):
(min demand for GP-2):
(min demand for WS-1):
(min demand for WS-2):
(any other constraints?):
(b) Create an XpressMP model to solve the above complete LP problem. Hand in a printout of
your .mos and .dat files as well as the solution output.
4 Convex functions
1. Prove the piecewise linear function f(x) = max{a
>
1 x+b1, . . . , a
>
mx+bm} for x ∈ R
n
is convex
using the Jensen’s inequality.
2. Prove the following functions are convex, using one of your favorite conditions (Jensen’s inequality, the first-order condition, or the second-order condition):
(a) f(x) = e
ax for x ∈ R and any a ∈ R. Plot it.
(b) f(x) = x
a
for x > 0 and a ≥ 1 or a ≤ 0. Is such a function convex or concave for
0 ≤ a ≤ 1? Plot f(x) for a ≥ 1, a ≤ 0, and 0 ≤ a ≤ 1, separately.
3
(c) f(x) = − log(x) on x > 0. Plot it.
(d) f(x) = x log(x) for x > 0. This function is called the negative entropy function. Plot it.
(e) f(x, y) = x
2/y over x ∈ R and y > 0. Plot it.
(f) f(x1, x2) = (|x1|
p + |x2|
p
)
1/p for (x1, x2) ∈ R
2 and p ≥ 1. This is called the `p norm. We
have seen examples for p = 1, p = 2.
4
