[Scip] More solutions
Stefan Vigerske
stefan at math.hu-berlin.de
Thu Nov 19 17:46:33 MET 2009
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
>>>>>>
>>>>>
>>>>
>>>
>>>
>>
>
More information about the Scip
mailing list