branch-and-cut algorithm

A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … 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