[Osi] Several integers solutions

[Goossens Jan-Willem]

Robert,

> The particular kind of constraint that you need to add to cut off a
> solution depends on your problem.
Thanks for the generalization.

For a specific type of problem, it could pay off to get the strongest (valid..) cut.

Thus, *if*
         sum_{i in S} x_i <= |S| - 1
is valid, then it cuts off more than
         sum_{i in S} x_i - sum_{i in T} x_i <= |S| - 1

Anyway, adding cuts and resolving is the only way to go for Nathann, I guess.


Jan-Willem

-----Original Message-----
From: Robert Schwarz [mailto:mail at rschwarz.net]
Sent: 31 July 2009 15:08
To: Goossens Jan-Willem [Internet]
Cc: Nathann Cohen; osi at list.coin-or.org
Subject: Re: [Osi] Several integers solutions



Goossens Jan-Willem wrote:
> [...]
>
> What you can do to get multiple solutions is add constraints that cut
> off all previous solutions.
>
> The particular kind of constraint that you need to add to cut off a
> solution depends on your problem.
>
> Let’s use what you describe. Say in the first solve you find the
> solution x0, with S = {i | x0_i = 1}. Then you could add a constraint
> (again, depending on your problem)
>
> Sum_{i  in S}  x_i  <= |S| - 1
>
> And solve this new problem from scratch. You can continue this, adding
> another constraint each time, as long as you want.
>
> For example, you can continue this until the objective value is too far
> from the original obj val, or something.
>

The approach to get more optimal solutions by cutting off known ones
works in principle, but I think the kind of constraint you propose
doesn't work in general (for you don't allow keeping all those variables
1 and then switch some more to 1).

Assuming you use only binary variables and have a point x, with sets
  S = {i | x_i = 1} and
  T = {i, x_i = 0}.
Then there is the following similar, yet weaker constraint that cuts off
 this point x (but no other binary point):
Please correct me, if I'm mistaken here.

--
Robert Schwarz <mail at rschwarz.net>

Get my public key at http://rschwarz.net/key.asc