Subject: Re: [boost] A possible GSOC 2011 proposal idea
From: Robert Ramey (ramey_at_[hidden])
Date: 2011-03-20 16:09:04
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