[Osi] Several integers solutions

Nathann Cohen nathann.cohen at sophia.inria.fr
Fri Jul 31 13:46:20 EDT 2009


Don't you think there may be some special way to do it with Cbc, though ? It
seems a huge waste to begin again the computations from scratch, or just to
modify the problem when all the necessary informations to enumerate the
solutions seems to be available to the solver :-/

Thanks for you help, though ! ;-)

Nathann

2009/7/31 Goossens Jan-Willem <Jan-Willem.Goossens at nc3a.nato.int>

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090731/1e7546c8/attachment.html>


More information about the Osi mailing list