[Scip] More solutions
Julio Rojas
jcredberry at gmail.com
Fri Nov 20 10:30:59 MET 2009
Well, thanks for the suggestion Stefan. The results are the following:
SCIP Status : solving was interrupted [user interrupt]
Solving Time (sec) : 0.01
Solving Nodes : 51
Primal Bound : +1.00000000000000e+20 (0 solutions)
Dual Bound : +2.60000000000000e+01
Gap : infinite
Feasible Solutions : 10 (3 non-trivial feasible subtrees)
I think this is good for me. Specially if the number of feasible solutions
is small (not the reported one, but the real one). Much better than having
an arbitrary solution is having 10 arbitrary solutions. ;)
Still, what's the difference with the "optimize" command? It says:
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes : 1
Primal Bound : +2.60000000000000e+01 (1 solutions)
Dual Bound : +2.60000000000000e+01
Gap : 0.00 %
Thanks a lot for your help.
-------------------------------------------------
Julio Rojas
jcredberry at gmail.com
On Fri, Nov 20, 2009 at 9:12 AM, Stefan Heinz <heinz at zib.de> wrote:
> 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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20091120/271136e7/attachment.html
More information about the Scip
mailing list