[Scip] More solutions
Stefan Heinz
heinz at zib.de
Fri Nov 20 09:12:09 MET 2009
Hi Julio,
I would suggest to do the following:
1) Solve the original problem to optimality and let c^* be the optimal value
2) Add the objective function as constraint with left and right hand side
equal to c^*
3) load the adjusted problem into SCIP
4) set the parameter <constraints/countsols/sollimit> to the number of optimal
solution you want to collect, let say 10. This can be done as follows:
SCIP> set constraints countsols sollimit 10
5) load the settings Armin told you to avoid dual fixings
6) start counting
Then SCIP will stop if the given number of solutions is exceeded.
If this could work for you we can provide you with the functionality to write
the collected solution into a file.
Best Stefan
Am Donnerstag 19 November 2009 schrieb Julio Rojas:
> Thanks Armin. Maybe I don't need "write allsolution", as sometimes the
> number of solutions can be quite big, but "write solutions 10" to write the
> first 10 solutions. I have tried the "count" command to very weird results,
> as you say (the number of solutions reported by "count" vastly differs from
> the one obtained after "optimize"). Again, I don't need all solutions, but
> only some of them to pick from them the one I need (might or might not be
> the first, but by having more than one I can help reduce the probability of
> a "bad" solution).
>
> I hope you get to implement this command. I believe I'm not the only one
> interested. Good luck and godspeed.
> -------------------------------------------------
> Julio Rojas
> jcredberry at gmail.com
>
>
> 2009/11/19 Armin Fügenschuh <fuegenschuh at zib.de>
>
> > Dear Julio,
> >
> > to count all solutions of a given binary or integer linear program,
> > SCIP offers already the "count" command from the interactive shell
> > (before, use "set load ./setting/emphasis/counter.set", which switches
> > off some presolve features that otherwise disturb the counting). From
> > this you already get the number of feasible solutions. To output them
> > all to a file, we have a dialog (as Tobias described), which is under
> > development. Please test the "count" command first, and if you need
> > "write allsolutions", we'll find a way to make it available for you.
> >
> > Regards,
> > Armin
> >
> > 2009/11/19 Stefan Vigerske <stefan at math.hu-berlin.de>:
> > > Hi,
> > >
> > > let barX be the solution you want to eliminate, then try
> > > sum_{i: barX_i = 0} X_i + sum_{i: barX_i = 1} (1 - X_i) >= 1
> > > This should say that at least one variable X_i should take a value
> > > different from barX_i.
> > >
> > > Stefan
> > >
> > > Am 19.11.2009 17:37, schrieb Julio Rojas:
> > >> BTW, when I add a constraint with the first solution obtained the
> >
> > presolver
> >
> > >> deletes it. The constraint is of the type:
> > >>
> > >> sum(Xi)<floor(n/2)+1, Xi in 1st Solution.
> > >>
> > >> Any other idea?
> > >> -------------------------------------------------
> > >> Julio Rojas
> > >> jcredberry at gmail.com
> > >>
> > >>
> > >> On Thu, Nov 19, 2009 at 4:47 PM, Julio Rojas <jcredberry at gmail.com>
> >
> > wrote:
> > >>> I think I'll try this. The algorithm I'm using is pretty fast and I
> >
> > think
> >
> > >>> it will handle this overload. Maybe times will go from 7 seconds to
> > >>> 45 seconds, but it's not that bad, specially for the worst case
> > >>> scenarios.
> >
> > But
> >
> > >>> it's much better to have it directly from the interface. :D
> > >>>
> > >>> Again, thanks.
> > >>>
> > >>> -------------------------------------------------
> > >>> Julio Rojas
> > >>> jcredberry at gmail.com
> > >>>
> > >>>
> > >>> On Thu, Nov 19, 2009 at 4:38 PM, Stefan Vigerske <
> >
> > stefan at math.hu-berlin.de
> >
> > >>>> wrote:
> > >>>>
> > >>>> Hi,
> > >>>>
> > >>>> if performance does not matter and since you said that all variables
> >
> > are
> >
> > >>>> binary, you could generate for each solution SCIP gives you a
> >
> > constraint
> >
> > >>>> that forbids exactly this solution, then reoptimize, see what is
> > >>>> solution you get then, exclude this one too, and so on...
> > >>>>
> > >>>> Stefan
> > >>>>
> > >>>> Am 19.11.2009 16:12, schrieb Julio Rojas:
> > >>>>> Thank you. I have never written a piece of C code and I'm in a
> > >>>>> tight schedule right now. I wanted to prove some convexity
> > >>>>> condition I
> >
> > thinnk
> >
> > >>>> is
> > >>>>
> > >>>>> hidden behind all possible solutions this problem has. I know all
> > >>>>
> > >>>> solutions
> > >>>>
> > >>>>> have the same value, but this is because this is a simplified
> > >>>>> version
> >
> > of
> >
> > >>>> a
> > >>>>
> > >>>>> much more complex problem. In the more complex problem, these
> >
> > solutions
> >
> > >>>> have
> > >>>>
> > >>>>> a different value and I don't know if the first solution obtained
> > >>>>> in
> >
> > the
> >
> > >>>>> simpler model is the best one. I have made an heuristic algorithm
> >
> > that
> >
> > >>>>> solves this problem, but I would really like to see if by picking a
> > >>>>> different solution (not the first one) I converge faster to the
> > >>>>> point
> >
> > I
> >
> > >>>> want
> > >>>>
> > >>>>> to get. I think this will have to wait until I have the time to
> > >>>>> look
> >
> > for
> >
> > >>>>> help in C coding.
> > >>>>>
> > >>>>> Sorry for all the bothering and thank you very much for all your
> > >>>>> help
> > >>>>
> > >>>> and
> > >>>>
> > >>>>> for an excelent program. Best regards.
> > >>>>> -------------------------------------------------
> > >>>>> Julio Rojas
> > >>>>> jcredberry at gmail.com
> > >>>>>
> > >>>>>
> > >>>>> On Thu, Nov 19, 2009 at 3:55 PM, Tobias Achterberg <
> >
> > achterberg at zib.de
> >
> > >>>>> wrote:
> > >>>>>> First, SCIP does not have a "populate" feature like CPLEX. That
> >
> > means,
> >
> > >>>> if
> > >>>>
> > >>>>>> the model is solved to optimality, you cannot get more solutions
> > >>>>>> (alternative optima or inferior solutions).
> > >>>>>>
> > >>>>>> SCIP collects all solutions that it finds during the solving
> >
> > process.
> >
> > >>>> With
> > >>>>
> > >>>>>> the "write solution" command, you can only write the current
> >
> > incumbent
> >
> > >>>>>> (i.e., best known solution).
> > >>>>>>
> > >>>>>> Using the callable library, you could also access the other
> >
> > solutions,
> >
> > >>>> but
> > >>>>
> > >>>>>> I think that this is not possible with the interactive version of
> >
> > SCIP.
> >
> > >>>>>> If you are not afraid of implementing stuff on your own, it is
> > >>>>>> very
> > >>>>
> > >>>> easy to
> > >>>>
> > >>>>>> extend SCIP to do what you want, i.e., to add an interactive
> > >>>>>> command
> > >>>>
> > >>>> like
> > >>>>
> > >>>>>> "write allsolutions". You just need to write a dialog handler
> > >>>>>> plugin
> > >>>>
> > >>>> (look
> > >>>>
> > >>>>>> at src/scip/dialog_default.c how to do this). The SCIP team can
> > >>>>
> > >>>> certainly
> > >>>>
> > >>>>>> help you with this if you have any questions.
> > >>>>>>
> > >>>>>>
> > >>>>>> Tobias
> > >>>>>>
> > >>>>>> Julio Rojas wrote:
> > >>>>>>> Maybe I'm doing something wrong. Let me write the commands I'm
> > >>>>
> > >>>> issuing:
> > >>>>>>> read problem.lp
> > >>>>>>> set limits solutions 1
> > >>>>>>> optimize
> > >>>>>>> write solution sol1.txt
> > >>>>>>> read problem.lp
> > >>>>>>> set limits solution 2
> > >>>>>>> optimize
> > >>>>>>> write solution sol2.txt
> > >>>>>>>
> > >>>>>>> sol1.txt and sol2.txt should be different, as the optimizer is
> >
> > telling
> >
> > >>>>>>> me it have found two solutions, but that's not the case as both
> > >>>>>>> solutions are the same (diff sol1.txt sol2.txt).
> > >>>>>>>
> > >>>>>>> If I do this:
> > >>>>>>>
> > >>>>>>> read problem.lp
> > >>>>>>> set limits solutions 1
> > >>>>>>> optimize
> > >>>>>>> write solution sol1.txt
> > >>>>>>> set limits solution 2
> > >>>>>>> optimize
> > >>>>>>>
> > >>>>>>> Then the solver tells me the model is already solved and the same
> > >>>>>>> solution appears.
> > >>>>>>>
> > >>>>>>> So, maybe there is just one solution even if the solver says
> > >>>>>>> there
> >
> > are
> >
> > >>>>>>> two? Or I'm not doing the correct procedure to get the second
> > >>>>
> > >>>> solution.
> > >>>>
> > >>>>>>> Thank you so much for your time and patience.
> > >>>>>>> -------------------------------------------------
> > >>>>>>> Julio Rojas
> > >>>>>>> jcredberry at gmail.com <mailto:jcredberry at gmail.com>
> > >>>>>>>
> > >>>>>>>
> > >>>>>>>
> > >>>>>>> On Thu, Nov 19, 2009 at 2:45 PM, Stefan Vigerske
> > >>>>>>> <stefan at math.hu-berlin.de <mailto:stefan at math.hu-berlin.de>>
> >
> > wrote:
> > >>>>>>> Hi,
> > >>>>>>>
> > >>>>>>> I think the idea was to set the limit to one before starting
> > >>>>>>> optimization. Then it should stop when the limit is reached,
> > >>>>>>> and
> >
> > so
> >
> > >>>>>>> on...
> > >>>>>>>
> > >>>>>>> Stefan
> > >>>>>>>
> > >>>>>>> Am 19.11.2009 14:22, schrieb Julio Rojas:
> > >>>>>>> > I tried to do what you suggest me. In one problem, after
> > >>>>>>>
> > >>>>>>> optimization, the
> > >>>>>>>
> > >>>>>>> > report is the following:
> > >>>>>>> >
> > >>>>>>> > SCIP Status : problem is solved [optimal solution
> >
> > found]
> >
> > >>>>>>> > Solving Time (sec) : 0.07
> > >>>>>>> > Solving Nodes : 1
> > >>>>>>> > Primal Bound : +5.20000000000000e+01 (2 solutions)
> > >>>>>>> > Dual Bound : +5.20000000000000e+01
> > >>>>>>> > Gap : 0.00 %
> > >>>>>>> >
> > >>>>>>> > So, in theory, I have two solutions. If I check the value
> > >>>>>>> > of
> >
> > the
> >
> > >>>>>>> solution
> > >>>>>>>
> > >>>>>>> > limit it shows:
> > >>>>>>> > SCIP> set limits solution
> > >>>>>>> > current value: -1, new value [-1,2147483647]: 2
> > >>>>>>> > parameter <limits/solutions> set to 2
> > >>>>>>> >
> > >>>>>>> > It doesn't matter if I do it before or after optimization,
> >
> > when
> >
> > >>>> I
> > >>>>
> > >>>>>>> run
> > >>>>>>>
> > >>>>>>> > optimize again it tells me the problem has already been
> >
> > solved
> >
> > >>>>>>> and no new
> > >>>>>>>
> > >>>>>>> > solution is presented.
> > >>>>>>> >
> > >>>>>>> > Thanks for your kind help.
> > >>>>>>> > -------------------------------------------------
> > >>>>>>> > Julio Rojas
> > >>>>>>> > jcredberry at gmail.com <mailto:jcredberry at gmail.com>
> > >>>>>>> >
> > >>>>>>> >
> > >>>>>>> >
> > >>>>>>> >
> > >>>>>>> > _______________________________________________
> > >>>>>>> > Scip mailing list
> > >>>>>>> > Scip at zib.de <mailto:Scip at zib.de>
> > >>>>>>> >
> > >>>>>>> > http://listserv.zib.de/mailman/listinfo/scip
> > >>>>>>>
> > >>>>>>> _______________________________________________
> > >>>>>>> Scip mailing list
> > >>>>>>> Scip at zib.de
> > >>>>>>> http://listserv.zib.de/mailman/listinfo/scip
> > >
> > > _______________________________________________
> > > Scip mailing list
> > > Scip at zib.de
> > > http://listserv.zib.de/mailman/listinfo/scip
> >
> > --
> >
> > Dr. Armin Fügenschuh
> >
> > Konrad-Zuse-Zentrum für
> > Informationstechnik Berlin (ZIB)
> >
> > Division Scientific Computing
> > Department Optimization
> >
> > Takustrasse 7
> > 14195 Berlin
> >
> > Tel. : +49 (0)30 84185-205
> > Fax: +49 (0)30 84185-269
> > email: fuegenschuh at zib.de
More information about the Scip
mailing list