mipstart: CBC can not use a feasible solution as a starting point

[dimitryerkin]

Hello,

I have CBC solver version 2.10 which is built from the source files:

Welcome to the CBC MILP Solver Version: 2.10 Build Date: Dec 30 2019

The solver is not capable of using an initial solution, despite this solution is a feasible one. Below you can find an example of how I run the solver. Corresponding files are zipped and attached to this message.

command line - cbc 4ae88e8889054d15a8f9962f63ac3b56-pulp.mps max mips 4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol threads 8 ratio 0.5 presolve on gomory on knapsack on probing on seconds 960 branch printingOptions all solution 4ae88e8889054d15a8f9962f63ac3b56-pulp.sol (default strategy 1) At line 2 NAME MODEL At line 3 ROWS At line 1219 COLUMNS At line 10508 RHS At line 11723 BOUNDS At line 13272 ENDATA Problem MODEL has 1214 rows, 1548 columns and 5904 elements Coin0008I MODEL read with 0 errors opening mipstart file ./4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol. MIPStart values read for 1548 variables. threads was changed from 0 to 8 ratioGap was changed from 0 to 0.5 Option for gomoryCuts changed from ifmove to on Option for knapsackCuts changed from ifmove to on seconds was changed from 1e+100 to 960 Continuous objective value is 539986 - 0.04 seconds Cgl0004I processed model has 1022 rows, 1476 columns (1476 integer (1188 of which binary)) and 5340 elements Cutoff increment increased from 1e-05 to 0.1999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 1476 of 1476 integer variables, 38 variables are still fractional. Cbc0038I Full problem 1022 rows 1476 columns, reduced to 224 rows 311 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. Cbc0038I Initial state - 49 integers unsatisfied sum - 14.3553

4ae88e8889054d15a8f9962f63ac3b56-pulp.zip

[h-g-s]

Tested in trunk, it is solved with pre-processing and no variables remain, so mipstart doesn't have additional work to do...

elcome to the CBC MILP Solver Version: Trunk (unstable) Build Date: Jan 5 2020 Revision Number: 2785

command line - cbc 4ae88e8889054d15a8f9962f63ac3b56-pulp.mps mips 4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol solve (default strategy 1) At line 2 NAME MODEL At line 3 ROWS At line 1219 COLUMNS At line 10508 RHS At line 11723 BOUNDS At line 13272 ENDATA Problem MODEL has 1214 rows, 1548 columns and 5904 elements Coin0008I MODEL read with 0 errors opening mipstart file ./4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol. MIPStart values read for 1548 variables. Continuous objective value is 0 - 0.01 seconds Cgl0004I processed model has 0 rows, 0 columns (0 integer (0 of which binary)) and 0 elements Cbc3007W No integer variables - nothing to do Cuts at root node changed objective from 0 to -1.79769e+308 Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value: 0.00000000 Enumerated nodes: 0 Total iterations: 0 Time (CPU seconds): 0.04 Time (Wallclock seconds): 0.04

Total time (CPU seconds): 0.07 (Wallclock seconds): 0.07

[dimitryerkin]

This is a maximization problem so

cbc 4ae88e8889054d15a8f9962f63ac3b56-pulp.mps max mips 4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol solve Welcome to the CBC MILP Solver Version: 2.10 Build Date: Dec 30 2019

command line - cbc 4ae88e8889054d15a8f9962f63ac3b56-pulp.mps max mips 4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol solve (default strategy 1) At line 2 NAME MODEL At line 3 ROWS At line 1219 COLUMNS At line 10508 RHS At line 11723 BOUNDS At line 13272 ENDATA Problem MODEL has 1214 rows, 1548 columns and 5904 elements Coin0008I MODEL read with 0 errors opening mipstart file ./4ae88e8889054d15a8f9962f63ac3b56-pulp_init.sol. MIPStart values read for 1548 variables. Continuous objective value is 539986 - 0.04 seconds Cgl0004I processed model has 1022 rows, 1476 columns (1476 integer (1188 of which binary)) and 5340 elements Cutoff increment increased from 1e-05 to 0.1999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 1476 of 1476 integer variables, 38 variables are still fractional. Cbc0038I Full problem 1022 rows 1476 columns, reduced to 224 rows 311 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. Cbc0038I Initial state - 49 integers unsatisfied sum - 14.3553

[reidswanson]

I seem to be running into this issue as well. Is there any additional information about the problem? Manually built CBC version 2.10.3 PuLP 2.2

[lapseofreason]

I think this might be related to #215.

I have recently done another test with Cbc-master-precise-linux-x86_64-gcc9 built on August 5 on a rather large instance that unfortunately I'm not able to share. I generated a feasible solution in a first run and then tried to pass the resulting soln file to -mipstart. However, cbc is not able to build a solution out of it:

