ISUD

ISUD: Integral simplex using decomposition for the set partitioning problem. Since the 1970s, several authors have studied the structure of the set partitioning polytope and proposed adaptations of the simplex algorithm that find an optimal solution via a sequence of basic integer solutions. E. Balas and M. W. Padberg [Oper. Res. 20, 1152–1161 (1972; Zbl 0254.90035)] proved the existence of such a sequence with nonincreasing costs, but degeneracy makes it difficult to find the terms of the sequence. This paper uses ideas from the improved primal simplex to deal efficiently with degeneracy and find subsequent terms in the sequence. When there is no entering variable that leads to a better integer solution, the algorithm referred to as the integral simplex using decomposition algorithm uses a subproblem to find a group of variables to enter into the basis in order to obtain such a solution. We improve the Balas and Padberg results by introducing a constructive method that finds this sequence by only using normal pivots on positive coefficients. We present results for large-scale problems (with up to 500,000 variables) for which optimal integer solutions are often obtained without any branching.


References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Desaulniers, Guy; Lessard, François; Saddoune, Mohammed; Soumis, François: Dynamic constraint aggregation for solving very large-scale airline crew pairing problems (2020)
  2. Zaghrouti, Abdelouahab; El Hallaoui, Issmail; Soumis, François: Improving set partitioning problem solutions by zooming around an improving direction (2020)
  3. Foutlane, Omar; El Hallaoui, Issmail; Hansen, Pierre: Integral simplex using double decomposition for set partitioning problems (2019)
  4. Zaghrouti, Abdelouahab; El Hallaoui, Issmail; Soumis, François: Improved integral simplex using decomposition for the set partitioning problem (2018)
  5. Bouarab, Hocine; Desaulniers, Guy; Desrosiers, Jacques; Gauthier, Jean Bertrand: Linear fractional approximations for master problems in column generation (2017)
  6. Rosat, Samuel; Elhallaoui, Issmail; Soumis, François; Chakour, Driss: Influence of the normalization constraint on the integral simplex using decomposition (2017)
  7. Rosat, Samuel; Elhallaoui, Issmail; Soumis, François; Lodi, Andrea: Integral simplex using decomposition with primal cutting planes (2017)
  8. Rosat, Samuel; Quesnel, Frédéric; Elhallaoui, Issmail; Soumis, François: Dynamic penalization of fractional directions in the integral simplex using decomposition: application to aircrew scheduling (2017)
  9. Kuschel, Torben; Bock, Stefan: The weighted uncapacitated planned maintenance problem: complexity and polyhedral properties (2016)
  10. Desrosiers, Jacques; Gauthier, Jean Bertrand; Lübbecke, Marco E.: Row-reduced column generation for degenerate master problems (2014)
  11. Rönnberg, Elina; Larsson, Torbjörn: All-integer column generation for set partitioning: basic principles and extensions (2014)
  12. Zaghrouti, Abdelouahab; Soumis, François; El Hallaoui, Issmail: Integral simplex using decomposition for the set partitioning problem (2014)