[boost] A possible GSOC 2011 proposal idea

Subject: [boost] A possible GSOC 2011 proposal idea
From: Chad Seibert (chadjseibert_at_[hidden])
Date: 2011-03-20 08:17:32

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