[Scip] More solutions

Julio Rojas jcredberry at gmail.com
Thu Nov 19 18:03:54 MET 2009


Ok. It works, now to the hard work. Again, thanks.
-------------------------------------------------
Julio Rojas
jcredberry at gmail.com


On Thu, Nov 19, 2009 at 5:46 PM, Stefan Vigerske
<stefan at math.hu-berlin.de>wrote:

> 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
> >>>>>>
> >>>>>
> >>>>
> >>>
> >>>
> >>
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20091119/cee8efd1/attachment.html


More information about the Scip mailing list