Michael Poss

Easy distributions for combinatorial optimization problems with probabilistic constraints

  • Bernard Fortz
  • Michael Poss
    • Categories Combinatorial Optimization, Stochastic Programming Tags , ,

    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 … Read more

    Transmission Expansion Planning with Re-design

  • Michael Poss
  • Claudia Sagastizábal
  • Luciano S. Moulin
    • Categories Applications - Science and Engineering, Combinatorial Optimization Tags , ,

    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 … Read more

    Stochastic binary problems with simple penalties for capacity constraints violations

  • Bernard Fortz
  • Martine Labbé
  • Michael Poss
  • F Louveaux
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , , ,

    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 … Read more

    An improved Benders decomposition applied to a multi-layer network design problem

  • Bernard Fortz
  • Michael Poss
    • Categories Branch and Cut Algorithms, Telecommunications Tags , ,

    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. CitationTechnical Reports of the ULB Computer Science Department, … Read more