View Problem Statement (PDF) - CMU-IBM Cyber

Chance-Constrained Problems with Stochastic Quadratic
Inequalities
Miguel A. Lejeune∗, F. Margot†.
1
Formulation
Let D be the set of demand points and M be the number of facilities to be opened. The random demand
originating from d is denoted by ξd . The maximum demand level stemming from d is given by Ud . The
parameter Ci is the capacity of facility i. The continuous variable yid gives the fraction of the demand of
P
point d served by facility i. The probabilistic total weighted distance is t =
td , with td denoting the
d∈D
probabilistic weighted distance to deliver to demand point d.
The facilities can be located anywhere. The Cartesian coordinates of facility i are represented by a
pair of continuous decision variables (ai , bi ), i = 1, 2, . . . , M, while the known coordinates of demand
point d are the constants (¯ad , b¯ d ), d ∈ D. The Manhattan distance hid between facility i and demand point
d is a non-negative continuous decision variable
hid = |ai − a¯ d | + |bi − b¯ d | , i = 1, . . . , M, d ∈ D .
(1)
This distance function can be linearized with the introduction of non-negative auxiliary variables sid and
s0id and using the constraints: (2)-(6):
sid ≥ ai − a¯ d , i ∈ I, d = 1, . . . , M
(2)
sid ≥ a¯ j − ai , i ∈ I, d = 1, . . . , M
0
sid ≥ bi − b¯ d , i ∈ I, d = 1, . . . , M
0
s ≥ b¯ d − bi , i ∈ I, d = 1, . . . , M
(3)
id
0
hid = sid + sid , i ∈ I, d = 1, . . . , M
(4)
(5)
(6)
The problem is thus formulated as:
P
SFL1 : min
(7)
td
d∈D
(2) − (6)
subject to
P
M
P
!
ξd yid hid ≤ td , d ∈ D ≥ p
(8)
i=1
M
P
yid = 1
Pi=1
yid Ud ≤ Ci
d∈D
lia
lib
d∈D
(9)
i = 1, . . . , M
(10)
≤ ai ≤ uai
i = 1, . . . , M
(11)
ubi
i = 1, . . . , M
(12)
i = 1, . . . , M, d ∈ D
(13)
≤ bi ≤
yid ≥ 0
∗
George Washington University, Washington, DC, USA; [email protected]
Carnegie Mellon University, Pittsburgh, PA, USA; [email protected]. Supported by ONR grant N00014-1210032
†
1
The plane where the facilities can be opened is delineated which provides lower and upper bounds for
the coordinates of the facilities (see (11) and (12)). The constraints (9) stipulate that each demand point
is assigned to and served by exactly one facility. The constraints (10) ensure that the capacity of a facility
is never exceeded.
Using the Boolean approach of [14], the basic reformulation includes mixed-integer trilinear terms
including one binary variable and two continuous ones. For each stochastic variable ξd , a set of cut
points {cd1 , . . . , cdn j } are selected and a representation of the possible values of the random variables
using binary vectors βd associated with these cutpoints. We also define
odl+1 = cdl+1 − cdl d ∈ D, l = 1, . . . , nd − 1
.
od1 = cd1
d∈D
(14)
Each odl+1 measures the distance between two consecutive cut points cdl and cdl+1 .
Binarized values of all random variables are called recombinations and are partitioned into p-sufficient
and p-insufficient recombinations, representing essentially infeasible and feasible scenarios. The set K˜ −
is the set of non-dominated p-insufficient points. For each ωk ∈ K˜ − and its corresponding binarized
¯ = max{1 ≤ l ≤ nd | βk = 1}, d ∈ D.
vector βk , we define `(d)
dl
We study several exact reformulation (see [14] for more details).
P
M2-2 : min
td
d∈D
(2) − (6)
!
yid hid ≤ td d ∈ D
subject to
M
P
ed
i=1
M
P
d∈D
(16)
yid Ud ≤ Ci
i = 1, . . . , M
(17)
≤ ai ≤ uai
i = 1, . . . , M
(18)
ubi
i = 1, . . . , M
(19)
i = 1, . . . , M, d ∈ D
(20)
d ∈ D, 2 ≤ l ≤ nd
(21)
d∈D
(22)
d ∈ D, 1 ≤ l ≤ nd
k ∈ K˜ −
(23)
(24)
d∈D
(25)
i=1
P
d∈D
lia
lib
yid = 1
≤ bi ≤
yid ≥ 0
γd,l−1 ≥ γdl
γd1 = 1
γdl ∈ {0, 1}
P
d∈D
(15)
γd`¯k (d)+1 ≥ 1,
ed ≥
nd
P
γdl odl ,
l=1
When formulation M2-2 is passed to Couenne, it breaks the trilinear term hid · yid · ed by creating a
new variable for vid = hid · yid and then a variable zid` = vid · ed . Another possibility is to introduce in
M2-2 a new variable vid = ed · yid and apply a McCormick reformulation on these equalities and then a
variable zid = vid · hid . This gives us formulation M2-2-MC1. A third possibility is to introduce in M2-2
a new variable vid = ed · hid and apply a McCormick reformulation on these equalities and then a variable
zid = vid · yid . This gives us formulation M2-2-MC2.
We customize the COIN-OR open source code Couenne [4, 9]. Branching candidates selected by
Couenne are always among variables appearing in a nonlinear object. The justification for this is that
2
all linear constraints of the problem are included in the linear relaxation used by Couenne, so branching
to make sure that all nonlinear expressions are satisfied is sufficient for correctness. But in specific
situations, branching on variables that are not involved in any nonlinear expression is far superior.
When studying the branching decisions made during the tests with the trunk version Trb [10] of
Couenne, we noticed that the code branches often on variables hid or yid . Due to bound propagation
techniques used by Couenne and the presence of equations (1), it should be much better to branch on
variables ai or bi instead of hid . Indeed, ai and bi are involved in equation (1) for all customers and
reducing the range of one of them will, in general, reduce the ranges of all variables hid for all d. On the
other hand, branching on variable hid for one particular d might reduce or not the range for variable ai or
bi and is likely to induce far less bound tightening. This option is called Branching for Facility Location
(BFL).
A second improvement is generated by the following simple observation. Let R be the ranges of all
variables hid at a node of the enumeration tree. Let G(R) be the bipartite graph whose vertices corresponds
to the facilities and demand points and containing an edge between facility i and demand point d if and
only if the range of variable hid excludes both 0 and 1, i.e. if and only if hid must take a fractional value
in any feasible solution. Then there exists an optimal solution with ranges S such that G(S ) is acyclic.
Thus, any node of the enumeration tree for which G(R) is not acyclic can be pruned.
Modifications to the code of Couenne to implement this option are non trivial. We coded this option
by modifying the strong branching candidate selection and the computations of violations for nonlinear
objects and call it Branching for Facility Location (BFL). Based on these two observations, we modified the code of Trb such that when Couenne wishes to include a variable hid in its strong branching
candidates, it includes either ai or bi instead (the one with largest range) and prune nodes according to
the second observation. This gives us a new code specifically designed to solve these facility location
instances named Trb-L.
References
[1] Averbakh I., Bereg S. 2005. Facility Location Problems with Uncertainty on the Plane. Discrete
Optimization 2 (1), 3–34.
[2] Baron O., Berman O., Krass D. 2008. Facility Location with Stochastic Demand and Constraints
on Waiting Time. Manufacturing & Service Operations Management 100 (3), 484–505.
[3] Baron O., Berman O., Krass D., Wang Q. 2007. The Equitable Location Problem on the Plane.
European Journal of Operational Research 90, 183–578.
[4] Belotti P., Lee J., Liberti L., Margot, F., W¨achter, A. 2009. Branching and Bound Tightening Techniques for Nonconvex MINLPs. Optimization Methods and Software 24, 597–634.
[5] Benkoczi R., Bhattacharya B.K., Das S., Sember J. 2009. Single Facility Collection Depots Location Problem in the Plane. Computational Geometry 42 (5), 403–418.
[6] Berman O., Krass D. 2002. Facility Location Problems with Stochastic Demands and Congestion.
In: Facility Location: Applications and Theory. Eds: Drezner Z., Hamacher H.W. Springer-Verlag,
New York, NY.
[7] Berman O., Krass D. 2011. On n-Facility Median Problem with Facilities Subject to Failure Facing
Uniform Demand. Discrete Applied Mathematics 159, 420–432.
3
[8] Carbone R. 1974 Public Facilities Location under Stochastic Demand. INFOR 12 (3), 261–270.
[9] COIN-OR.
Computational
http://www.coin-or.org/
Infrastructure
for
Operations
Research
Project.
[10] https://projects.coin-or.org/svn/Couenne/trunk, revision 1070.
[11] Farahani R.Z., Hekmatfar M. 2009. Facility Location: Concepts, Models, Algorithms and Case
Studies. Springer, Heidelberg, Germany.
[12] Laporte G., Louveaux F.V., van Hamme L. 1994. Exact Solution to a Location Problem with
Stochastic Demands. Transportation Science 28 (2), 95–103.
[13] Larson R.C., Sadiq G. 1983. Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel. Operations Research 31 (4), 652–669.
[14] Lejeune M., Margot F., “Solving Chance-Constrained Optimization Problems with Stochastic
Quadratic Inequalities” Tepper Working Paper 2014-E8 (2014)
4

Download Report