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 :-/<br>
<br>Thanks for you help, though ! ;-)<br><br>Nathann<br><br><div class="gmail_quote">2009/7/31 Goossens Jan-Willem <span dir="ltr"><<a href="mailto:Jan-Willem.Goossens@nc3a.nato.int">Jan-Willem.Goossens@nc3a.nato.int</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Robert,<br>
<div class="im"><br>
> The particular kind of constraint that you need to add to cut off a<br>
> solution depends on your problem.<br>
</div>Thanks for the generalization.<br>
<br>
For a specific type of problem, it could pay off to get the strongest (valid..) cut.<br>
<br>
Thus, *if*<br>
sum_{i in S} x_i <= |S| - 1<br>
is valid, then it cuts off more than<br>
<div class="im"> sum_{i in S} x_i - sum_{i in T} x_i <= |S| - 1<br>
<br>
</div>Anyway, adding cuts and resolving is the only way to go for Nathann, I guess.<br>
<font color="#888888"><br>
<br>
Jan-Willem<br>
</font><div><div></div><div class="h5"><br>
-----Original Message-----<br>
From: Robert Schwarz [mailto:<a href="mailto:mail@rschwarz.net">mail@rschwarz.net</a>]<br>
Sent: 31 July 2009 15:08<br>
To: Goossens Jan-Willem [Internet]<br>
Cc: Nathann Cohen; <a href="mailto:osi@list.coin-or.org">osi@list.coin-or.org</a><br>
Subject: Re: [Osi] Several integers solutions<br>
<br>
<br>
<br>
Goossens Jan-Willem wrote:<br>
> [...]<br>
><br>
> What you can do to get multiple solutions is add constraints that cut<br>
> off all previous solutions.<br>
><br>
> The particular kind of constraint that you need to add to cut off a<br>
> solution depends on your problem.<br>
><br>
> Let’s use what you describe. Say in the first solve you find the<br>
> solution x0, with S = {i | x0_i = 1}. Then you could add a constraint<br>
> (again, depending on your problem)<br>
><br>
> Sum_{i in S} x_i <= |S| - 1<br>
><br>
> And solve this new problem from scratch. You can continue this, adding<br>
> another constraint each time, as long as you want.<br>
><br>
> For example, you can continue this until the objective value is too far<br>
> from the original obj val, or something.<br>
><br>
<br>
The approach to get more optimal solutions by cutting off known ones<br>
works in principle, but I think the kind of constraint you propose<br>
doesn't work in general (for you don't allow keeping all those variables<br>
1 and then switch some more to 1).<br>
<br>
Assuming you use only binary variables and have a point x, with sets<br>
S = {i | x_i = 1} and<br>
T = {i, x_i = 0}.<br>
Then there is the following similar, yet weaker constraint that cuts off<br>
this point x (but no other binary point):<br>
</div></div><div><div></div><div class="h5">Please correct me, if I'm mistaken here.<br>
<br>
--<br>
Robert Schwarz <<a href="mailto:mail@rschwarz.net">mail@rschwarz.net</a>><br>
<br>
Get my public key at <a href="http://rschwarz.net/key.asc" target="_blank">http://rschwarz.net/key.asc</a><br>
</div></div></blockquote></div><br>