[Cbc] Several optimal integers solutions

[Gabrielle A. Grun]

HI Nathann,
Setting the maximum number of solution is an adjustment of the termination 
criteria. to the best of my knowledge, the solution count in Cbc is an 
integer solution count, not an optimal integer solution count.
Finding and getting output of all optimal answers is not exactly trivial. 
The best possible solution may differ from the "cutoff" by epsilon, and  the 
equality is treated differently in various  places.
The issue has been raised on the list or the coin-discuss list in the past.
It also has been on my "to do" items for a long time.



Gabrielle A. Grün, Ph.D. Student
School of Computing Science
Simon Fraser University
8888 University Drive
Burnaby, BC
V5A 1S6
<http://www.cs.sfu.ca/~grun>


----- Original Message ----- 
From: Nathann Cohen
To: cbc at list.coin-or.org
Sent: Sunday, August 02, 2009 8:54 AM
Subject: [Cbc] Several optimal integers solutions


Hello everybody !

I first asked my question on list Osi, thinking it may be an 
interface-related problem, but we found no answer and I hope you may be 
knowledgeable on this point :-)

Here is my problem : I have been solving continuous and integer programs 
with Cbc for some time now and it works absolutely fine !
Now, I would like to add some spices to what I am doing with it, by trying 
to compute several integers solutions to linear programs.

For example, I would like the following program ( with x and y binary 
variables ) :

Max:
   x + y
Constraints :
  x + y <= 1

to return the two solutions : x = 0, y=1 and x=1,y=0.

I saw there were functions in OsiClpInterface like setMaximumSolution and 
getMaximumSolutions. I also found the function getSolutionCount in CbcModel 
but it does not seem to do what I want it to do ;-)
I set the Maximum Number of Solutions to 200 and checked with 
getMaximumSolutions there was no problem assigning the value, but when I 
solve the previous problem getSolutionCount always return 1. Would you know 
how to make it work properly  ? Would you have an example where several 
solutions are found, which I could read to see both how it is done, and how 
to iterate through all the solutions found after ? It it possible to set the 
infinity as the MaximumNumber of solution if I want all of them ( I know 
this can grow quite huge ! )

>From what I learnt on list Osi, it may well be that these functions act very 
differently from what I first thought, and that the feature I am looking for 
is not implemented yet. I am actually trying to enumerate *** all the 
optimal solutions *** of a MIP containing binary/integer variables, and this 
would just imply that the solver should nut cut branch whose objective is 
"lesser or equal" to the current best integer solution, but only cut 
branches whose objective is "strictly less" than the current best integer 
solution.

I assure you I know several people who may be tremendously interested by 
such a feature in CBC !! :-)

Thank you very much for your help !

Nathann Cohen






_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/cbc



Gabrielle A. Grün, Ph.D. Student
School of Computing Science
Simon Fraser University
8888 University Drive
Burnaby, BC
V5A 1S6
<http://www.cs.sfu.ca/~grun>