Michael Poss

I obtained a PhD in Operations Research from the Université Libre de Bruxelles in 2011, under the supervision of Bernard Fortz, Martine Labbé and François Louveaux. Currently, I am a postdoctoral researcher at the Mathematics Department / CMUC from the University of Coimbra. Contact information: Email:  mjposs at gmail dot com

• Stochastic and robust programming
• Transmission expansion planning
• Network design
• Benders decomposition

• Affine recourse for the robust network design problem: between static and dynamic routing. (with C. Raack) Accepted in Networks.   preprint | abstract
• Stochastic binary problems with simple penalties for capacity constraints violations. (with B. Fortz, M. Labbé, and F. Louveaux) Mathematical Programming A, in press   link | preprint | abstract

  Abstract:

  This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly NP-hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and arbitrary random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

• Benders decomposition for the hop-constrained survivable network design problem. (with Q. Botton, B. Fortz and L. Gouveia) INFORMS J. on Computing, in press  link | preprint | abstract

  Abstract:

  Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most $L$ edges between each pair in Q. Using the layered representation introduced by Gouveia, we present a formulation for the problem valid for any K,L>= 1. We use a Benders decomposition method to efficiently handle the big number of variables and constraints. We show that our Benders cuts contain the constraints used by Huygens et al to formulate the problem for L=2,3,4, as well as new inequalities when L>= 5. While some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

• Lot-sizing and scheduling in a glass container manufacture company. (with A. Agra, C. Avelino, A. Cerveira, A. Delgado) Int. J. of Mathematical Modelling and Numerical Optimisation, 2(3):253-272, 2011. link
• Easy distributions for combinatorial optimization problems with probabilistic constraints. (with B. Fortz) Oper. Res. Lett., 38:545-549, 2010. link | preprint | abstract

  Abstract:

  We show how we can linearize probabilistic linear constraints with binary variables when all coefficients are distributed according to either $\mathcal{N}(\mu_i,\lambda \mu_i)$, for some $\lambda >0$ and $\mu_i>0$, or $\Gamma(k_i,\theta)$ for some $\theta >0$ and $k_i>0$. The constraint can also be linearized when the coefficients are independent and identically distributed if they are, besides, either positive or strictly stable random variables.

• Transmission expansion planning with re-design. (with S. L. Moulin and C. Sagastizábal) Energy Systems, 1(2):113-139, 2010. link | preprint | abstract

  Abstract:

  Expanding an electrical transmission network requires heavy investments that need to be carefully planned, often at a regional or national level. We study relevant theoretical and practical aspects of transmission expansion planning, set as a bilinear programming problem with mixed 0-1 variables. We show that the problem is NP-hard and that, unlike the so-called Network Design Problem, a transmission network may become more efficient after cutting-off some of its circuits. For this reason, we introduce a new model that, rather than just adding capacity to the existing network, also allows for the network to be re-designed when it is expanded. We then turn into different reformulations of the problem, that replace the bilinear constraints by using a “big-M” approach. We show that computing the minimal values for the “big-M” coefficients involves finding the shortest and longest paths between two buses. We assess our theoretical results by making a thorough computational study on real electrical networks. The comparison of various models and reformulations shows that our new model, allowing for re-design, can lead to sensible cost reductions.

• An improved benders decomposition applied to a multi-layer network design problem. (with B. Fortz ) Oper. Res. Lett., 37:359-364, 2009. link | preprint | abstract

  Abstract:

  Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bilayer networks, comparing with Knippel’s previous results.

• Cost/benefit analysis of losses and reliability criteria for transmission planning (with L. Moulin and C. Sagastizábal, and P. F. M. Araujo) SEPOPE 2012. abstract
• Layered Formulation for the Robust Vehicle Routing Problem with Time Windows (with A. Agra, M. Christiansen, L. M. Hvattum, R. Figueiredo, and C. Requejo) ISCO 2012. preprint | abstract
• Transmission Expansion Planning With Re-Design: A Greedy Randomized Adaptive Search Procedure. (with R. Figueiredo and P. G. Henrique Silva) ICORES 2012. link | pdf | abstract

  Abstract:

  Transmission expansion planning with re-design has been recently proposed in the literature to improve on the classical transmission expansion planning by allowing to cut-off circuits while expanding the network. Although the reductions in the solution costs are significant, the resulting mixed-integer linear programming formulations are very difficult to solve exactly for large networks. In this work, we propose the first metaheuristic for the transmission expansion planing problem with re-design: a simple yet efficient GRASP metaheuristic. We show on realistic networks for which the optimal solutions are known that our method is able to provide in short amounts of time feasible solutions as cheap as the optimal ones. Moreover, we are able to compute a new feasible solution for benchmark instance Brazil Southeast that is cheaper than the best solution from the literature.

• Affine recourse for the robust network design problem: between static and dynamic routing. (with C. Raack) INOC 2011, Lecture Notes in Computer Science, 2011, Volume 6701/2011, 150-155.   link | abstract

  Abstract:

  Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. Following Ouorou and Vial, we apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing scheme to the well-studied static and dynamic routing schemes for robust network design. It is shown that affine routing can be seen as a generalization of the widely used static routing while still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.

• A branch-and-cut-and-price framework for convex MINLP applied to a stochastic network design problem. (with B. Fortz and M. Labbé) In European Workshop on Mixed Integer Nonlinear Programming, 2010. link | abstract

  Abstract:

  Many convex linearly constrained programs and mixed integer programs have a large number of variables, so that the variables should be generated dynamically throughout the solution algorithm. This yields to the well known ``branch-and-price algorithm'' and ``simplicial decomposition''. We present a novel ``branch-and-cut-and-price algorithm'' to extend this idea to certain classes of convex linearly constrained MINLP. Our algorithm incorporates the variables generation into the ``LP/NLP algorithm'' introduced by Quesada and Grossman. We detail our framework for the stochastic network design problem with simple recourse and present preliminary computational results.

• The robust vehicle routing problem with time windows (with A. Agra, M. Christiansen, R. Figueiredo, L. M. Hvattum, and C. Requejo)
• A comparison of routing sets for robust network design.   preprint | abstract

  Abstract:

  Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. The problem can be seen a two-stage robust program where the recourse function consists in choosing the routing for each demand vector. Allowing the routing to change arbitrarily as the demand varies yields a very difficult optimization problem so that different subsets of admissible routings have been discussed in the literature. In this paper, we compare theoretically the optimal capacity allocation costs for six of these routing sets: affine routing, volume routing and its two simplifications, the routing based on an arbitrary 2-cover of the uncertainty set, and the routing based on a cover delimited by a hyperplane. We show that the two routing sets based on covers of the uncertainty set yield the same optimal costs. We show then that the two simplified volume routings are special cases of affine routings. Finally, assuming that the uncertainty set is the one studied by Bertsimas and Sim (2004), we show that the optimal cost provided by volume routing is not less than the costs provided by the simplified volume routings.