[Coin-discuss] OSI with Clp, how to use interior-point solver

[Michael Hennebry]

On Tue, 9 Oct 2007, Sebastian Nowozin wrote:
> For a machine learning problem I am currently solving with Osi/Clp it is
> important to obtain a risk-balanced solution if there is a face/set of
> optimal solutions which corresponds to the analytic center of the
> polytope solution face.  The usual Clp simplex solver provides a vertex
> solution and thus is not optimal in this respect.  (One could argue
> about the objective function value not faithfully representing the true
> objective here, but lets say we know the center of the solution face to
> be a good solution.)

You still have the problem of knowing that
the face has more than a single point.
Floating point makes that difficult.

Once you have an optimal solution,
you can decide how much slop is allowed
and use that to generate a constraint.
You can use the reduced costs to decide
which constraints to call degenerate.

Starting with
min cz
s.t.
   Ax >= b
Solve it and then solve
max z
s.t.
    cx <= small_enough
    Ax >= b
    zs <= Ax-b

where s is a nonnegative column vector.
It should be zero in entries corresponding
to nondegenerate constraints.

If the above isn't good enough (it could be degenerate),
you could try solving the following with an interior point solver:
max cx
s.t.
    cx <= small_enough
    Ax >= b

-- 
Mike   hennebry at web.cs.ndsu.NoDak.edu
"Horse guts never lie."  -- Cherek Bear-Shoulders