tag:blogger.com,1999:blog-3001120404365621770.post9145680416731595569..comments2023-10-04T08:15:37.640-07:00Comments on Constraint Programming: Yes we can … optimize!Jean-Charles Réginhttp://www.blogger.com/profile/06540516780781311246noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3001120404365621770.post-28400360158181169612011-04-26T05:19:03.291-07:002011-04-26T05:19:03.291-07:00I can understand how you can introduce a "str...I can understand how you can introduce a "strictly better" constraint to integrate a integer-valued objective function. However, I wonder how you can do the same for continuous objective functions, since "strictly better" has no meaning in this context...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3001120404365621770.post-77986310152332522812011-04-13T08:25:32.373-07:002011-04-13T08:25:32.373-07:00Hello Renaud,
Thank you for your comment. When I ...Hello Renaud,<br /><br />Thank you for your comment. When I was still at Dynadec, I've build an example in the userman of Comet doing exactly what you suggest for the quadratic assignment problem. If you have the userman of Comet, just have a look at Section "Speeding Up Branch and Bound with CBLS". I agree with you this is a very good approach when you need to prove optimality. <br /><br />The problem is that it is not always easy to design good incremental moves. That's why I usually prefer LNS (when proof of optimality is not important).pschaushttps://www.blogger.com/profile/10578391475922351456noreply@blogger.comtag:blogger.com,1999:blog-3001120404365621770.post-28468071133229457402011-04-12T02:40:11.797-07:002011-04-12T02:40:11.797-07:00Sure it works, thanks to tight bounds that might b...Sure it works, thanks to tight bounds that might be delivered if you are lucky (or smart) enough to have this objective variable involved in such global constraint delivering tight bounds. <br /><br />One might be interested in having a search _directed towards the improvement_ of the solution, as done in local search, where you sense the neighbourhood, and go to the next "best" solution among the neighbours. This is also why simplex is so good, it follows a path towards improvement. <br /><br />Intuitively, CP will follow its own path, described by the distribution procedure and might be unaware of interesting neighbours that are just one "perturbation" away, re-building the solution from the choice that would allow the search implementing this perturbation. <br /><br />One might be interested for instance in a composite search using CP to find a solution, then exploring the neighbourhood for a local optimum, and using this improved optimum as new bound to continue the search in a B&B fashion. Is there any chance that it would make the best of both worlds?rdlnoreply@blogger.com