Youssouf Emine

The Branch-and-Bound Tree Closure

  • Marius Roland
  • Nagisa Sugishita
  • Alexandre Forel
  • Youssouf Emine
  • Ricardo Fukasawa
  • Thibaut Vidal
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    This paper investigates the a-posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree’s branching … Read more

    A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

  • Miguel F. Anjos
  • Youssouf Emine
  • Andrea Lodi
  • Zhao Sun
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Network Optimization Tags , , ,

    In this note, we consider several polynomial optimization formulations of the max- imum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior. … Read more