Re: [boost] A possible GSOC 2011 proposal idea

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