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

© Copyright 2024 ExpyDoc