[Cbc] CBC 2.9 vs. 2.8, presolving

[Christoph Cullmann]

Hi,

using the example:

http://www.absint.com/dla/lpsolve/value_9041131.lp.gz

and a solver like below that mail, now the presolving no longer
terminates in any reasonable time (e.g. > 20 minutes here instead of seconds with CBC 2.8).

Is this a regression or just some API misuse?

Greetings
Christoph

bool solveLP (const char *infile)
{
    /**
     * liberror message handler
     */
    ClpsolveMessageHandler messageHandler;

    /**
     * load problem from lp file, else die
     */
    Ur::printf (Ur::Progress, "Reading lp file '%s'...", infile);
    OsiClpSolverInterface solver;
    setLpOptions (&solver, messageHandler);
    if (solver.readLp(infile)) {
        Ur::printf (Ur::Error, "Cannot open '%s', CPLEX LP file processing error.", infile);
        return false;
    }
    Ur::printf (Ur::Progress, "Finished reading lp file.");

    /**
     * some stats
     */
    Ur::printf (Ur::Note,
                "Statistics:\n"
                "Number of columns: %d.\n"
                "Number of rows: %d.\n"
                "Number of non-zero elements: %d.\n",
                solver.getNumCols(),
                solver.getNumRows(),
                solver.getNumElements());

    double time1 = CoinCpuTime();
    double time2 = time1;

    /**
     * initial solve parameters
     */
    ClpSolve solvectl;
    // Tell code to return at once if infeasible
    solvectl.setInfeasibleReturn(true);
    // make sure uses dual
    solvectl.setSolveType(ClpSolve::useDual);

    /**
     * fast initial solve
     */
    ClpSimplex *simplex = solver.getModelPtr();

    // deactivate scaling
    simplex->scaling(0);
    solver.setHintParam(OsiDoScale,false,OsiHintDo);

    // Set perturbation on
    simplex->setPerturbation(50);

    if (simplex->initialSolve(solvectl) == -1 || !simplex->isProvenOptimal()) {
        if (simplex->problemStatus()==1)
            handleNoResult (solver, "This problem is infeasible", Ur::MessageNumber::ILPSolving::InfeasibleOrUnboundedProblem);
        else
            handleNoResult (solver, "This problem is unbounded", Ur::MessageNumber::ILPSolving::InfeasibleOrUnboundedProblem);
        return true;
    }

    // make sure basis correct in solver
    solver.setWarmStart(NULL);
    // below not needed - just making sure for now
    solver.initialSolve();
    // Change infeasibility weight if large objective
    if (fabs(simplex->objectiveValue() + simplex->objectiveOffset()) > 1.0e10) {
        simplex->setInfeasibilityCost(1000.0 * simplex->infeasibilityCost());
    }
    // find largest value
    {
        const double *solution = solver.getColSolution();
        int numberColumns = solver.getNumCols();
        double largest = 0.0;
        for (int i = 0; i < numberColumns; i++)
            largest = CoinMax(largest, solution[i]);
        simplex->setDualBound(CoinMin(simplex->dualBound(), 1.01 * largest + 1.0));
    }

    /**
     * Create CglPreProcessor
     */
    CglPreProcess process;
    process.passInMessageHandler (&messageHandler);

    /**
     * do pre process
     */
    OsiSolverInterface *preprocessedSolver = process.preProcess (solver);
    time2 = CoinCpuTime();
    if (!preprocessedSolver) {
        handleNoResult (solver, "This problem is infeasible", Ur::MessageNumber::ILPSolving::InfeasibleOrUnboundedProblem);
        return true;
    }

    /**
     * some stats
     */
    Ur::printf (Ur::Note,
                "Statistics (after preprocessing):\n"
                "Number of columns: %d.\n"
                "Number of rows: %d.\n"
                "Number of non-zero elements: %d.\n",
                preprocessedSolver->getNumCols(),
                preprocessedSolver->getNumRows(),
                preprocessedSolver->getNumElements());

    /**
     * resolve
     */
    setLpOptions (preprocessedSolver, messageHandler);
    preprocessedSolver->resolve();

    /**
     * Cbc model creation
     */
    CbcModel model (*preprocessedSolver);
    model.passInMessageHandler (&messageHandler);

    /**
     * add some defaults
     */
    CbcMain0 (model);

    /**
     * solve
     */
    model.branchAndBound();
    if (model.isProvenOptimal()) {
        // Good
    } else if (model.isProvenInfeasible()) {
        handleNoResult (solver, "This problem is infeasible", Ur::MessageNumber::ILPSolving::InfeasibleOrUnboundedProblem);
        return true;
    } else {
        // some error
        Ur::printf (Ur::Error, "No optimal solution found, solving failed.");
        return false;
    }

    process.postProcess(*model.solver());

    // look at solution
    const double *solution = solver.getColSolution();
    int numberColumns = solver.getNumCols();

    int iColumn;
    // double check
    const double *lower = solver.getColLower();
    const double *upper = solver.getColUpper();
    int numberIntegers = 0;
    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
        double value = floor(solution[iColumn] + 0.5);
        if (solver.isInteger(iColumn)) {
            solver.setColLower(iColumn, CoinMax(value, lower[iColumn]));
            solver.setColUpper(iColumn, CoinMin(value, upper[iColumn]));
            numberIntegers++;
        }
    }
    if (numberIntegers < numberColumns) {
        solver.resolve();
    } else {
        // just setup so will do checks
        solver.getModelPtr()->setProblemStatus(1);
    }
    // Use relaxed criterion
    solver.getModelPtr()->checkUnscaledSolution();
    if (!solver.isProvenOptimal()) {
        // bug
        Ur::printf (Ur::Error, "No optimal solution found, solving failed.");
        return false;
    }

    // objective value
    outputObjectiveValue ((solver.getObjValue () < 0) ? -solver.getObjValue () : solver.getObjValue ());

    /* column values... */
    for (iColumn = 0; iColumn < numberColumns; iColumn++)
        outputColumnValue (iColumn, solver.getColName(iColumn).c_str(), solution[iColumn]);

    // be done
    return true;
}


-- 
----------------------------- Dr.-Ing. Christoph Cullmann ---------
AbsInt Angewandte Informatik GmbH      Email: cullmann at AbsInt.com
Science Park 1                         Tel:   +49-681-38360-22
66123 Saarbrücken                      Fax:   +49-681-38360-20
GERMANY                                WWW:   http://www.AbsInt.com
--------------------------------------------------------------------
Geschäftsführung: Dr.-Ing. Christian Ferdinand
Eingetragen im Handelsregister des Amtsgerichts Saarbrücken, HRB 11234