Variable with Type=Integer ends with non-integral Value

[adante111]

I'm experiencing a situation where SONNET is returning from a solve and setting the Value to a non-integral value.

The variable was configured to be a binary integer (ie Type = VariableType.Integer; x.Lower = 0; x.Upper = 1;)

In the the debugger, the variable looks like this:

This seems a little counterintuitive to me but I am very far from an expert in linear programming let alone SONNET or the COIN-OR suice. I was just trying to understand what combination of this being a bug, edge case behaviour or a misconfiguration on my part this might be.

Some information about the model:

• The model is composed of purely binary variables.
• The binary variables represent classification choices so are all subject to constraints such as VAR_X_A + VAR_X_B + VAR_X_C <= 1.
• The constraint appear to be applying correctly (i.e. there is another variable that is part of the classification group that has a value of 1 - 0.215... = 0.78...).
• There are other constraints in play.
• In addition, I have been calling the solver through this code:

var osicbc = new COIN.OsiCbcSolverInterface();
var args = Sonnet.Utils.GetCbcSolverArgs(osicbc).ToList();
args.Add("-sec");
args.Add(timeout_seconds.ToString());
Sonnet.Utils.SetCbcSolverArgs(osicbc, args.ToArray());
Solver solver = new Solver(model, osicbc);
solver.Maximise();

(The reason for this was in order to get a timeout as it would not seem to terminate otherwise. This I achieved from mainly guesswork. When I used PULP I used to use timeLimit=X and gapRel=Y arguments in PULP_CBC_CMD to control for this but I'm
uncertain if there is a more idiometic manner to control timeouts in SONNET?)

• Unfortunately, the data itself is proprietary. I am trying to get a minimal reproducible example I can share, but this may not be trivial.

If anybody has any input it would be appreciated! Thank you for your consideration.

[jhmgoossens]

About non-integer solution:
Most likely, the solver hasn't found any integer solution yet--or the solution returned by Cbc to Sonnet is like the latest relaxation, not the last integer solution.
Can you check the output for message about solutions? (or even post the output here?)

About timeout:
Sonnet relies on OsiSolverInterface. Therefore, any parameter/setting that doesn't come via OSI (like timeout) has only limited support (see Osi Discussion 150). In the case of Cbc you found the way to pass tailored settings: via the args.

[adante111]

Thanks for clarifying - I clearly had some incorrect assumptions about how this all works!

If by output you mean the ToSolutionString, it does return something like this which confirms it is probably terminating prematurely:

Model 'Model_0'
Model status: not Optimal
Objective: 24910010779.4882
Variables:
...
[REDACTED]_01_BWC : Integer : [0, 1] = 0.721534756684656   ( 0 )
[REDACTED]_02_BWW : Integer : [0, 1] = 0   ( 0 )
[REDACTED]_03_BWTC : Integer : [0, 1] = 0   ( 0 )
[REDACTED]_04_BWTS : Integer : [0, 1] = 0.278465243315344   ( 0 )
[REDACTED]_Trash : Integer : [0, 1] = 0   ( 0 )
...

For console output, there didn't seem to be much other than:

Welcome to the CBC MILP Solver 
Version: 2.10.5 
Build Date: Sep  5 2020 

command line - Sonnet -sec 60 -ratiogap 0.001 -solve -quit (default strategy 1)
seconds was changed from 1e+100 to 60
ratioGap was changed from 0 to 0.001

As some follow on questions (apologies in advance if this is well documented somewhere):

1. Is it possible to obtain the last integer solution? And how close this is to a theoretical optimum, if any? From playing with PULP/CBC and reading http://www.decom.ufop.br/haroldo/files/cbcCommandLine.pdf I get the impression this might be doa-ble from CBC directly by reading output, but suspect not from sonnet due to the OSI standardisation? I suppose just checking my thinking here.
2. Is it in theory possible to apply a timeout to the solver, along with a warmstart to allow the search to effectively be stopped/resumed? I briefly played with this but didn't have much luck. I tried a loop like below but didn't see any progress, so suspect once again I am misusing/misunderstanding things.

WarmStart warmStart = null;
while (!cancel && !solver.IsProvenOptimal)
{
	count++;
	
	if (warmStart != null)
		solver.SetWarmStart(warmStart);
	
	solver.Maximise();			
				
	warmStart = solver.GetWarmStart();
				
	Console.WriteLine("Iterated " + model.Objective.Value);
}

Thank you again for your time and consideration and please feel free to disregard if these questions are too onerous.

[jhmgoossens]

Is it possible to obtain the last integer solution?
That is the normal behavior. The best known (if any) integer solution is returned by CBC to Sonnet.
Assuming the problem has a feasible solution, then that will eventually be found. If you put a timeout (or node limit, etc.) then you might be forcing the solver to return before any feasible (integer) solution was found.
I suspect that your 5-seconds limit is simply not enough. You can increase the limit or try to find the Cbc parameters (cuts, etc.) to solve more quickly..
(You can use var args = osiCbc.GetCbcSolverArgs().ToList(); for slightly shorter code)

I ran a few tests on miplib problems and using timeout, and found that this works as expected:

• Set the timeout high enough and the best solution known at that time is returned.
• Set the timeout too low (like 1 second) such that no feasible solution was found yet, and then the solution returned is not a feasible one (like you experience).
  You can ask the sonnet solver to check the returned solution by using solver.IsFeasible which checks all variables and constraints against their bounds, types etc. and returns true or false for the received solution. If you don't put limits for time, #nodes, etc., then calling IsFeasible is not necessary. But if you do impose limits, then check.

Is it in theory possible to apply a timeout to the solver, along with a warmstart to allow the search to effectively be stopped/resumed?
Probably. Please check with the Cbc folks how to halt/resume. Sonnet merely wraps the CbcModel (in your case). One simple observation is that the time limits count from the beginning of the solve in Cbc. So you'd have to at least increase the time limit in every iteration--it doesn't mean another 5 seconds.
You can use the cbcModel.getBestPossibleObjValue(); to get the dual bound.

[jhmgoossens]

BTW:
When using Cbc, you might also want to try not "sec"--which might stop without any solution, as you found out--, but

• ratio(Gap) : Stop when gap between best possible and best known is less than this fraction of larger of two
• secni(fs) : maximum seconds without improving the incumbent solution

In both cases, at least one MIP solution will be found before stopping, but which might be after a long time.
Using one of these two plus a larger absolute time limit of "sec" and using isFeasible lets you say like "no solution found in time".

[jhmgoossens]

Is it in theory possible to apply a timeout to the solver, along with a warm-start to allow the search to effectively be stopped/resumed?
If all you want is to halt/continue the solving, check out the CbcModel events—available in Sonnet as of b478a69. For an example of how to do this via Sonnet, see SonnetTest42 in BasicTests. Binaries on Appveyor.

[adante111]

Thank you very much for this!

If all you want is to halt/continue the solving

Yes, I think this is the case (my thinking is: prior to using Sonnet I was playing with PULP/cbc.exe to build some proof-of-concepts to solve some problems. So my hope is I can utilise Sonnet to solve the same solving, except wrapped up in a nicer UI (my app is C#/.NET) that allows to report on progress (e.g. user is told the solution status, and given an option to continue processing or stop here) etc.

I have been fumbling my way through it in the last week and building up some questions, but need to take the time to rubber duck debug this first so as not to waste others time!

I'll have a play with these latest builds though, thank you again