[Cbc] Constraint to make a solution infeasible

[Stuart Mitchell (uni)]

ok to find all solutions at a degenerate optimal point.

1) add a constraint fixing the optimal objective value  x1 + x2 + x3 + x4 == 4
2) use the method outlined in
http://www.springerlink.com/content/q10kw74m2127n119/ to find all
solutions to the new problem

or

use cplex which does it automatically

https://www-304.ibm.com/support/docview.wss?uid=swg21399929&wv=1

Stu

On Tue, Jun 14, 2011 at 3:32 PM, Terry <maillst at aol.com> wrote:
>
> Thanks Stu.
>
> So I need a different approach.
>
> I see what you're saying. I could add a constraint like:
> x1 + x2 + x3 + x4 >= 4.1
> That would "cut off" the first solution with obj value = 4, and as you note, other solutions with the same obj value. But, I need all those other solutions too.
>
> I guess I could change the obj function slightly:
> x1 + 1.1 x2 + 1.01 x3 + 1.001 x4
> Then, those solutions that previously had the same obj value of 4, would now all be different. That would allow me to re-run the solver for each solution. It seems to work for this simple example.
>
> My real world problem could have 400 variables. I'm concerned about the amount of precision I would need.
>
> Thoughts about this method?
> Any other ideas?
>
> Thanks.
> Terry
>
>
> On Jun 13, 2011, at 7:14 PM, Stuart Mitchell (uni) wrote:
>
>> Ok I found which of my emails are a member of this list. Here is the
>> longer explanation.
>>
>> Unfortunately that example assumes all variables are binary [0,
>> 1] variables (see the assert in the example), this approach does not
>> work with general integer
>> variables, as each cut generated will make more than one possible
>> solution infeasible.
>>
>> Of course if you assume the solution is not degenerate (unlikely) you
>> could always put in a constraint that cuts off the solution based on
>> the objective value. Though I see the solutions you have already found, have the
>> same objective value.
>>
>> Stu
>>
>> On Tue, Jun 14, 2011 at 12:09 PM, Stuart Mitchell
>> <s.mitchell at auckland.ac.nz> wrote:
>>> The solution given int the examples only really work for binary [0,1]
>>> variables, otherwise the cuts cut more than one solution.
>>>
>>> Stu
>>>
>>>
>>> On Mon, Jun 13, 2011 at 3:08 PM, Terry <maillst at aol.com> wrote:
>>>>
>>>> Thanks for the tip Ed. That sounds like exactly what I want.
>>>> I changed repeat.cpp to use readLp instead of readMps. Then I was able to
>>>> run it on my file.
>>>> Any idea why it only gives 3 answers, [2 0 0 2], [0 2 0 2], [1 1 1 1]? Then
>>>> it gives up with:
>>>> Cbc0006I The LP relaxation is infeasible or too expensive
>>>> /coin/Coin-Pkg/bin/terry/ex2.lp took 0.00074 seconds, 0 nodes with objective
>>>> 1.79769e+308 Finished
>>>>
>>>> I added bounds 0 to 10 for each variable and I tried changing the obj and
>>>> constraints slightly, but I could not get it to give more than 2 or 3
>>>> solutions before failing. I guess there's a lot more I need to understand
>>>> first.
>>>> Terry
>>>>
>>>>
>>>> On Jun 12, 2011, at 7:56 PM, Ed Bulog wrote:
>>>>
>>>> Hi Terry,
>>>>
>>>> While I'm far from an expert, I remember that the "repeat.cpp" example
>>>> (https://projects.coin-or.org/Cbc/browser/stable/2.7/Cbc/examples/repeat.cpp)
>>>> essentially does this. I believe it repeatedly finds the optimal solution
>>>> and then adds a cut to remove it, so that you end up with the 20 "best"
>>>> solutions. Hope that helps you.
>>>>
>>>> Cheers,
>>>>
>>>> Ed
>>>>
>>>> On 13 June 2011 11:08, Terry <maillst at aol.com> wrote:
>>>>>
>>>>> CBC will find an optimal solution to my IP problem. Now I want the "next"
>>>>> optimal solution. That is, I want to make the previous solution infeasible
>>>>> and run CBC again to find another solution.
>>>>>
>>>>> Here's an example I'm working with:
>>>>>
>>>>> Minimize
>>>>>  x1 + x2 + x3 + x4
>>>>> Subject To
>>>>>  5 x1 +  5 x2 >= 10
>>>>>  7 x3 + 14 x4 >= 21
>>>>> Integers
>>>>>  x1
>>>>>  x2
>>>>>  x3
>>>>>  x4
>>>>> End
>>>>>
>>>>>
>>>>> Optimal - objective value 4.00000000
>>>>>      0 x1                     2                      1
>>>>>      1 x2                     0                      1
>>>>>      2 x3                     1                      1
>>>>>      3 x4                     1                      1
>>>>>
>>>>>
>>>>> Can I add a constraint so that [2 0 1 1] is infeasible, but allows any
>>>>> other answer? I'm afraid this is a stupid question, but I don't see how to
>>>>> do it.
>>>>>
>>>>> Thanks.
>>>>> Terry
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Cbc mailing list
>>>>> Cbc at list.coin-or.org
>>>>> http://list.coin-or.org/mailman/listinfo/cbc
>>>>
>>>>
>>>>
>>>
>>>
>>> _______________________________________________
>>> Cbc mailing list
>>> Cbc at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/cbc
>>>
>
>