[Cbc] Cbc Digest, Vol 55, Issue 3

[Lou Hafer]

John,

> To be specific: I am implementing an algorithm, part of which needs to solve 
> an sequence of expanding systems of linear inequalities. As the algorithm 
> progresses, I have different choices for which direction to take, so I have to 
> expand the system tentatively with a set of inequalities, see if that works, & 
> if not, try another one. &c.
> 
> For example, suppose I have the system L={x-y>0,3x-y>0}. First I make sure L 
> has a solution. It does, so then I have to choose between the union of L and 
> {x-z>0}, and the union of L and {z-x>0}. This requires me to copy L to two 
> different systems, add the constraints, see if I can solve the new systems, 
> choose the more preferable system if they both have solutions, etc.

	What you're describing here sounds like a branch-and-cut algorithm,
which is what any modern MIP solver implements. With perhaps a greedy
flavour. (Do you revisit each choice of `more preferable system', or
make the choice and move on, never looking back?) And some specialised
cut generation criteria. (However it is that you come up with x-z > 0, etc.)

	Some options, depending on how much coding you want to do and how much
efficiency you need in your implementation:

  * Use any of the commercial algebraic modelling packages that
    provide a back end interface to Coin solvers. Easy to specify
    your constraint systems, but it'll probably be inconvenient to
    evaluate `preferable system' and generate new constraints.

  * Code up your algorithm (evaluate `preferable system', generate
    cuts) using something like CoinModel or CoinPackedMatrix, plus
    some vectors, to represent the constraint system. Call cbc to
    solve each system independently. (Relatively easy to code,
    horrendously inefficient in execution, but might get you by for
    not too many small problems.)

  * Write a cut generator for cbc. If `preferable system' can be cast
    as a linear objective function, the standard branch-and-cut
    algorithm may do exactly what you want. (If memory serves, there
    will be a few additional tricks required, but the hooks are
    there.)

  * Have a look at BiCePS (https://projects.coin-or.org/CHiPPS), a
    general-purpose branch-cut-price framework which you can adapt
    to your needs. (Inquire on the CHiPPS mailing list.)

If you have someone local (in Math or Business) with a background in
operations research, you might run this by them. They will certainly
recognise the flavour of the algorithm and have suggestions.

						Lou