Re: [boost] A possible GSOC 2011 proposal idea

Subject: Re: [boost] A possible GSOC 2011 proposal idea
From: Hartmut Kaiser (hartmut.kaiser_at_[hidden])
Date: 2011-03-20 11:52:48

> 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