tag:blogger.com,1999:blog-8781383461061929571.post2954314243626521320..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Finding All Solutions (or Not)Paul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-8781383461061929571.post-89530136691941572482018-08-15T11:26:09.764-04:002018-08-15T11:26:09.764-04:00Thanks for the post!
One other potential approach...Thanks for the post!<br /><br />One other potential approach: <br />If you restrict yourself to finding all optimal solutions to an LP, you could run an interior point method (without crossover), which would find the analytic center of the optimal face. If the IPM finds an extreme point then you have the unique optimal solution, otherwise the set of binding constraints at the analytic center defines the optimal face and you can extend this set of constraints by combining it with any of the non-binding constraints to form a basis, which would be optimal wherever it is feasible. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-59518017080976789032016-07-26T04:38:24.759-04:002016-07-26T04:38:24.759-04:00Yep. That works great for the type and size of pro...Yep. That works great for the type and size of problem instances I am dealing with. Many thanks Paul :-)Anonymoushttps://www.blogger.com/profile/09298545751078968862noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77212961843814807452016-07-24T16:56:21.172-04:002016-07-24T16:56:21.172-04:00Thanks Paul, Yes that sounds a lot better. Will tr...Thanks Paul, Yes that sounds a lot better. Will try that.Anonymoushttps://www.blogger.com/profile/09298545751078968862noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-46368426094914760912016-07-24T14:08:27.793-04:002016-07-24T14:08:27.793-04:00I'm not familiar with lp_solve (I know what it...I'm not familiar with lp_solve (I know what it is, but I don't recall ever using it), so I won't be much help with specifics. If your model has binary variables, you can try adding a no-good constraint to eliminate the first optimal solution, then solving again. If the new optimal solution has a worse objective value, you're done; if the objective is the same, record it, add another no-good constraint, and iterate. It's also a hack, but less brute force than toggling binaries.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-65416007329407973612016-07-24T04:32:54.200-04:002016-07-24T04:32:54.200-04:00Having a similar problem with lp_solve. I know my ...Having a similar problem with lp_solve. I know my models contain a few (well not too many) optimal solutions but the java wrapper I am using does not expose any methods for finding more than one. <br /><br />If I find the first one, add the extra constraint using the optimal value, can I then start toggling the variables one by one (they are binary variables) while I resolve? That'll give me 2^n possible iterations? which just seems like a hack :-(Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55352051209008174302016-04-10T10:44:00.879-04:002016-04-10T10:44:00.879-04:00It works,
really thank you for this idea!
Nice to ...It works,<br />really thank you for this idea!<br />Nice to meet you Helpful Prof Rubin.<br />Anonymoushttps://www.blogger.com/profile/09235623050374025622noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-46675849406460914262016-04-04T09:40:35.346-04:002016-04-04T09:40:35.346-04:00I'm not sure, since I don't use CP Optimiz...I'm not sure, since I don't use CP Optimizer. For constraint satisfaction problems, this is covered in the user manual for CP Optimizer. Look in "Search in CP Optimizer > Searching for solutions > Solving a satisfiability problem". You can use solve() to find the optimal objective value, add a constraint limiting the objective to that value, then do a new search as a constraint satisfaction problem and call next() repeatedly. That may not be the most efficient way, though. You probably should search the CP Optimizer support forum and, if you don't find it (I suspect it's a FAQ), ask there.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-34706423652536006582016-04-04T06:04:29.682-04:002016-04-04T06:04:29.682-04:00Hello, I'm using CPLEX Optimization Studio 12....Hello, I'm using CPLEX Optimization Studio 12.6 to find the optimum solution of a CP. I would like to find a way to get all the optimal solutions for that problem, because the default settings seem to return just one optimal solution. Can you help me or give me an example ? thanksAnonymoushttps://www.blogger.com/profile/09235623050374025622noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77151003904916064152016-02-19T16:01:21.363-05:002016-02-19T16:01:21.363-05:00Fair point. What I might describe as theoretical o...Fair point. What I might describe as theoretical or algorithmic investigations could legitimately require identifying the full set of optima. My comments should have been targeted at people solving problem instances for the purposes of making decisions (which may not benefit from a panoply of optimal choices, and will almost sure benefit from reaching a conclusion in a timely manner).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-59155883811114533242016-02-19T15:51:36.062-05:002016-02-19T15:51:36.062-05:00thanks for the post. One reason why you may want ...thanks for the post. One reason why you may want all the optimal solutions is that you know a set of optimal solutions exist and you are interested in the properties of the set. For example, when working with partially identified parameters in statistical estimators.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-19675484512220076842015-12-07T10:32:38.348-05:002015-12-07T10:32:38.348-05:00If you're asking whether commercial solvers co...If you're asking whether commercial solvers contain routines/commands to find all solutions, I've not aware of any that do.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-42050060957257356962015-12-01T22:08:46.672-05:002015-12-01T22:08:46.672-05:00using a commercial solver, is it possible to get a...using a commercial solver, is it possible to get all optimal vertices? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-29729525680218634972015-02-02T14:11:26.132-05:002015-02-02T14:11:26.132-05:00Maybe the method suggested by the Wikipedia: https...Maybe the method suggested by the Wikipedia: https://en.wikipedia.org/w/index.php?title=Special:CiteThisPage&page=LaTeX&id=413720397 (subsection labeled "BibTeX entry")?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-23448118143400328602015-02-02T13:10:15.538-05:002015-02-02T13:10:15.538-05:00Ahh...thank you very much Prof Rubin. This cleared...Ahh...thank you very much Prof Rubin. This cleared my doubts and you were very fast in replying me back. Thanks for that as well.<br />One off-topic question I have is that, I found quite a lot of posts very helpful for my thesis work and I want to cite your work but I can't find a proper Bibtex format for my references. Do you think you assist me regarding this issue?Varunnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55226498246491324982015-02-02T11:56:54.328-05:002015-02-02T11:56:54.328-05:00Suppose your LP is $$\min c'y$$ s.t. $$Ay \le ...Suppose your LP is $$\min c'y$$ s.t. $$Ay \le b$$ with $y\ge 0$. Let $\hat{y}$ and $\tilde{y}$ be two optimal solutions with objective value $f*$, and let $\lambda \in [0,1]$. Then $$c' [\lambda\hat{y}+(1-\lambda)\tilde{y}]=\lambda(c'\hat{y})+(1-\lambda)(c'\tilde{y})=\lambda f*+(1-\lambda)f*=f*$$ and $$<br />A[\lambda\hat{y}+(1-\lambda)\tilde{y}]=\lambda(A\hat{y})+(1-\lambda)(A\tilde{y})\le\lambda b+(1-\lambda)b=b.$$Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55129263573021968572015-02-02T10:50:50.660-05:002015-02-02T10:50:50.660-05:00Hello Prof Rubin,
I'm not able to understand ...Hello Prof Rubin, <br />I'm not able to understand the first two sentences of the section "Uncountably infinite is a lot.". I certainly did not understand how the convex combination with the lambda part has the same objective value. Can you please help me out in understanding that part?Varun RSnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89532007025272205272013-01-20T11:17:33.528-05:002013-01-20T11:17:33.528-05:00Looks right, but I glaze over quickly when it come...Looks right, but I glaze over quickly when it comes to complexity terminology.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-30575743021816925972013-01-19T18:58:37.806-05:002013-01-19T18:58:37.806-05:00"Finding all optimal solutions would be, what..."Finding all optimal solutions would be, what, NP-NP-hard?"<br /><br />#P-hard, I think. http://en.wikipedia.org/wiki/Sharp-P http://en.wikipedia.org/wiki/Sharp-P-complete Matthew Saltzmanhttps://www.blogger.com/profile/03225420623527632062noreply@blogger.com