Hello Community! Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost. An LP solver is library designed to solve LP problems. An LP problem is any problem of the form max sum(a_i x_i, 0 <= i <= m) subject to: sum(b_ij x_i, 0 <= i <= m) <= c_j, 0 <= j <= n x_i >= 0, 0<= i <= m where m is the number of variables and n is the number of constraints that define the problem. The constants are a_i, b_ij, and c_j; the variables are x_i A concrete example is the following: max 5x_1+2x_2 subject to: 2x_1 + 3x_2 <= 5 x_1 + 5x_2 <= 10 x_1 >= 0, x_2 >= 0 It is the objective of the LP solver to find a pair (x_1, x_2) such that 5x_1 + 2x_2 is maximum (this is unique) and that satisfies the constraints. In order to do this, I will implement the two major algorithms designed to solve these problems: the simplex algorithm and (possibly) Karmakar's algorithm. Furthermore, a programmatic interface and file parsing interface using Boost.Spirit will also be implemented. A second type of LP problem is where we require all the variables to be integers. Such an LP is called an integer programming problem, or ILP. We first note that solving ILP's is NP complete, therefore, there seems to be no efficient way to solve these kinds of problems. Nevertheless, algorithms have been developed to solve them and in practice, perform well. In particular, the cutting plane and branch and bound methods will be implemented. But why should we care about LP problems? The answer is that MANY problems in optimization can be reduced to solving an LP. A list of problems with polynomial time reductions to LP's include: * Scheduling problems * Knapsack problems, including their multi-dimensional variants * Allocation of resources * Covering/Packing problems * Cutting Stock problems and many others. Even the shortest path problem from graph theory can be phrased as an ILP (although one would never do this). If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week. Thank you for reading this and any feedback would be greatly appreciated! Chad Seibert
Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost. An LP solver is library designed to solve LP problems. An LP problem is any problem of the form
max sum(a_i x_i, 0 <= i <= m) subject to:
sum(b_ij x_i, 0 <= i <= m) <= c_j, 0 <= j <= n x_i >= 0, 0<= i <= m
where m is the number of variables and n is the number of constraints that define the problem. The constants are a_i, b_ij, and c_j; the variables are x_i A concrete example is the following:
max 5x_1+2x_2 subject to:
2x_1 + 3x_2 <= 5 x_1 + 5x_2 <= 10 x_1 >= 0, x_2 >= 0
It is the objective of the LP solver to find a pair (x_1, x_2) such that 5x_1 + 2x_2 is maximum (this is unique) and that satisfies the constraints. In order to do this, I will implement the two major algorithms designed to solve these problems: the simplex algorithm and (possibly) Karmakar's algorithm. Furthermore, a programmatic interface and file parsing interface using Boost.Spirit will also be implemented.
A second type of LP problem is where we require all the variables to be integers. Such an LP is called an integer programming problem, or ILP. We first note that solving ILP's is NP complete, therefore, there seems to be no efficient way to solve these kinds of problems. Nevertheless, algorithms have been developed to solve them and in practice, perform well. In particular, the cutting plane and branch and bound methods will be implemented.
But why should we care about LP problems? The answer is that MANY problems in optimization can be reduced to solving an LP. A list of problems with polynomial time reductions to LP's include:
* Scheduling problems * Knapsack problems, including their multi-dimensional variants * Allocation of resources * Covering/Packing problems * Cutting Stock problems
and many others. Even the shortest path problem from graph theory can be phrased as an ILP (although one would never do this).
If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week.
Thank you for reading this and any feedback would be greatly appreciated!
I really like this idea and would be willing to mentor such an effort. Please go ahead and submit your proposal as soon as the submission is open. Regards Hartmut --------------- http://boost-spirit.com
Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost. An LP solver is library designed to solve LP problems. An LP problem is any problem of the form
I really like this idea and would be willing to mentor such an effort. Please go ahead and submit your proposal as soon as the submission is open.
I also think this is a great summer project and would definitely encourage you to submit a proposal for this project. I would also strongly recommend that spend some time investigating other LP solver libraries and compare/contrast your approach to these as part of your proposal. This will help give you (and us) more perspective on design alternatives. Hartmut, I can't invite mentors for a couple of days. the GSoC folks have managed to disable that feature while they roll out a new version of their web app. Should be sometime toward the end of the week that I can start sending out invitations. Andrew
On 20/03/2011 13:17, Chad Seibert wrote:
A second type of LP problem is where we require all the variables to be integers. Such an LP is called an integer programming problem, or ILP. We first note that solving ILP's is NP complete, therefore, there seems to be no efficient way to solve these kinds of problems. Nevertheless, algorithms have been developed to solve them and in practice, perform well. In particular, the cutting plane and branch and bound methods will be implemented.
I personally have need of a compile-time ILP solver. Would you be interested in working on that?
On 03/20/2011 05:17 AM, Chad Seibert wrote:
Hello Community!
Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost. [snip]
Maybe you're already familiar with the MATLAB package cvx or similar such packages for python? As creating a fast solver for LPs and other similar optimization problems is a rather involved engineering task, it might be better to create something that can provide a unified, high-level interface to many of the existing commercial and open source solvers, rather than writing your own solver.
Chad Seibert-2 wrote:
Hello Community!
Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost.
Hi, I'm interested, I added on the Wish List a Constraint Programming library long time ago. Happy some one is volunteering for that. I see as many modern libraries separated in 3 parts: * Front ends * a modern c++ interface usually using expression templates (static) * parsing from a textual form (dynamic) * Core * Back ends (implementing algorithms or forwarding to existing libraries) I think this is a large project, and the perimeter should be reduced so you can have something by the end of the summer, but who knows maybe I'm too pessimistic. I hope this will encourage you to define a pragmatic proposal. Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/A-possible-GSOC-2011-proposal-idea-tp3391... Sent from the Boost - Dev mailing list archive at Nabble.com.
Chad Seibert wrote:
Hello Community!
Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost.
A second type of LP problem is where we require all the variables to be integers. Such an LP is called an integer programming problem, or ILP. We first note that solving ILP's is NP complete, therefore, there seems to be no efficient way to solve these kinds of problems. Nevertheless, algorithms have been developed to solve them and in practice, perform well. In particular, the cutting plane and branch and bound methods will be implemented.
and many others. Even the shortest path problem from graph theory can be phrased as an ILP (although one would never do this).
If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week.
Thank you for reading this and any feedback would be greatly appreciated! Chad Seibert
I think you're underestimating the effort required to produce an LP library which would be considered acceptable to boost by two orders of magnitude. Robert Ramey
On 3/20/2011 3:09 PM, Robert Ramey wrote:
I think you're underestimating the effort required to produce an LP library which would be considered acceptable to boost by two orders of magnitude.
I completely agree. Getting a basic LP running isn't difficult. Getting one that's robust in a production environment is a nightmare. That being said, I think the smaller problem of getting a nice, crisp boost front end done, with some drop-in backends (for MATLAB, NAG, and a couple of good open source solvers) would be great. I've had to re-invent that wrapper a couple of times, and I'm sure my attempts are horrendous. I freely admit to sucking at library writing.
If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week.
I think you're underestimating the effort required to produce an LP library which would be considered acceptable to boost by two orders of magnitude.
In 3 moths? Absolutely! But I'm not terribly worried about that. If Chad good submits a proposal with reasonable goals, I'd be more than happy to fund the proposal. Andrew
Andrew Sutton wrote:
If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week.
I think you're underestimating the effort required to produce an LP library which would be considered acceptable to boost by two orders of magnitude.
In 3 moths? Absolutely! But I'm not terribly worried about that. If Chad good submits a proposal with reasonable goals, I'd be more than happy to fund the proposal.
Hmmm- two orders of magnitude = 100 so I was saying that that such a job would be 100 weeks. My real point is that to be accepted into boost, a library pretty much has to be demonstrably better than any opensource/openlicense alternative. I'm not making a judgment on this, it's just the way that I see the review process working. Also, "toy implementations" (with few, if any, exceptions) have not passed the boost review process either. When something is submitted it is compared to all the alternatives and criticised according to the needs of a wide variety of applications so if it's not complete and very robust it doesn't get accepted. Then there is a huge amount of work including build, test and documentation. Finally, I think that numerical analysis issues such as near singular basis matrices, cycling, accumulated error and periodic re-inversion etc, etc are not issues that can be addressed satisfactorily in a couple of weeks for a library which would hope to reach the level that boost users expect and demand. I would say this is true even if the scope were confined to a simplex method implemenatation. Including mixed integer problems would be a whole 'nother level. To do this right really is a very big job. I should note that many (most) of the GSOC proposals have failed to enter boost because the effort was way underestimated. Of course, if anyone want's to take a shot, go ahead - it's a free country. . Robert Ramey PS "I'd be more than happy to fund the proposal." Where can I line up for some of this? RR
Andrew _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 3/21/2011 1:03 PM, Robert Ramey wrote:
Andrew Sutton wrote:
If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week.
I think you're underestimating the effort required to produce an LP library which would be considered acceptable to boost by two orders of magnitude.
In 3 moths? Absolutely! But I'm not terribly worried about that. If Chad good submits a proposal with reasonable goals, I'd be more than happy to fund the proposal.
Hmmm- two orders of magnitude = 100 so I was saying that that such a job would be 100 weeks. My real point is that to be accepted into boost, a library pretty much has to be demonstrably better than any opensource/openlicense alternative. I'm not making a judgment on this, it's just the way that I see the review process working.
Also, "toy implementations" (with few, if any, exceptions) have not passed the boost review process either. When something is submitted it is compared to all the alternatives and criticised according to the needs of a wide variety of applications so if it's not complete and very robust it doesn't get accepted.
Then there is a huge amount of work including build, test and documentation.
Finally, I think that numerical analysis issues such as near singular basis matrices, cycling, accumulated error and periodic re-inversion etc, etc are not issues that can be addressed satisfactorily in a couple of weeks for a library which would hope to reach the level that boost users expect and demand. I would say this is true even if the scope were confined to a simplex method implemenatation. Including mixed integer problems would be a whole 'nother level. To do this right really is a very big job.
I should note that many (most) of the GSOC proposals have failed to enter boost because the effort was way underestimated.
Of course, if anyone want's to take a shot, go ahead - it's a free country.
I agree with Robert. One of the best GSOC project, IMHO, is the Fusion project by Thomas Heller. As his mentor, I have to say that he has exceeded my expectation by 'ten orders of magnitude' :-) His work went beyond the GSOC time and until now and the future to come, he's totally devoted to the project and has become a full fledged author/maintainer. At the start, I had to make it clear that Thomas should expect more than GSOC's time frame and make him commit further beyond in order to fully satisfy the goals of the project --no less than what's expected of a Boost library in terms of quality. One year after GSOC 2010 and Thomas is still going strong. Bottom line: I think a key to a successful GSOC project is commitment by the student to go beyond the GSOC time frame. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
In 3 moths? Absolutely! But I'm not terribly worried about that. If Chad good submits a proposal with reasonable goals, I'd be more than happy to fund the proposal.
Hmmm- two orders of magnitude = 100 so I was saying that that such a job would be 100 weeks. My real point is that to be accepted into boost, a library pretty much has to be demonstrably better than any opensource/openlicense alternative. I'm not making a judgment on this, it's just the way that I see the review process working.
"Reasonable goals" means that the the proposed work can be finished, to the satisfaction of the student's mentor, over the course of the summer. Students that want to build new libraries for Boost need to realize that it's not a 3 month process. I think that we've been pretty clear about that in the past, and we've also helped students prune down their expectations.
I should note that many (most) of the GSOC proposals have failed to enter boost because the effort was way underestimated.
It's not helpful to measure failure by this yardstick because otherwise we'd be probably looking at a near 100% failure rate for each summer. Long-term (over the course of 2-3 years), that rate may drop to 90%. It's unlikely that these patterns will change in the foreseeable future. Because of that, and because of the fact that only 4 of 5 people suggested projects this year, I'm more than happy to take "toy projects"---as long as there's a mentor willing work with the student. If the student is willing to commit to work beyond the summer time frame, then I would consider that a success.
PS "I'd be more than happy to fund the proposal."
Where can I line up for some of this?
You have to be at least 18 years of age, have been registered as a full-time student over the past year, and submit (and have accepted) a proposal to a mentoring organization. Funding is provided by Google, but assigned by the mentoring organization. Andrew
participants (9)
-
Andrew Sutton -
Chad Seibert -
Eric J. Holtman -
Hartmut Kaiser -
Jeremy Maitin-Shepard -
Joel de Guzman -
Mathias Gaunard -
Robert Ramey -
Vicente Botet