Effective Solution Approaches for Stochastic and Integer Problems

Effective solution approaches for solving stochastic and integer problems Michel Gendreau CIRRELT and MAGI cole Polytechnique de Montr al SESO 2015 International Thematic Week ENSTA and ENPC Paris, June 22-26, 2015

Outline Introduction 1. An exact method for stochastic, fixed cost, capacitated multi-commodity network design problems 2. A heuristic approach for stochastic, fixed cost, capacitated multi-commodity network design problems 3. Problems with integer 2nd stage 4. Conclusion and perspectives 5. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 2

Acknowledgements Walter Rei CIRRELT and ESG UQ M Section 3 is also coauthored with Teodor G. Crainic, Xiaorui Fu, and Stein W. Wallace SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 3

Introduction

Stochastic and integer problems Integer programming problems (pure or mixed) are among the most difficult optimization problems. Stochastic optimization problems are also extremely difficult to deal with. Problems that display both combinatorial and stochastic elements are thus among the most difficult! SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 5

Some important problems In many different fields: network design problems In logistics: stochastic vehicle routing and supply chain problems In energy management: stochastic unit commitment problems And many others! SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 6

Modelling does matter The intrinsic nature of a problem is important, but it is not the only thing! Deciding which modelling framework is used to state the problem is critical. For instance, if a problem can be formulated as a stochastic dynamic program with reasonable state and action spaces, it can be dealt with relatively easily. In this talk, we focus on problems which can be attacked within the framework of stochastic programming with recourse (normally, two-stage). SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 7

An exact method for stochastic, fixed cost, capacitated multi-commodity network design problems

The problem Network design problems are encountered in a wide variety of settings. Notation: Set of nodes N Set of arcs A = {(i, j), i N, j N} with Fixed cost fij Variable (unit) cost cij Capacity uij Set of commodities (O-D pairs) K : origin o(k), destination s(k), and volume of demand w(k) SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 9

Decision variables SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 10

The model SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 11

Stochastic variants of the CMND Possible uncertain parameters: Demand: Volume of demand w(k) Origin o(k) or destination s(k) Costs Arc failures We should also specify objective and constraints. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 12

The main variant We focus on the variant with stochastic demands: Arcs must be selected before knowing demands Commodity flows can be routed in an optimal fashion after demands have been observed. We could allow some demands to be only partially satisfied at some cost (which can be quite high). The objective is to minimize the expected total cost of the design: Fixed costs + variable costs + penalties SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 13

Stochastic demand SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 14

Formulation SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 15

Formulation (contd) SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 16

Formulation (contd) If we use continuous distributions for commodity demands, the problem will be very difficult to tackle. One way of dealing with this stochastic complexity is either to: Use directly a scenario-based description of uncertainty, i.e., define a finite set S of representative scenarios (this could be used, among other things, to account for correlations between demands). Create a set of scenarios through Monte Carlo sampling (possibly coupled with techniques for enlarging the scenario set, such as sample average approximation) SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 17

Final model SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 18

Important observations SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 19

Possible solution approaches Brute force: if the model is not too large (small enough network and not too many scenarios), one could just dump the complete model in a commercial MIP solver (not very elegant, but easy to implement, if it works ). Alternately, use the L-shape algorithm of Van Slyke and Wets (1969). Or resort to heuristics... SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 20

The L-Shape algorithm This algorithm can be seen as a direct adaptation of Benders decomposition to the problem at hand: The master problem corresponds to the first stage of the model with the yijdesign variables and cuts. Subproblems are defined for each scenario and correspond to the second stage CMCMCFP for a given y vector and a given scenario s. They generate feasibility and optimality cuts for the master problem. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 21

The L-Shape algorithm Initialize counters for the number of feasibility and optimality cuts, and the number of iterations. Solve the relaxed master problem Minimize (First-stage objective) + s.t. First-stage constraints, if any. Feasibility cuts Optimality cuts (which involve ) Given the current solution of the master problem (yv, v), solve the |S| scenario subproblems. As soon as an infeasible subproblem is encountered, create a feasibility cut, add it to the master problem and return to Step 2. Otherwise, go to Step 4 1. 2. 3. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 22

