Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Infeasible with Reduce-and-split on #99

Open
christoph-cullmann opened this issue Mar 14, 2024 · 7 comments
Open

Infeasible with Reduce-and-split on #99

christoph-cullmann opened this issue Mar 14, 2024 · 7 comments

Comments

@christoph-cullmann
Copy link

This ILP will become infeasible if Reduce-and-split is turned on.

value_17869585116638.lp.txt
@christoph-cullmann
Copy link
Author

At least that happens with my driver, with standard cbc I get

❯ ../usr/bin/cbc test/value_17869585116638.lp -reduce=on -solve
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Mar 14 2024
command line - test/value_17869585116638.lp -reduce on -solve (default strategy 1)
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Continuous objective value is 1.78696e+13 - 0.01319 seconds
Cgl0003I 0 fixed, 148 tightened bounds, 13 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 78 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 10 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 557 rows, 418 columns (418 integer (133 of which binary)) and 1859 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 1.770%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
Cbc0012I Integer solution of 1.7869585e+13 found by DiveCoefficient after 1 iterations and 0 nodes (0.65 seconds)
Cbc0031I 1 added rows had average density of 3
Cbc0013I At root node, 1 cuts changed objective from 1.7869585e+13 to 1.7869585e+13 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 2287 row cuts average 3.9 elements, 0 column cuts (0 active)  in 0.506 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.009 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.011 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Reduce-and-split) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.013 seconds - new frequency is 1000
Cbc0014I Cut generator 4 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 5 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 6 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.010 seconds - new frequency is -100
Cbc0014I Cut generator 7 (FlowCover) - 198 row cuts average 1.5 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is 1
Cbc0001I Search completed - best objective 17869585116638, took 1 iterations and 0 nodes (0.65 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 1.78696e+13 to 1.78696e+13
Probing was tried 100 times and created 2287 cuts (0.505655 seconds)
Gomory was tried 100 times and created 0 cuts (0.008579 seconds)
Knapsack was tried 100 times and created 0 cuts (0.01133 seconds)
Reduce-and-split was tried 100 times and created 0 cuts (0.013238 seconds)
Clique was tried 100 times and created 0 cuts (0.00084 seconds)
OddWheel was tried 100 times and created 0 cuts (0.00128 seconds)
MixedIntegerRounding2 was tried 100 times and created 0 cuts (0.010035 seconds)
FlowCover was tried 100 times and created 198 cuts (0.003332 seconds)
TwoMirCuts was tried 1 times and created 0 cuts (9.6e-05 seconds)
ZeroHalf was tried 1 times and created 0 cuts (0.000604 seconds)

Result - Optimal solution found
Objective value:                1.78695851166e+13
Enumerated nodes:               0
Total iterations:               1
Time (CPU seconds):             0.656969
Time (Wallclock seconds):       0.668097
Total time (CPU seconds):       0.667192   (Wallclock seconds):       0.679074

@christoph-cullmann
Copy link
Author

-gmi=on and -reduce=on are needed for infeasible

❯ ../usr/bin/cbc test/value_17869585116638.lp -gmi=on -reduce=on -solve
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Mar 14 2024
command line - test/value_17869585116638.lp -gmi on -reduce on -solve (default strategy 1)
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Continuous objective value is 1.78696e+13 - 0.006487 seconds
Cgl0003I 0 fixed, 148 tightened bounds, 13 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 78 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 10 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 557 rows, 418 columns (418 integer (133 of which binary)) and 1859 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 1.770%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
Cbc0031I 10 added rows had average density of 44.4
Cbc0013I At root node, 52 cuts changed objective from 1.7869585e+13 to 1.7869202e+13 in 3 passes
Cbc0014I Cut generator 0 (Probing) - 54 row cuts average 3.7 elements, 0 column cuts (0 active)  in 0.017 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2 row cuts average 71.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Reduce-and-split) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1000
Cbc0014I Cut generator 4 (Gomory(2)) - 21 row cuts average 42.8 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is 1
Cbc0014I Cut generator 5 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (MixedIntegerRounding2) - 1 row cuts average 74.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (FlowCover) - 8 row cuts average 1.8 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0001I Search completed - best objective -1e+50, took 26 iterations and 0 nodes (0.08 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 1.78696e+13 to 1.78692e+13
Probing was tried 3 times and created 54 cuts (0.016971 seconds)
Gomory was tried 3 times and created 2 cuts (0.00036 seconds)
Knapsack was tried 3 times and created 0 cuts (0.000372 seconds)
Reduce-and-split was tried 3 times and created 0 cuts (0.000456 seconds)
Gomory(2) was tried 3 times and created 21 cuts (0.00052 seconds)
Clique was tried 3 times and created 0 cuts (3.5e-05 seconds)
OddWheel was tried 3 times and created 0 cuts (4.9e-05 seconds)
MixedIntegerRounding2 was tried 3 times and created 1 cuts (0.000361 seconds)
FlowCover was tried 3 times and created 8 cuts (0.000159 seconds)
TwoMirCuts was tried 1 times and created 0 cuts (0.000124 seconds)
ZeroHalf was tried 1 times and created 0 cuts (0.000766 seconds)

Result - Problem proven infeasible
No feasible solution found
Enumerated nodes:               0
Total iterations:               26
Time (CPU seconds):             0.077994
Time (Wallclock seconds):       0.0781639
Total time (CPU seconds):       0.080401   (Wallclock seconds):       0.0805731

@jjhforrest
Copy link
Contributor

Hopefully fixed. Reduce-and-split gets confused on odd row types. Clp thought a cut (from another cut generator was odd) and confused reduce-and-split. A lot of the cuts were "interesting" e.g. sum ... <= -1.0e10

@christoph-cullmann
Copy link
Author

Hmm, did rerun with current master, debug build, still got

../usr/bin/cbc test/value_17869585116638.lp -gmi=on -reduce=on -solve
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Mar 15 2024
command line - test/value_17869585116638.lp -gmi on -reduce on -solve (default strategy 1)
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Continuous objective value is 1.78696e+13 - 0.012475 seconds
Cgl0003I 0 fixed, 148 tightened bounds, 13 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 78 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 10 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 557 rows, 418 columns (418 integer (133 of which binary)) and 1859 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 1.770%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
### ERROR: CglRedSplit::generateCuts(): rstat[557]: 0
Cbc0031I 10 added rows had average density of 44.4
Cbc0013I At root node, 52 cuts changed objective from 1.7869585e+13 to 1.7869202e+13 in 3 passes
Cbc0014I Cut generator 0 (Probing) - 54 row cuts average 3.7 elements, 0 column cuts (0 active)  in 0.017 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2 row cuts average 71.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Reduce-and-split) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1000
Cbc0014I Cut generator 4 (Gomory(2)) - 21 row cuts average 42.8 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is 1
Cbc0014I Cut generator 5 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (MixedIntegerRounding2) - 1 row cuts average 74.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (FlowCover) - 8 row cuts average 1.8 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0001I Search completed - best objective -1e+50, took 26 iterations and 0 nodes (0.08 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 1.78696e+13 to 1.78692e+13
Probing was tried 3 times and created 54 cuts (0.016582 seconds)
Gomory was tried 3 times and created 2 cuts (0.000344 seconds)
Knapsack was tried 3 times and created 0 cuts (0.000368 seconds)
Reduce-and-split was tried 3 times and created 0 cuts (0.000428 seconds)
Gomory(2) was tried 3 times and created 21 cuts (0.000513 seconds)
Clique was tried 3 times and created 0 cuts (2.8e-05 seconds)
OddWheel was tried 3 times and created 0 cuts (4.1e-05 seconds)
MixedIntegerRounding2 was tried 3 times and created 1 cuts (0.000351 seconds)
FlowCover was tried 3 times and created 8 cuts (0.00015 seconds)
TwoMirCuts was tried 1 times and created 0 cuts (0.000119 seconds)
ZeroHalf was tried 1 times and created 0 cuts (0.000729 seconds)

Result - Problem proven infeasible
No feasible solution found
Enumerated nodes:               0
Total iterations:               26
Time (CPU seconds):             0.083056
Time (Wallclock seconds):       0.0831409
Total time (CPU seconds):       0.093484   (Wallclock seconds):       0.0936129

@jjhforrest
Copy link
Contributor

I am unable to reproduce the error.

Your log says -
Cgl0003I 0 fixed, 148 tightened bounds, 13 strengthened rows, 0 substitutions
Mine says -
Cgl0003I 0 fixed, 152 tightened bounds, 13 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 81 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 10 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 557 rows, 418 columns (418 integer (133 of which binary)) and 1859 elements

so there is a very subtle difference

I am using
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

What are you using and what compile options?

@christoph-cullmann
Copy link
Author

I use


❯ ../usr/bin/clang --version
clang version 17.0.3
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/ssd/cullmann/build/lpsolve.clpsolve/lpsolve.clpsolve/../usr/bin

with

-ffp-model=strict -O2 -fno-omit-frame-pointer

@christoph-cullmann
Copy link
Author

I found the issue, I didn't have the define COIN_FAST_CODE set, with that it works.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@christoph-cullmann @jjhforrest