tag:blogger.com,1999:blog-8781383461061929571.post1620685047111491796..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: K Best SolutionsPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-8781383461061929571.post-84476602097248431372018-09-04T10:54:27.901-04:002018-09-04T10:54:27.901-04:00According to the most recent documentation, the po...According to the most recent documentation, the populate method does in fact solve the problem to optimality (assuming, of course, that you don't run out of time or memory first). The two methods (populate and solve+populate) will not always generate the same results, but they should both generate results that include an optimal solution.<br /><br />The CPLEX user manual now has a section "Choosing whether to accumulate or populate" that discusses differences between solve (with a pool size and filtering criteria you get to choose) versus populate. I don't know if they discuss solve+populate in detail anywhere.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-27475113728306731792018-09-03T19:09:07.299-04:002018-09-03T19:09:07.299-04:00Hi Paul, i'm also running populate and solve+p...Hi Paul, i'm also running populate and solve+populate. Even though i'm able to find the optimun with both strategies I'm not sure it's always possible.<br /> <br />Do you know if populate by itself is able to find the optimun value? Or it just finds a bigger diversity than solve itself?<br />In other words, is populate and solve+populate the same approach? When comparing both methods it took more iterations on the first strategy, but the objective value was the same. <br /><br />Ps: I do not need the K-best solutions, but the best one alongside others.Anonymoushttps://www.blogger.com/profile/03555271261712591986noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-34284191275538888822013-12-30T09:53:28.731-05:002013-12-30T09:53:28.731-05:00Thanks. That will help me a lot. Thanks. That will help me a lot. Maziarhttps://www.blogger.com/profile/07529746182972982381noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-27075392271612263922013-12-25T17:47:23.227-05:002013-12-25T17:47:23.227-05:00With the solution pool method, I'm not sure th...With the solution pool method, I'm not sure there is any guarantee that you always get the K best solutions. Based on my experiments (reported in the post), the safest way to use the pool is to set the pool capacity as high as possible. The default is 2.1 billion, but how high you can go clearly depends on how much memory you have, and how high you need to go depends on how many feasible solutions exist (which you typically won't know). My take is that it is a gamble, but with the default capacity setting probably a pretty good gamble.<br /><br />If the pool method does find the K best solutions, I do not think you can extract them in objective order. I believe you will have to scan all the solutions in the pool and figure out which are the K best.<br /><br />As far as the method you are using, I think that with all the restarts it is slower (perhaps much slower) than the callback methods (labeled "reject" and "inject") I described above. They, like your current method, are guaranteed to produce the K best solutions (though not necessarily in ascending objective order).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-51891958631278406832013-12-24T11:28:49.069-05:002013-12-24T11:28:49.069-05:00Hello Paul.,
I have a question on Solution Pool me...Hello Paul.,<br />I have a question on Solution Pool method of CPLEX. Does it give us the best K solutions or it might be few solutions left better than those K ones? I have been using the integer-cut constraint to generate all the solutions. This will reassure me that I will find the exact K best solutions and in the increasing value of objective function (while minimizing). However this needs restarting the optimization every time I add the constraint. Does the pool method give me the ordered list of solutions?Maziarhttps://www.blogger.com/profile/07529746182972982381noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3734458083667527042012-07-13T12:00:29.076-04:002012-07-13T12:00:29.076-04:00Just sent you the code.
PaulJust sent you the code.<br /><br />PaulPaul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47919501996133841792012-07-12T16:48:13.120-04:002012-07-12T16:48:13.120-04:00Paul, I've been looking to generate K best sol...Paul, I've been looking to generate K best solutions where K depend on the problem size (e.g. K=N in your example). I came across your blog. I also code in c++ and use concert technology. Could you please e-mail me your code? My e-mail is bkeskin@cba.ua.edu<br /><br />Thanks,<br />BurcuBurcu Keskinhttps://www.blogger.com/profile/12312218551552522348noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-26419547631824990292012-06-11T19:01:48.508-04:002012-06-11T19:01:48.508-04:00Bissa: I just sent you the Java code. -- PaulBissa: I just sent you the Java code. -- PaulPaul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89907650036718332242012-06-11T18:57:37.061-04:002012-06-11T18:57:37.061-04:00Dear Paul,
This is an excellent article.
I don&#...Dear Paul,<br /><br />This is an excellent article.<br /><br />I don't have AMPL. But I can run CPLEX through C++/Java. It would be very good for me if you provide me the Java code that you have.<br /><br />My email :<br /><br />...@gmail.com<br /><br />Best regards,<br /><br />Bissa NathBissa Nathnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83349744972823887362012-05-23T15:50:30.872-04:002012-05-23T15:50:30.872-04:00It's not hard to do, but the answer was long e...It's not hard to do, but the answer was long enough to warrant a separate post. The link is in the addendum above.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88987344603726257292012-05-23T11:21:47.308-04:002012-05-23T11:21:47.308-04:00Paul, Have you used Cplex solution pool with AMPL?...Paul, Have you used Cplex solution pool with AMPL? If you did, could you share the codes you have: <br />1) to populate the solution pool after solving the MIP, and<br />2) to poluate the pool only.<br />Thanks.Pratimnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-61764665675614460162012-04-21T09:08:28.934-04:002012-04-21T09:08:28.934-04:00@Thomas: Indeed. It would be slower than the callb...@Thomas: Indeed. It would be slower than the callback approach, since you would be restarting the search tree each time. Also, as I mentioned in the last post, it is easy to exclude solutions when the variables are all binary, not so easy when they are general integer. (It's easy to exclude a specific general integer solution if you are using constraint programming, though.)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-29894727782916387682012-04-21T04:08:23.816-04:002012-04-21T04:08:23.816-04:00You could also mention your last blog post. One co...You could also mention your last blog post. One could K-times exclude the current optimal solution and reoptimize. This should ensure finding the K best solutions.Thomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-33568672325730364492012-04-20T10:41:03.273-04:002012-04-20T10:41:03.273-04:00J-F: Thanks for the pointer. I should be able to...J-F: Thanks for the pointer. I should be able to acquire the paper through our library system.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-40518587143546660452012-04-20T10:30:38.191-04:002012-04-20T10:30:38.191-04:00Paul,
we did something in constraint progrmaming ...Paul,<br /><br />we did something in constraint progrmaming that might interest you<br /><br />Michel Lefebvre, Jean-François Puget and Petr Vilim. Route Finder : Efficiently Finding K Shortest PathsUsing Constraint Programming, in proceedings of CP 2011Jean-François Pugethttp://twitter.com/JFPugetnoreply@blogger.com