[Scip] More solutions
Julio Rojas
jcredberry at gmail.com
Thu Nov 19 22:34:10 MET 2009
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20091119/b14c7194/attachment.html
More information about the Scip
mailing list