[Cbc] Constraint to make a solution infeasible

[Terry]

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
>>