opening mipstart file ././instance.soln.
MIPStart values read for 302084 variables.
Continuous objective value is 2.59811e+10 - 605.47 seconds
Cgl0002I 1349 variables fixed
Cgl0008I 6559 inequality constraints converted to equality constraints
Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions
Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10662 strengthened rows, 0 substitutions
Cgl0004I processed model has 82188 rows, 147343 columns (147343 integer (147339 of which binary)) and 1885007 elements
Coin3009W Conflict graph built in 2.586 seconds, density: 0.011%
Cgl0015I Clique Strengthening extended 6 cliques, 6 were dominated
After applying Clique Strengthening continuous objective value is 25786762227.06
Cutoff increment increased from 0.0001 to 0.9999
Cbc0045I Fixing only non-zero variables.
Cbc0045I MIPStart solution provided values for 141373 of 147343 integer variables, 646 variables are still fractional.
Cbc0038I Full problem 82188 rows 147343 columns, reduced to 10415 rows 8004 columns
Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0045I Warning: mipstart values could not be used to build a solution.

Let me know if I can do anything to help debug this issue, I'd be happy to.

[jjhforrest]

To narrow the problem down -

a) If you add -preprocess off does it work?

If not then ??? try fixing variables to known solution and check for mistakes.

If yes then bug in Cbc - but first try

b) -tune 99000000

If you do Cbc and then tune?? you will see that the 99 says do a very simple preprocess. If that works and problem size is not too bad then use that for now.

John Forrest

On 14/08/2020 09:03, lapseofreason wrote:

I think this might be related to #215 https://github.com/coin-or/Cbc/issues/215.

I have recently done another test with |Cbc-master-precise-linux-x86_64-gcc9| built on August 5 on a rather large instance that unfortunately I'm not able to share. I generated a feasible solution in a first run and then tried to pass the resulting |soln| file to |-mipstart|. However, cbc is not able to build a solution out of it:

|opening mipstart file ././instance.soln. MIPStart values read for 302084 variables. Continuous objective value is 2.59811e+10 - 605.47 seconds Cgl0002I 1349 variables fixed Cgl0008I 6559 inequality constraints converted to equality constraints Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10662 strengthened rows, 0 substitutions Cgl0004I processed model has 82188 rows, 147343 columns (147343 integer (147339 of which binary)) and 1885007 elements Coin3009W Conflict graph built in 2.586 seconds, density: 0.011% Cgl0015I Clique Strengthening extended 6 cliques, 6 were dominated After applying Clique Strengthening continuous objective value is 25786762227.06 Cutoff increment increased from 0.0001 to 0.9999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 141373 of 147343 integer variables, 646 variables are still fractional. Cbc0038I Full problem 82188 rows 147343 columns, reduced to 10415 rows 8004 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. |

Let me know if I can do anything to help debug this issue, I'd be happy to.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/282#issuecomment-673946594, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHGGATVVMABIGT3PCIDSATVVHANCNFSM4KETMROA.

[lapseofreason]

I'm pretty sure the solution file is valid, apart from the fact that it was created by cbc, I verified it as follows:

1. Update bounds for all variables in original LP file to fix them to values from solution file.
2. Solve the updated LP file with cbc. It finishes quickly with "Result - Optimal solution found", as it is able to remove all variable during presolve.

The run without preprocessing is still in progress, as the model is large it takes a while to run.

[jjhforrest]

Looking more closely at the run log, I am concerned that Clique strengthening might be the culprit. If it strengthens the model then the input solution might be infeasible.

If the model is a maximization problem, then that might be where the bug is. If it is a minimization problem then I am even more worried that Clique strengthening seems to have lowered the objective value.

John Forrest

14/08/2020 09:03, lapseofreason wrote:

I think this might be related to #215 https://github.com/coin-or/Cbc/issues/215.

I have recently done another test with |Cbc-master-precise-linux-x86_64-gcc9| built on August 5 on a rather large instance that unfortunately I'm not able to share. I generated a feasible solution in a first run and then tried to pass the resulting |soln| file to |-mipstart|. However, cbc is not able to build a solution out of it:

|opening mipstart file ././instance.soln. MIPStart values read for 302084 variables. Continuous objective value is 2.59811e+10 - 605.47 seconds Cgl0002I 1349 variables fixed Cgl0008I 6559 inequality constraints converted to equality constraints Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10662 strengthened rows, 0 substitutions Cgl0004I processed model has 82188 rows, 147343 columns (147343 integer (147339 of which binary)) and 1885007 elements Coin3009W Conflict graph built in 2.586 seconds, density: 0.011% Cgl0015I Clique Strengthening extended 6 cliques, 6 were dominated After applying Clique Strengthening continuous objective value is 25786762227.06 Cutoff increment increased from 0.0001 to 0.9999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 141373 of 147343 integer variables, 646 variables are still fractional. Cbc0038I Full problem 82188 rows 147343 columns, reduced to 10415 rows 8004 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. |

