[Cbc] Constraint to make a solution infeasible

[Stuart Mitchell (uni)]

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
>