[Osi] Several integers solutions

[Robert Schwarz]

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):
  sum_{i in S} x_i - sum_{i in T} x_i <= |S| - 1
Please correct me, if I'm mistaken here.

-- 
Robert Schwarz <mail at rschwarz.net>

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