Let me know if I can do anything to help debug this issue, I'd be happy to.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/282#issuecomment-673946594, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHGGATVVMABIGT3PCIDSATVVHANCNFSM4KETMROA.

[h-g-s]

Hi,

Looking more closely at the run log, I am concerned that Clique strengthening might be the culprit. If it strengthens the model then the input solution might be infeasible.

Clique strenghtening itself should not render any feasible solution infeasible (unless it is a bug), but clique strengthing + the availability of a feasible solution + reduced cost fixing may remove some non-optimal solutions.

If the model is a maximization problem, then that might be where the bug is. If it is a minimization problem then I am even more worried that Clique strengthening seems to have lowered the objective value.

The second case seems like a bug, I'll take a look here.

John Forrest

14/08/2020 09:03, lapseofreason wrote:

I think this might be related to #215 https://github.com/coin-or/Cbc/issues/215.

I have recently done another test with |Cbc-master-precise-linux-x86_64-gcc9| built on August 5 on a rather large instance that unfortunately I'm not able to share. I generated a feasible solution in a first run and then tried to pass the resulting |soln| file to |-mipstart|. However, cbc is not able to build a solution out of it:

|opening mipstart file ././instance.soln. MIPStart values read for 302084 variables. Continuous objective value is 2.59811e+10 - 605.47 seconds Cgl0002I 1349 variables fixed Cgl0008I 6559 inequality constraints converted to equality constraints Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10662 strengthened rows, 0 substitutions Cgl0004I processed model has 82188 rows, 147343 columns (147343 integer (147339 of which binary)) and 1885007 elements Coin3009W Conflict graph built in 2.586 seconds, density: 0.011% Cgl0015I Clique Strengthening extended 6 cliques, 6 were dominated After applying Clique Strengthening continuous objective value is 25786762227.06 Cutoff increment increased from 0.0001 to 0.9999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 141373 of 147343 integer variables, 646 variables are still fractional. Cbc0038I Full problem 82188 rows 147343 columns, reduced to 10415 rows 8004 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. |

Let me know if I can do anything to help debug this issue, I'd be happy to.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/282#issuecomment-673946594, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHGGATVVMABIGT3PCIDSATVVHANCNFSM4KETMROA.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, orunsubscribe.[AB4VZOWGGYWBFXTQWIUDNFLSAVN6ZA5CNFSM4KETMROKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXH JKTDN5WW2ZLOORPWSZGOFAXKINQ.gif]

[lapseofreason]

It is a maximization problem.

Unfortunately, the run without preprocessing is still running (time limit was 1h, but I guess it is stuck somewhere before the main search).

