This PR adds cuts to the MIP solver. This includes the following: 1. Add constraints in the form C*x <= d to an LP that has already been solved to optimality (and has basis information). - The constraints must be violated at the current relaxation solution x^star. That is, C*x^star > d. - The constraint matrix, rhs, basis, and basis factorization, are all updated to include the additional constraints. - Dual simplex is started in phase 2 from a dual feasible solution. 2. Remove constraints from an LP that has already been solved to optimality. - The constraints must have slacks in the basis - The basis is refactored from scratch 3. Add cut pass loop after solving the root relaxation 4. Add a cut pool to store cuts and select cuts - We currently score cuts based on distance and orthogonality. 6. Add Mixed Integer Gomory Cuts - These are computed via a MIR cut on a row of the simplex tableau 7. Add Mixed Integer Rounding (MIR) Cuts - These are constructed by aggregating rows of the constraint matrix. 8. Add Strong Chvatal-Gomory Cuts - These are constructed from a row of the tableau matrix and from rows of the constraint matrix. 9. Fixes to Handling of Steepest Edge Norms in Dual Simplex - Ensure that all basic variables have a positive steepest edge norms 10. Reduced Costs Fixing at Root Node - These are applied after each cut pass and after strong branching, if a heuristic solution is available. 12. Fix issues in Crossover when solving the dual problem - We were not correctly populating slack variables when solving the dual. This issue appeared on graph20-80-1rand 14. Fix issue in Crossover when basis became rank-deficient in dual push 15. Fix issues across the code with handling and propagating concurrent halt. 16. New solver options: mip-cut-passes, mip-mixed-integer-gomory-cuts, mip-mir-cuts, mip-strong-chvatal-gomory-cuts, mip-knapsack-cuts, mip-cut-change-threshold, mip-cut-min-orthogonality. Closes #698, #205 Results from a GH200 A/B test with 64 threads and a 300 second time limit. Further runs needed with larger time limit. Further work is needed to get the full benefit of cuts. A: cuts PR with --mip-cut-passes=10 B: cuts PR with --mip-cut-passes=0 Geomean MIP GAP A / (B = baseline): 0.97 Geomean Time to Optimal A/B: 0.96 A optimal 45 B optimal 37 A problems with feasible solutions 225 B problems with feasible solutions 224 A wins drayage-100-23 1.14 8.61 gfd-schedulen180f7d50m30k18 87.85 300.0 neos-827175 12.28 25.86 neos-1171448 28.85 98.2 n5-3 180.62 300.0 neos859080 0.78 1.38 seymour1 38.78 300.0 neos-860300 71.98 90.91 neos-3083819-nubu 30.48 300.0 neos-933966 248.26 300.0 neos-957323 46.36 300.0 neos-960392 50.12 115.68 netdiversion 121.59 300.0 ns1208400 162.15 300.0 nw04 39.89 45.98 piperout-27 8.22 14.09 supportcase7 30.48 300.0 supportcase6 70.22 300.0 uccase12 26.95 41.87 A wins 19 A losses app1-1 2.3 0.74 cbs-cta 2.21 1.83 irp 17.59 12.94 istanbul-no-cutoff 18.26 13.56 mas76 300.0 20.98 neos-1122047 8.3 6.46 neos-1445765 1.86 1.52 neos-1582420 134.3 93.44 neos-3004026-krka 6.56 1.31 neos8 0.88 0.68 ns1952667 99.84 64.92 piperout-08 10.75 8.23 pk1 224.32 91.84 qap10 134.76 62.82 swath1 60.04 50.3 trento1 300.0 172.28 triptim1 246.65 130.92 A losses 17 Authors: - Chris Maes (https://github.com/chris-maes) Approvers: - Ramakrishnap (https://github.com/rgsl888prabhu) - Akif ÇÖRDÜK (https://github.com/akifcorduk) - Alice Boucher (https://github.com/aliceb-nv) URL: #814

Uh oh!

[FEA] MIP cuts #205

Description

Activity

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions