[Scip] More solutions
Julio Rojas
jcredberry at gmail.com
Fri Nov 20 13:00:59 MET 2009
Thanks for the explanation Arwin. My problem doesn't have a global optimum,
as it is kind of a knapsack problem where I need to fill a minimum number of
equal items, given that if some item is in the bag, another one cannot. With
a lot of constraints of this type, the chance of having just one solution is
big, but as the number of constraints dwindle the number of solutions grow.
As I told, in this simplified version of the problem all the solutions have
the same value, but when look at the real problem, this, almost surely, is
not be the case. I need a set of solutions to compare and get the one that
solves the original problem better.
So, "optimize" might just show the first solution it finds, doesn't it?
-------------------------------------------------
Julio Rojas
jcredberry at gmail.com
2009/11/20 Armin Fügenschuh <fuegenschuh at zib.de>
> Dear Julio,
>
> The difference between both commands is the following:
>
> - "count" gives *all* feasible solutions for a given IP.
>
> - "optimize" gives only the global optimal solution (in the end),
> where some more feasible solutions might (or might not) be found
> during the branch-and-bound search (or by one of the heuristics).
>
> Regards,
> Armin
>
>
> 2009/11/20, Julio Rojas <jcredberry at gmail.com>:
> > 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
> >>
> >>
> >>
> >
>
>
> --
>
> 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/3d3f961c/attachment.html
More information about the Scip
mailing list