In the meantime I tried a smaller instance of the same problem, and I ran into something else: The mipstart was able to construct a solution, but for some reason did not use it (i.e. the returned solution is worse than the mipstart solution (as can be seen in the log below, even though the sign reported by reduced search is off):

opening mipstart file ./instance.soln.
MIPStart values read for 130437 variables.
...
Cgl0004I processed model has 12433 rows, 14893 columns (14893 integer (14893 of which binary)) and 133128 elements
Coin3009W Conflict graph built in 0.073 seconds, density: 0.047%
Cgl0015I Clique Strengthening extended 1 cliques, 1 were dominated
After applying Clique Strengthening continuous objective value is 5525750073.81
Cutoff increment increased from 0.0001 to 0.9999
Cbc0045I MIPStart provided solution with cost 5.38774e+09
Cbc0012I Integer solution of 5.3877405e+09 found by Reduced search after 0 iterations and 0 nodes (77.77 seconds)
Cbc0038I Full problem 12433 rows 14893 columns, reduced to 3047 rows 1400 columns
Cbc0012I Integer solution of -5.3908997e+09 found by RINS after 0 iterations and 0 nodes (90.25 seconds)
...
Cbc0020I Exiting on maximum time
Cbc0005I Partial search - best objective -5.3908997e+09 (best possible -5.4361882e+09), took 104447 iterations and 4 nodes (301.26 seconds)
...

Result - Stopped on time limit

Objective value:                5390899709.00000000
Upper bound:                    5436188241.086
...

Do you think this could be related or is this a different issue?

Let me know if I can do any other runs with something else turned off/on (Clique strengthening?).

[h-g-s]

Could you provide the larger instance ? In the MPS available the pre-processing removes all rows and columns so there is nothing to do.

[h-g-s]

It is a maximization problem.

Unfortunately, the run without preprocessing is still running (time limit was 1h, but I guess it is stuck somewhere before the main search).

In the meantime I tried a smaller instance of the same problem, and I ran into something else: The mipstart was able to construct a solution, but for some reason did not use it (i.e. the returned solution is worse than the mipstart solution (as can be seen in the log below, even though the sign reported by reduced search is off):

That happens because the reported cost is the cost for the pre-processed problem, which is different from the original problem. It does not means that the solution is wrongly evaluated. With some effort the cost for the original problem could be reported.

opening mipstart file ./instance.soln.
MIPStart values read for 130437 variables.
...
Cgl0004I processed model has 12433 rows, 14893 columns (14893 integer (14893 of which binary)) and 133128 elements
Coin3009W Conflict graph built in 0.073 seconds, density: 0.047%
Cgl0015I Clique Strengthening extended 1 cliques, 1 were dominated
After applying Clique Strengthening continuous objective value is 5525750073.81
Cutoff increment increased from 0.0001 to 0.9999
Cbc0045I MIPStart provided solution with cost 5.38774e+09
Cbc0012I Integer solution of 5.3877405e+09 found by Reduced search after 0 iterations and 0 nodes (77.77 seconds)
Cbc0038I Full problem 12433 rows 14893 columns, reduced to 3047 rows 1400 columns
Cbc0012I Integer solution of -5.3908997e+09 found by RINS after 0 iterations and 0 nodes (90.25 seconds)
...
Cbc0020I Exiting on maximum time
Cbc0005I Partial search - best objective -5.3908997e+09 (best possible -5.4361882e+09), took 104447 iterations and 4 nodes (301.26 seconds)
...

Result - Stopped on time limit

Objective value:                5390899709.00000000
Upper bound:                    5436188241.086
...

Do you think this could be related or is this a different issue?

Let me know if I can do any other runs with something else turned off/on (Clique strengthening?).

[lapseofreason]

Could you provide the larger instance ? In the MPS available the pre-processing removes all rows and columns so there is nothing to do.

I'm afraid that I can't share it as it would be quite some effort to anonymize it properly.

[lapseofreason]

That happens because the reported cost is the cost for the pre-processed problem, which is different from the original problem. It does not means that the solution is wrongly evaluated. With some effort the cost for the original problem could be reported.

Oh, this was my mistake, I misinterpreted the solutions. It is a maximisation problem, so 5.3908997e+09 is better than 5.3877405e+09. So this case is actually correct.

The core issue still remains though, that for the larger instance (and for the max version of the instance of @dimitryerkin) no feasible solution can be built by mipstart. I'm pretty sure that the provided solution is feasible, as when fixing the variables cbc immediately recognizes it as optimal.

Anything else I could try?

[reidswanson]

Sorry, I don't intend to hijack the thread, but wanted to clarify that I now believe I do not have the same problem. I believe I had a misunderstanding of how the warm restart could be used. In my case, I solve a problem optimally. Then add an additional set of constraints and try to resolve. It is obvious now why this won't work and is not what warm restarts are about.

[lapseofreason]

@jjhforrest Preprocessing seems indeed to be the issue.

However, without preprocessing the problem cannot be solved because it takes too much time. How much time exactly I do not know, I left it running for several days and it is still not doing branch-and-cut.

Here is the log without preprocessing:

Welcome to the CBC MILP Solver 
Version: devel 
Build Date: Aug  5 2020 

command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.int.lp.bz2 -stat=1 -preprocess off -mipstart ./instance.soln.low -solve (default strategy 1)
seconds was changed from 1e+100 to 3600
Option for printingOptions changed from normal to all
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements
...
Option for preprocess changed from sos to off
opening mipstart file ./instance.soln.low.
MIPStart values read for 172619 variables.
Continuous objective value is 2.59811e+10 - 603.20 seconds
Coin3009W Conflict graph built in 4.232 seconds, density: 0.012%
Cgl0015I Clique Strengthening extended 2666 cliques, 9502 were dominated
After applying Clique Strengthening continuous objective value is 25931039816.59
Cbc0045I Trying just fixing integer variables (and fixingish SOS).
Cbc0045I MIPStart provided solution with cost 2.07288e+10
Cbc0012I Integer solution of 2.0728829e+10 found by Reduced search after 0 iterations and 0 nodes (807.35 seconds)
Cbc0038I Full problem 122628 rows 172620 columns, reduced to 17214 rows 7756 columns
Terminated

Here is the log with -tune 99000000:

Welcome to the CBC MILP Solver 
Version: devel 
Build Date: Aug  5 2020 

command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.lp.bz2 -stat=1 -tune 99000000 -mipstart ./instance.soln.low -solve (default strategy 1)
seconds was changed from 1e+100 to 3600
Option for printingOptions changed from normal to all
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements
...
tunePreProcess was changed from 6 to 99000000
opening mipstart file ./instance.soln.low.
MIPStart values read for 172619 variables.
Continuous objective value is 2.59811e+10 - 855.15 seconds
Coin0506I Presolve 82989 (-46475) rows, 141541 (-31079) columns and 1787930 (-799047) elements
Coin3009W Conflict graph built in 2.526 seconds, density: 0.012%
Cgl0015I Clique Strengthening extended 302 cliques, 519 were dominated
After applying Clique Strengthening continuous objective value is 25927275337.01
Cbc0045I MIPStart provided solution with cost 2.06575e+10
Cbc0012I Integer solution of 2.0657548e+10 found by Reduced search after 0 iterations and 0 nodes (1094.15 seconds)
Cbc0038I Full problem 82772 rows 141541 columns, reduced to 17069 rows 7759 columns
Terminated

Here is the log with preprocessing:

Welcome to the CBC MILP Solver 
Version: devel 
Build Date: Aug  5 2020 

command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.int.lp.bz2 -stat=1 -mipstart ./instance.soln.low -solve (default strategy 1)
seconds was changed from 1e+100 to 3600
Option for printingOptions changed from normal to all
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements
...
opening mipstart file ./instance.soln.low.
MIPStart values read for 172619 variables.
Continuous objective value is 2.59811e+10 - 868.69 seconds
Cgl0002I 1349 variables fixed
Cgl0008I 6559 inequality constraints converted to equality constraints
Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions
Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions
Cgl0004I processed model has 82197 rows, 147343 columns (147343 integer (147339 of which binary)) and 1877944 elements
Coin3009W Conflict graph built in 2.481 seconds, density: 0.011%
Cgl0015I Clique Strengthening extended 10 cliques, 17 were dominated
After applying Clique Strengthening continuous objective value is 25817896851.71
Cutoff increment increased from 0.0001 to 0.9999
Cbc0045I Fixing only non-zero variables.
Cbc0045I MIPStart solution provided values for 147343 of 147343 integer variables, 2976 variables are still fractional.
Cbc0038I Full problem 82190 rows 147343 columns, reduced to 10355 rows 7999 columns
Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0045I Warning: mipstart values could not be used to build a solution.
Cbc0020I Exiting on maximum time
...

Btw, the problem contains no continuous variables, only binary ones.

How can I further narrow this down?

[jjhforrest]

Thinking it over, there may be no bug anywhere.

The point of preprocessing is to tighten and reduce the model in order to get an optimal solution. This can cut off non-optimal solutions. So if preprocessing finds that in an optimal solution x must be 1, then it will set it to 1 and if in input solution it was 0, then it may well find that to be infeasible.

The fact that the 99000000 run found a solution, but it is worse than the no preprocessing run gives support to that idea.

One could write a driver which would at least use that solution as a bound and maybe use that to drive a branching strategy.

John Forrest

On 17/08/2020 07:56, lapseofreason wrote:

@jjhforrest https://github.com/jjhforrest Preprocessing seems indeed to be the issue.

However, without preprocessing the problem cannot be solved because it takes too much time. How much time exactly I do not know, I left it running for several days and it is still not doing branch-and-cut.

Here is the log without preprocessing:

|Welcome to the CBC MILP Solver Version: devel Build Date: Aug 5 2020 command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.int.lp.bz2 -stat=1 -preprocess off -mipstart ./instance.soln.low -solve (default strategy 1) seconds was changed from 1e+100 to 3600 Option for printingOptions changed from normal to all CoinLpIO::readLp(): Maximization problem reformulated as minimization Coin0009I Switching back to maximization to get correct duals etc Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements ... Option for preprocess changed from sos to off opening mipstart file ./instance.soln.low. MIPStart values read for 172619 variables. Continuous objective value is 2.59811e+10 - 603.20 seconds Coin3009W Conflict graph built in 4.232 seconds, density: 0.012% Cgl0015I Clique Strengthening extended 2666 cliques, 9502 were dominated After applying Clique Strengthening continuous objective value is 25931039816.59 Cbc0045I Trying just fixing integer variables (and fixingish SOS). Cbc0045I MIPStart provided solution with cost 2.07288e+10 Cbc0012I Integer solution of 2.0728829e+10 found by Reduced search after 0 iterations and 0 nodes (807.35 seconds) Cbc0038I Full problem 122628 rows 172620 columns, reduced to 17214 rows 7756 columns Terminated |

Here is the log with -tune 99000000:

|Welcome to the CBC MILP Solver Version: devel Build Date: Aug 5 2020 command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.lp.bz2 -stat=1 -tune 99000000 -mipstart ./instance.soln.low -solve (default strategy 1) seconds was changed from 1e+100 to 3600 Option for printingOptions changed from normal to all CoinLpIO::readLp(): Maximization problem reformulated as minimization Coin0009I Switching back to maximization to get correct duals etc Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements ... tunePreProcess was changed from 6 to 99000000 opening mipstart file ./instance.soln.low. MIPStart values read for 172619 variables. Continuous objective value is 2.59811e+10 - 855.15 seconds Coin0506I Presolve 82989 (-46475) rows, 141541 (-31079) columns and 1787930 (-799047) elements Coin3009W Conflict graph built in 2.526 seconds, density: 0.012% Cgl0015I Clique Strengthening extended 302 cliques, 519 were dominated After applying Clique Strengthening continuous objective value is 25927275337.01 Cbc0045I MIPStart provided solution with cost 2.06575e+10 Cbc0012I Integer solution of 2.0657548e+10 found by Reduced search after 0 iterations and 0 nodes (1094.15 seconds) Cbc0038I Full problem 82772 rows 141541 columns, reduced to 17069 rows 7759 columns Terminated |

Here is the log with preprocessing:

|Welcome to the CBC MILP Solver Version: devel Build Date: Aug 5 2020 command line - ./Cbc-master-precise-linux-x86_64-gcc9/bin/cbc -seconds 3600 -printingOptions all -import ./instance.int.lp.bz2 -stat=1 -mipstart ./instance.soln.low -solve (default strategy 1) seconds was changed from 1e+100 to 3600 Option for printingOptions changed from normal to all CoinLpIO::readLp(): Maximization problem reformulated as minimization Coin0009I Switching back to maximization to get correct duals etc Presolve 83266 (-46198) rows, 145794 (-26826) columns and 1792481 (-794496) elements ... opening mipstart file ./instance.soln.low. MIPStart values read for 172619 variables. Continuous objective value is 2.59811e+10 - 868.69 seconds Cgl0002I 1349 variables fixed Cgl0008I 6559 inequality constraints converted to equality constraints Cgl0003I 0 fixed, 0 tightened bounds, 26262 strengthened rows, 0 substitutions Cgl0003I 2 fixed, 0 tightened bounds, 8062 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 2264 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 9391 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10202 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10692 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 10850 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13399 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 13909 strengthened rows, 0 substitutions Cgl0004I processed model has 82197 rows, 147343 columns (147343 integer (147339 of which binary)) and 1877944 elements Coin3009W Conflict graph built in 2.481 seconds, density: 0.011% Cgl0015I Clique Strengthening extended 10 cliques, 17 were dominated After applying Clique Strengthening continuous objective value is 25817896851.71 Cutoff increment increased from 0.0001 to 0.9999 Cbc0045I Fixing only non-zero variables. Cbc0045I MIPStart solution provided values for 147343 of 147343 integer variables, 2976 variables are still fractional. Cbc0038I Full problem 82190 rows 147343 columns, reduced to 10355 rows 7999 columns Cbc0038I Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) Cbc0045I Warning: mipstart values could not be used to build a solution. Cbc0020I Exiting on maximum time ... |

Btw, the problem contains no continuous variables, only binary ones.

How can I further narrow this down?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/282#issuecomment-674698184, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHEBKVTBQP6WXYZJMUTSBDIDJANCNFSM4KETMROA.

[lapseofreason]

I see, this does make sense, but certainly might throw off some people if they pass a feasible solution and then cbc returns no solution found.

I wonder why a solution previously found by cbc is cut off by preprocessing on a different run. Does the preprocessing have random components?

[gtg489p]

This seems to be a larger issue...

I'm getting "Cbc0045I Warning: mipstart values could not be used to build a solution."

I'm using PULP so I can easily point the problem to another solver: when I run with another solver engine (cplex, gurobi, etc) with the exact same problem and the exact same initial solution, it accepts the initial solution and runs with it.

At one point last year w an older version (2.9 maybe will need to confirm) warm start was working for me with CBC and now it does not.

[ahpmueller]

Are there any updates on this issue? I have the same problem. If hand over a feasible initial solution to CBC, it prices this solution with the right costs, but in the end it returns that no feasible solution is found. The corresponding log is:

Welcome to the CBC MILP Solver 
Version: 2.10 
Build Date: Jan  3 2021 

seconds was changed from 1e+100 to 10
Option for timeMode changed from cpu to elapsed
Option for printingOptions changed from normal to all
opening mipstart file \Users\a.mueller\AppData\Local\Temp\tmp41inprry.cbc.soln.
MIPStart values read for 653 variables.
Presolve 817 (-1) rows, 6416 (-1) columns and 18847 (-1) elements
Statistics for presolved model
Original problem has 6416 integers (401 of which binary)
Presolved problem has 6416 integers (401 of which binary)
==== 6015 zero objective 2 different
6015 variables have objective of 0
401 variables have objective of 1000
==== absolute objective values 2 different
6015 variables have objective of 0
401 variables have objective of 1000
==== for integers 6015 zero objective 2 different
6015 variables have objective of 0
401 variables have objective of 1000
==== for integers absolute objective values 2 different
6015 variables have objective of 0
401 variables have objective of 1000
===== end objective counts

Problem has 817 rows, 6416 columns (401 with objective) and 18847 elements
Column breakdown:
0 of type 0.0->inf, 6015 of type 0.0->up, 0 of type lo->inf, 
0 of type lo->up, 0 of type free, 0 of type fixed, 
0 of type -inf->0.0, 0 of type -inf->up, 401 of type 0.0->1.0 
Row breakdown:
0 of type E 0.0, 0 of type E 1.0, 0 of type E -1.0, 
15 of type E other, 0 of type G 0.0, 0 of type G 1.0, 
0 of type G other, 802 of type L 0.0, 0 of type L 1.0, 
0 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 
0 of type Free 
Continuous objective value is 245535 - 0.10 seconds
Cgl0004I processed model has 817 rows, 6416 columns (6416 integer (401 of which binary)) and 18847 elements
Cutoff increment increased from 1e-05 to 1000
Cbc0045I MIPStart provided solution with cost 246000
Cbc0031I 180 added rows had average density of 132.36111
Cbc0013I At root node, 180 cuts changed objective from 245535 to 245535 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 6 row cuts average 2.0 elements, 0 column cuts (140 active)  in 0.155 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 747 row cuts average 383.0 elements, 0 column cuts (0 active)  in 1.399 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.005 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 6 row cuts average 9.8 elements, 0 column cuts (0 active)  in 0.062 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.264 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 749 row cuts average 16.0 elements, 0 column cuts (0 active)  in 0.266 seconds - new frequency is -100
Cbc0014I Cut generator 7 (ZeroHalf) - 7 row cuts average 16.0 elements, 0 column cuts (0 active)  in 0.625 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 245535 (4.55 seconds)
Cbc0020I Exiting on maximum time
Cbc0005I Partial search - best objective 1e+50 (best possible 245535), took 1894 iterations and 98 nodes (9.65 seconds)
Cbc0032I Strong branching done 1542 times (3782 iterations), fathomed 0 nodes and fixed 8 variables
Cbc0035I Maximum depth 50, 0 variables fixed on reduced cost
Cuts at root node changed objective from 245535 to 245535
Probing was tried 10 times and created 6 cuts of which 140 were active after adding rounds of cuts (0.155 seconds)
Gomory was tried 10 times and created 747 cuts of which 0 were active after adding rounds of cuts (1.399 seconds)
Knapsack was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
MixedIntegerRounding2 was tried 10 times and created 6 cuts of which 0 were active after adding rounds of cuts (0.062 seconds)
FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.264 seconds)
TwoMirCuts was tried 10 times and created 749 cuts of which 0 were active after adding rounds of cuts (0.266 seconds)
ZeroHalf was tried 10 times and created 7 cuts of which 0 were active after adding rounds of cuts (0.625 seconds)

