Impossible to pass all-zero solution as initial feasible solution

[lapseofreason]

I'm trying to solve a family of IP instances where I know that the all zero solution is feasible. Since cbc 2.10.0 does not find a feasible solution to some of those instances, I would like to pass in the all-zero solution using mipstart. However, when I pass an empty file to mipstart it still does not yield a feasible solution.

So I am wondering whether a) it is possible to pass the all-zero solution as an initial feasible solution using mipstart or b) cbc will always check the all-zero solution (or all remaining variables zero in case mipstart is given).

Surprisingly, cbc 2.9.10 finds a feasible solution to all such instances that I have tested (an initial solution is found by feasibility pump). I'm not sure if this is related, otherwise I might open a separate issue for this.

[h-g-s]

Your case is interesting, since these trivial solutions (all zero or all one) exist for some MIPS like yours and are easy to check, I think that before starting the search CBC should check if one of these two trivial solutions is feasible.

[jjhforrest]

I have coded (but not yet completely tested) a hack for mipStart.

The idea was to extend mipStart so that variables which were not mentioned were set to one of several values e.g. lower bound or lower bound if they don't have a cost and if they have a cost then the most expensive option.

As a quick hack the first was if the input solution file ended .low and similarly for other options. If the name of the file started empty. then no actual file was read.  So setting all variables to zero might be -mipstart empty.low.

Not quite working as I expected/hoped but getting some interesting results.

John Forrest On 16/04/2019 13:35, Haroldo Gambini Santos wrote:

Your case is interesting, since these trivial solutions (all zero or all one) exist for some MIPS like yours and are easy to check, I think that before starting the search CBC should check if one of these two trivial solutions is feasible.

— 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/215#issuecomment-483640527, or mute the thread https://github.com/notifications/unsubscribe-auth/AGycHBC4GqftTyYDGeA6ws2BmPC2kJRjks5vhcN8gaJpZM4cwsxW.

[lapseofreason]

@jjhforrest Thanks a lot for the mipStart hack!

I've done some testing with commit fc070c9, here are the results: cbc-fc070c9-coldstart.log cbc-fc070c9-warmstart.log cbc-fc070c9-emptylow.log

Cold start finds no solution (while cbc-2.9.8 does, see below) and warm start exits with an error (the *.soln file is read without problems by cbc-2.9.8). The new option empty.low claims in the beginning that MIPStart provided solution with cost 1.79769e+308 (which seems like an unreasonably high value to me), but then in the end claims No feasible solution found.

For reference, I did the same computations with cbc-2.9.8, both for cold and warm start. In both cases it found a feasible solution (see attached log). cbc-2.9.8-coldstart.log cbc-2.9.8-warmstart.log

I'm not sure what it is going on, could there be some deeper bug in the preprocessing/heuristics of 2.10/trunk compared to 2.9?

[lapseofreason]

I discovered why trunk failed on warm start: It was because the warm start file was a symlink. Without it, it works but is unable to construct a feasible solution (unlike cbc-2.9): cbc-fc070c9-warmstart.log

I did one more test where I passed only a single variable to mipstart, again trunk cannot find a feasible solution while cbc-2.9.8 does: cbc-fc070c9-singlevar.log cbc-2.9.8-singlevar.log

[lapseofreason]

I was finally able to do some more testing and I am still having some issues with mipstart. I was testing with versions 2.9.8 and 2.10-master commit dabc1ab.

I'm seeing two possible issues:

1. cbc 2.10-master does not find a mipstart solution where cbc 2.9.8 is able to find one (same *.lp, *.soln).
2. cbc 2.9.8 mipstart solution is worse thane the provided *.soln file.

Here is the log excerpt for issue 1:

Welcome to the CBC MILP Solver 
Version: 2.9.8 
Build Date: Jan 31 2019 

command line - cbc -seconds 600 -import instance.lp -mipstart instance.soln -solve (default strategy 1)
...
opening mipstart file ./instance.soln.
MIPStart values read for 2163 variables.
...
Cbc0045I MIPStart provided solution with cost -6.96495e+09

Welcome to the CBC MILP Solver 
Version: Trunk (unstable) 
Build Date: Jun  9 2019 

command line - .\cbc.exe -seconds 600 -import .\instance.lp -mipstart .\instance.soln -solve (default strategy 1)
...
opening mipstart file .\.\instance.soln.
MIPStart values read for 2163 variables.
...
Cbc0045I Fixing only non-zero variables.
Cbc0045I MIPStart solution provided values for 37984 of 39448 integer variables, 99 variables are still fractional.
Cbc0038I Full problem 26580 rows 39448 columns, reduced to 32 rows 34 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.

Here is the log excerpt for issue 2:

Objective value for complete run with cbc 2.10-master:

Objective value:                7016640403.00000000

Objective value found by mipstart with cbc 2.9.8 (sign of the objective is different because of internal reformulation prior to cbc 2.10):

Cbc0045I MIPStart provided solution with cost -6.96495e+09