The L-Shape algorithm Recover the simplex multipliers corresponding to the optimal solutions of all the current scenario subproblems solved in Step 3. 4. Construct an optimality cut using these multipliers. If the RHS of this cut, wv v, the current solution is optimal. STOP. Otherwise, add the optimality cut to the master problem and return to Step 2. 5. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 23

Notes about the L-Shape algorithm In the L-Shape algorithm, the optimality cuts are used to construct iteratively a piecewise linear outer approximation of the recourse function (the expected cost associated with the flows given the current yv vector and expressed in terms of this vector). When the subproblems are flow problems, feasibility cuts are capacity cuts, which force the addition of arcs with enough capacity to carry demand for each scenario. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 24

Notes about the L-Shape algorithm As in other applications of Benders decomposition, a na ve implementation will not perform well. One should first reinforce the master problem with constraints forcing the installation of some minimum capacity in the network (for instance by looking at the composite scenario with minimum demand for each commodity). Standard acceleration procedures for Benders decomposition, such as the McDaniel-Devine (1977) procedure can definitely help. More recent approaches, such as the one involving the addition of Local Branching cuts proposed by Rei et al. (2009), can significantly speed up convergence. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 25

Some computational results A fairly sophisticated implementation (Rei et al., 2009) was applied to a generalization of our stochastic network design problem, the Stochastic Integrated Logistics Network Design Problem, which also involves binary variables for location, product assignment, and sourcing decisions. A benchmark of 72 instances with 20, 30, 40 scenarios was solved. Out of these 72 instances, 22 easy instances were solved to optimality (< 1% gap) in 23 s on average, while 20 harder ones took on average of 163 s on a 2.4 GHz AMD Opteron 64-bit processor. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 26

Some recent developments Recent work by Crainic et al. (2014) shows that one can improve significantly the performance of this type of method by keeping some of the scenario subproblems in the master problem. Obviously, choosing well the scenarios helps! SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 27

A heuristic approach for the fixed cost, capacitated multi-commodity network design problem

A basic fact While exact methods have made much progress in recent years, it is still difficult, if not impossible, to solve fairly large instances of hard combinatorial problems. The situation gets even worse when dealing with stochastic variants of these problems. In such cases, one must resort to heuristics. Here, we want to tackle the same problem as before through an effective heuristic approach. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 29

Original model SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 30

Slight model modification SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 31

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 32

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 33

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 34

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 35

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 36

Scenario decomposition SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 37

General solution approach SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 38

General solution approach SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 39

General solution approach SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 40

General solution approach SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 41

Computational results SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 42

Computational results SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 43

Computational results SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 44

Computational results SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 45

What about multi-stage problems ?!? In theory, one could envision extending the method presented here to multi-stage problems, since (standard) Progressive Hedging is an effective method for (continuous) multi-stage stochastic programs. However, it still remains to be done. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 46

Problems with integer 2nd stage

What about integer 2ndstage ?!? There are interesting problems that exhibit an integer 2nd stage (e.g., stochastic vehicle routing problems). Because of the integer 2nd stage, the whole logic underlying Benders decomposition/L-shape method breaks down. A possible answer is the so-called Integer L-shape method of Laporte and Louveaux, if one looks for an exact method. There are other options, but they are usually restricted to fairly small instances (see the work of R diger Schultz among others). SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 48

A stochastic VRP formulation SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 49

The Integer L-shaped method The key element of the Integer L-shape method is the replacement of the feasibility and optimality cuts of the original L-shape algorithm by suitable equivalents. In the Integer L-shape method, optimality cuts simply express the fact that we know the value of the recourse for the integer solutions that have been encountered. They are thus very weak. Local branching cuts can also be added to extend the range of optimality cuts. Usually, one needs to add lower bounding functionals derived from partial solutions to obtain good results on larger instances. SESO 2015 June 22-26, 2015 Effective solution approaches for stochastic and integer problems 50