Result - Stopped on time limit

No feasible solution found
Lower bound:                    245535.000
Enumerated nodes:               98
Total iterations:               1894
Time (CPU seconds):             9.77
Time (Wallclock seconds):       9.77

Total time (CPU seconds):       10.20   (Wallclock seconds):       10.20

WARNING: Loading a SolverResults object with an 'aborted' status, but
    containing a solution

Is there any possibility to prevent cbc from discarding this initial solution? (The mps-file and the warmstart solution are attached to this comment)

model + warmstart_solution.zip

[jjhforrest]

The problem is that the mipStart is too trusting. So x641 is given a mipstart value of 100 - however its upper bound is 50!  But mipstart just sets the value to 100 before checking if can give  a valid solution.

Will modify code to say that nn values were outside bounds

On 11/04/2022 13:12, ahpmueller wrote:

Are there any updates on this issue? I have the same problem. If hand over a feasible initial solution to CBC, it prices this solution with the right costs, but in the end it returns that no feasible solution is found. The corresponding log is:

|Welcome to the CBC MILP Solver Version: 2.10 Build Date: Jan 3 2021 seconds was changed from 1e+100 to 10 Option for timeMode changed from cpu to elapsed Option for printingOptions changed from normal to all opening mipstart file \Users\a.mueller\AppData\Local\Temp\tmp41inprry.cbc.soln. MIPStart values read for 653 variables. Presolve 817 (-1) rows, 6416 (-1) columns and 18847 (-1) elements Statistics for presolved model Original problem has 6416 integers (401 of which binary) Presolved problem has 6416 integers (401 of which binary) ==== 6015 zero objective 2 different 6015 variables have objective of 0 401 variables have objective of 1000 ==== absolute objective values 2 different 6015 variables have objective of 0 401 variables have objective of 1000 ==== for integers 6015 zero objective 2 different 6015 variables have objective of 0 401 variables have objective of 1000 ==== for integers absolute objective values 2 different 6015 variables have objective of 0 401 variables have objective of 1000 ===== end objective counts Problem has 817 rows, 6416 columns (401 with objective) and 18847 elements Column breakdown: 0 of type 0.0->inf, 6015 of type 0.0->up, 0 of type lo->inf, 0 of type lo->up, 0 of type free, 0 of type fixed, 0 of type -inf->0.0, 0 of type -inf->up, 401 of type 0.0->1.0 Row breakdown: 0 of type E 0.0, 0 of type E 1.0, 0 of type E -1.0, 15 of type E other, 0 of type G 0.0, 0 of type G 1.0, 0 of type G other, 802 of type L 0.0, 0 of type L 1.0, 0 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 0 of type Free Continuous objective value is 245535 - 0.10 seconds Cgl0004I processed model has 817 rows, 6416 columns (6416 integer (401 of which binary)) and 18847 elements Cutoff increment increased from 1e-05 to 1000 Cbc0045I MIPStart provided solution with cost 246000 Cbc0031I 180 added rows had average density of 132.36111 Cbc0013I At root node, 180 cuts changed objective from 245535 to 245535 in 10 passes Cbc0014I Cut generator 0 (Probing)

