Name
Abstract | ||
|---|---|---|
The integral simplex using decomposition (ISUD) algorithm [22] is a dynamic constraint reduction method that aims to solve the popular set partitioning problem (SPP). It is a special case of primal algorithms, i.e. algorithms that furnish an improving sequence of feasible solutions based on the resolution, at each iteration, of an augmentation problem that either determines an improving direction, or asserts that the current solution is optimal. To show how ISUD is related to primal algorithms, we introduce a new augmentation problem, MRA. We show that MRA canonically induces a decomposition of the augmentation problem and deepens the understanding of ISUD. We characterize cuts that adapt to this decomposition and relate them to primal cuts. These cuts yield a major improvement over ISUD, making the mean optimality gap drop from 33.92% to 0.21% on some aircrew scheduling problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-07959-2_3 | SEA |
Keywords | Field | DocType |
primal cuts,cutting planes,integer programming,constraint aggregation,decomposition,primal algorithms,set partitioning | Mathematical optimization,Scheduling (computing),Computer science,Constraint reduction,Set partitioning problem,Simplex,Integer programming,Special case | Conference |
Volume | ISSN | Citations |
8504 | 0302-9743 | 7 |
PageRank | References | Authors |
0.49 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Rosat | 1 | 16 | 2.72 |
| Issmail Elhallaoui | 2 | 133 | 7.89 |
| François Soumis | 3 | 821 | 97.64 |
| Andrea Lodi | 4 | 2198 | 152.51 |