[Coin-discuss] improving the performance of adding constraints via OSI

[John J Forrest]

Kish,

If you can create a C++ driver which encapsulates the timing problem and
which you are fairly sure that if I make that driver go faster then your
code will go faster, then I am happy to look at the problem and hopefully
fix it.

CoinBuild was designed for lightweight addition.

I don't quite understand your example code as it seems to be adding columns
not constraints.

John


                                                                                                                           
  From:       Kish Shen <kish.shen at crosscoreop.com>                                                                        
                                                                                                                           
  To:         coin-discuss at list.coin-or.org                                                                                
                                                                                                                           
  Date:       05/26/2008 11:43 PM                                                                                          
                                                                                                                           
  Subject:    [Coin-discuss] improving the performance of adding constraints via      OSI                                  
                                                                                                                           





Hi,

I have been having this performance issue with adding constraints to a
problem, which I would
like to solve now.

My use of OSI is to provide an interface to the constraint logic
programming language ECLiPSe.
The user can create and modify a problem in many ways, in particular, the
user can add
constraints incrementally to a problem, and repeatedly solve a problem.
Unfortunately,  I
am unable to make this incremental adding of constraints efficient via OSI
-- the cost
increase quite rapidly with the number of constraints, while doing the same
thing with CPLEX
is much more efficient. Here are the results of a simple test I did with
adding the same
constraint repeatedly to a problem, and here are the timings for doing this
on CPLEX (10.1)
and CLP/CBC on the same machine:

                 CPLEX          CLP/CBC
  1000            0.06                   0.23
 10000           0.30                   4.06
 20000           0.67                  14.61

In my code, I add constraints vua OSI as follows:

    CoinBuild build;

    for (int i=0; i<coladded; i++)
    {
             build.addColumn(matbeg[i+1]-matbeg[i],
                                     &(matind[matbeg[i]]),
                                     &(matval[matbeg[i]]),
                                     bdl[i], bdu[i], objx[i]);
    }

    static_cast<OsiSolverInterface* >(lp->Solver)->addCols(build);

This code should be reasonably efficient if many constraints are added at
the same time, but in
my test case above, the constraints are added one by one (i.e. coladded =
1, and this code is
called each time a constraint is added). Added the constraints one by one
is often the most
convenient  for the user, so I would like to be able to make this
efficient.

As I am providing an interface myself, I would like the code to be
efficient for different cases:
the user can repeatedly modify and resolve the problem. Between each solve,
the user can add
only a few, or many constraints to the problem -- it is important that all
these cases are
efficient. It will also be very important to retain any warm start
information between the solves.

I had a brief discussion with John Forrest about this problem last week,
and he suggested
that I should retain the problem external to the solver (which I guess
means in the CoinBuild
matrix in my case), and only pass the problem to the solver when the
problem is to be solved.
Ideally I would like to be able to do this via OSI, because I would like my
code to work with
different solvers. It seems that the only way I can do this is to load the
problem afresh (via
loadProblem() or assignProblem()), but is this efficient for the case when
the problem is only
slightly modified, and how do I retain the warm start information in this
case?

If it is not possible to do this effectively with OSI, I am willing to
write special code to make it
efficient for CLP/CBC, which is the main linear solver I am interface to.

Thanks in advance for any information and help!

Yours sincerely,

Kish


_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss