[Cbc] Determining feasibility when a model times out
R. Kipp Martin
kmartin at chicagobooth.edu
Thu Jun 30 21:52:45 EDT 2011
Hi Ted and Troy:
Actually, I don't think any new code is needed if I correctly understand
your problem. The code already exists and is part of the Optimization
Services project. Troy, see the example,
https://projects.coin-or.org/CoinBazaar/browser/projects/ApplicationTemplates/trunk/osSolverDemo/OSSolverDemo.cpp
See the code starting in line 173. In particular, in line 181 we read in
the p0033 test problem. In line 188 we create an option object.
osoption = new OSOption();
In line 195 we set the max number of nodes to 1000.
osoption->setAnotherSolverOption("maxN","1000","cbc","","integer","");
In line 197 we set the time limit to .01 seconds
osoption->setAnotherSolverOption("sec",".01","cbc","","integer","");
In line 209 we create a generic Coin Solver
solver = new CoinSolver();
In line 210 we make it Cbc
solver->sSolverName ="cbc";
We set the instance and options in lines 215-216
solver->osinstance = osinstance;
solver->osoption = osoption;
Then we solve
solver->solve();
The string solver->osrl now has all of the result information. This
string can be used to create a result object which has an API. This
OSResult object API is designed, to use Ted's terminology, for
"post-solution queries." See how we use this string starting in line
574. In this particular case, because of the time limit of .01 seconds
we do not get an optimal solution and get the message
"feasible
time limit reached"
If I give myself 10 seconds but only 1 node I get the message
"feasible
node limit reached"
So in both cases above a feasible solution was found within the resource
limits. See example code for how to retrieve the solutions. Likewise,
had the problem terminated due to a time limit with no feasible solution
you would get
"infeasible
time limit reached"
You only know you are optimal when you get the message that an optimal
solution was found.
For Cbc, the Optimization Services code uses the underlying Cbc method
bool feasibleSolution(int & numberIntegerInfeasibilities,
int & numberObjectInfeasibilities) const;
I am assuming I have understood/implemented this correctly in my code.
If not, hopefully someone will correct me.
If you want more information on using the result language (get primal
values, dual values, etc) see
https://projects.coin-or.org/CoinBazaar/browser/projects/ApplicationTemplates/trunk/osResultDemo/OSResultDemo.cpp
All of this is solver agnostic. You can do this with the nonlinear
solvers such as Ipopt, Couenne, and Bonmin. You can also call the
solvers over the network. See
You can also do this from GAMS and AMPL.
https://projects.coin-or.org/OS
Cheers
> I agree with Matt. The design of Osi works fine for calling MILP
> solvers. It is not a perfect fit and there are ways in which Osi could
> have been designed a bit differently to better support calling MILP
> solvers directly. However, I don't see any reason OsiCbc can't
> support post-solution queries the way many of the other OsiXxx
> implementations do when solving an MILP.
>
> For Troy's question, something like getColSolution() or getObjValue()
> should work, in principle, to determine if a feasible solution has
> been found, but it looks to me like these are just pass-throughs to
> the interface of the LP solver (Clp) and so might not return the
> desired information. It is on my TODO list to look at this, but it
> might take some time.
>
> Cheers,
>
> Ted
>
> and I believe we should support calling Cbc through Osi as best we can.
>
> On Tue, Jun 28, 2011 at 5:51 PM, Matthew Galati
> <matthew.galati at gmail.com> wrote:
>> Just my 2-cents, but dropping to Cbc instead of supporting what is needed at
>> OsiCbc defeats the purpose of OSI. OsiXxx should at least support LP and
>> MILP solvers.
>>
>> If the long term plan is really to just support LP solvers, than let's call
>> it OSILP or something more appropriate.
>>
>> Matt
>>
>>
>>
>> On Tue, Jun 28, 2011 at 5:46 PM, Stefan Vigerske<stefan at math.hu-berlin.de>
>> wrote:
>>>
>>> Hi,
>>>
>>> I agree with Lou.
>>> If you still want to use Cbc via Osi, then you can get to the CbcModel
>>> via OsiCbc::getModelPtr() and call the status methods from there.
>>> You can then call isNodeLimitReached(), isSecondsLimitReached(), and get
>>> the dual bound via getBestPossibleObjValue().
>>> Comparing the latter with getObjValue() should be most reliable for
>>> seeing whether Cbc finished with a proven optimal solution or how far it
>>> may still be away.
>>>
>>> Stefan
>>>
>>>> Troy,
>>>>
>>>>> Using the OSI interface to CBC,
>>>>
>>>> This is your mistake :-) Seriously, Osi is just not set up to
>>>> provide the kind of control necessary for a MIP solver. If you want to
>>>> do anything more than run the solver to completion, you're better off to
>>>> use Cbc directly.
>>>>
>>>> There are a few folks out there who are more fond of OsiCbc. One
>>>> of
>>>> them may be able to offer more helpful advice.
>>>>
>>>> Lou
>>>>
>>>> if I call setMaximumSeconds and
>>>>> branchAndBound() terminates due to that limit, how do I distinguish
>>>>> between it finishing with a feasible (but possibly suboptimal)
>>>>> solution and finishing with an infeasible solution? I see methods
>>>>> like isProvenOptimal and isProvenPrimalInfeasible, but nothing like
>>>>> isFeasible.
>>>>>
>>>>> I could loop over all of the integer variables and check if they are
>>>>> within tolerance of integer values, but it seems that there should be
>>>>> a method that does that (and does not risk me using the wrong
>>>>> tolerance or getting a different rounding error).
>>>>>
>>>>> Is there something I am missing?
>>>>>
>>>>> Troy
>>>>>
>>>>>
>>>>> _______________________________________________ Cbc mailing list
>>>>> Cbc at list.coin-or.org http://list.coin-or.org/mailman/listinfo/cbc
>>>>
>>>> _______________________________________________
>>>> Cbc mailing list
>>>> Cbc at list.coin-or.org
>>>> http://list.coin-or.org/mailman/listinfo/cbc
>>>>
>>>
>>> _______________________________________________
>>> Cbc mailing list
>>> Cbc at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/cbc
>>
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/cbc
>>
>>
>
>
>
--
Kipp Martin
Professor of Operations Research
and Computing Technology
Booth School of Business
University of Chicago
5807 South Woodlawn Avenue
Chicago, IL 60637
773-702-7456
kmartin at chicagobooth.edu
http://www.chicagobooth.edu/faculty/bio.aspx?person_id=12825325568
http://projects.coin-or.org/OS
More information about the Cbc
mailing list