• 6 row cuts average 2.0 elements, 0 column cuts (140 active) in 0.155 seconds - new frequency is -100 Cbc0014I Cut generator 1 (Gomory) - 747 row cuts average 383.0 elements, 0 column cuts (0 active) in 1.399 seconds - new frequency is -100 Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.005 seconds - new frequency is -100 Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.001 seconds - new frequency is -100 Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 6 row cuts average 9.8 elements, 0 column cuts (0 active) in 0.062 seconds - new frequency is -100 Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.264 seconds - new frequency is -100 Cbc0014I Cut generator 6 (TwoMirCuts) - 749 row cuts average 16.0 elements, 0 column cuts (0 active) in 0.266 seconds - new frequency is -100 Cbc0014I Cut generator 7 (ZeroHalf) - 7 row cuts average 16.0 elements, 0 column cuts (0 active) in 0.625 seconds - new frequency is -100 Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 245535 (4.55 seconds) Cbc0020I Exiting on maximum time Cbc0005I Partial search - best objective 1e+50 (best possible 245535), took 1894 iterations and 98 nodes (9.65 seconds) Cbc0032I Strong branching done 1542 times (3782 iterations), fathomed 0 nodes and fixed 8 variables Cbc0035I Maximum depth 50, 0 variables fixed on reduced cost Cuts at root node changed objective from 245535 to 245535 Probing was tried 10 times and created 6 cuts of which 140 were active after adding rounds of cuts (0.155 seconds) Gomory was tried 10 times and created 747 cuts of which 0 were active after adding rounds of cuts (1.399 seconds) Knapsack was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.005 seconds) Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds) MixedIntegerRounding2 was tried 10 times and created 6 cuts of which 0 were active after adding rounds of cuts (0.062 seconds) FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.264 seconds) TwoMirCuts was tried 10 times and created 749 cuts of which 0 were active after adding rounds of cuts (0.266 seconds) ZeroHalf was tried 10 times and created 7 cuts of which 0 were active after adding rounds of cuts (0.625 seconds) Result - Stopped on time limit No feasible solution found Lower bound: 245535.000 Enumerated nodes: 98 Total iterations: 1894 Time (CPU seconds): 9.77 Time (Wallclock seconds): 9.77 Total time (CPU seconds): 10.20 (Wallclock seconds): 10.20 WARNING: Loading a SolverResults object with an 'aborted' status, but containing a solution |

Is there any possibility to prevent cbc from discarding this initial solution? (The mps-file and the warmstart solution are attached to this comment)

model + warmstart_solution.zip https://github.com/coin-or/Cbc/files/8463813/model.%2B.warmstart_solution.zip

— Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/282#issuecomment-1094973853, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHEGNI7MBH6FSFKPKWDVEQJLBANCNFSM4KETMROA. You are receiving this because you were mentioned.Message ID: @.***>

[ahpmueller]

Thanks for the quick reply! That solved my problem and was of course my mistake, sorry.

If now the log is even adjusted, then this should not happen in the future. 👍