[Coin-discuss] COIN participation in Google Summer of Code 2008?

[Sebastian Nowozin]

Hello everybody,

every year Google finances the "Summer of Code", an effort to support
contributions by students to open-source projects.  Many open-source
projects take part in this program successfully in the last few years.
 I am wondering if COIN would consider participating, as there are no
bad strings attached and this raises the visibility of the project as
well as supports student developers.  I asked earlier on this mailing
list but unfortunately did not receive any response.

If COIN is interested in taking this opportunity, please somebody from
the project step up and organize a short "mentoring organization"
application.   The applications have to be submitted around the
beginning of March and the projects run from June to August.

The application description:
http://code.google.com/support/bin/answer.py?answer=60303&topic=10727&ctx=sibling
More information are available on the previous year SoC website:
http://code.google.com/soc/2007/


As for possible projects, I am just a user of the COIN OR projects,
but the following additions would be nice and would possibly make nice
Google SoC projects if taken by smart students.  Excuse me if one or
two project ideas sound a little naive, its just from what I would
like to see as user.  I am sure the COIN experts can correct these or
come up with smarter project ideas for students, including maybe their
own students.

===

Cbc, Clp, automatic tuning wrapper application.  In applications where
a large number of parameters can be tuned to optimize performance on
certain problem classes, automatic optimization has become popular.
For example, optimizing over compiler optimization options can be
automated (http://www.coyotegulch.com/products/acovea/), and numeric
calculations can be automatically tuned to exploit the computing
architecture (http://math-atlas.sourceforge.net/).  Cbc and Clp offer
a large number of parameters to tune and while there are sensible
defaults, each problem class might benefit from different choices.
The goal would be to "learn" a set of best parameters given a set of
example problems of one class.  This might be especially useful for
tuning Cbc integer optimization options.

Clp, implementation of the self-dual interior point method.  For the
usual Mehrotra-style primal-dual interior point methods for linear
programming a feasible interior point has to be chosen by a heuristic.
 This heuristic can lead to bad starting points which in turn lead to
numerical problems or slow convergence.  For the self-dual interior
point method an extended version of the linear program is created for
which a trivial interior point is known.  (Reference: Bertsimas,
"Introduction to Linear Optimization")

Clp, network simplex implementation.  Linear network simplex and
possibly convex network optimization.  As Clp already supports network
matrices according to the FAQ, this would make a very nice and useful
addition.  Optionally a preprocessor could detect network problems and
automatically switch to the network simplex method if possible.
(Reference: Bertsekas, "Network Optimization")

IpOpt, interface to a CPL-compatible robust linear system solver,
inclusion into the distribution.  IpOpt is an excellent solver is a
robust linear system solver is available, such as the Harwell
Subroutine Library MA57 or PARDISO solvers, which come under their own
restrictive licenses.  With liberally licensed solvers such as MUMPS
the stability of IpOpt suffers greatly.  The goal of this project
would be to survey alternatives compatible with the CPL license and
interface a suitable candidate with IpOpt.  It involves developing
testcases to excercise robustness versus the currently available
solvers (MA27, PARDISO, MUMPS).

"CMPL", COIN-OR Mathematical Programming Language.  AMPL and GNU
Mathprog can be used with the COIN-OR solvers.  For AMPL the AMPL
library is used to read in .nl files produced by the proprietary AMPL
binary; for GNU Mathprog, the user has to compile a solver binary
including the GLPK library which is licensed under the GNU GPL.  This
is unsatisfactory in the long term for two reasons, first, the GNU GPL
is incompatible with the CPL and hence there can never be official
binaries distributed by COIN-OR which include support for GNU
MathProg.  Second, while COIN OR has a large number of high quality
solvers, a high level modelling layer is missing.  This project would
provide a sensible starting point, either interfacing to COIN Osi or
to COIN OS.  Interfacing to the latter would allow extension to
nonlinear problems later on.  Reimplementing the technically
well-documented GNU Mathprog language for COIN would provide a great
first step.

OBOE, interfaces to other languages.  The OBOE solver has a minimal
interface over which all relevant information about the optimization
problem is transmitted.  Interfacing OBOE to other languages (Python,
Matlab/Octave, Java) will allow easier adoption.  Possibly, multiple
languages can be wrapped at once with SWIG.  The project would need to
contain ported examples into the wrapped language and testcases and
documentation.

Modelling classes.  In Operations Research a few standard models occur
again and again, and a clean C++ library of such models could be
built.  For example a library of planning problems (for example from
"Production Planning with Mixed Integer Programming" by Pochet and
Wolsey) could be implemented and thoroughly tested.

===


Thanks for considering,
Sebastian