source/solver/solver.cxx

/**************************************************************
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/


#include <CoinMP.h>

#include "solver.hxx"
#include "solver.hrc"

#include <com/sun/star/beans/XPropertySet.hpp>
#include <com/sun/star/container/XIndexAccess.hpp>
#include <com/sun/star/frame/XModel.hpp>
#include <com/sun/star/lang/XMultiServiceFactory.hpp>
#include <com/sun/star/sheet/XSpreadsheetDocument.hpp>
#include <com/sun/star/sheet/XSpreadsheet.hpp>
#include <com/sun/star/table/CellAddress.hpp>
#include <com/sun/star/table/CellRangeAddress.hpp>
#include <com/sun/star/text/XTextRange.hpp>

#include <rtl/math.hxx>
#include <rtl/ustrbuf.hxx>
#include <cppuhelper/factory.hxx>
#include <vector>
#include <hash_map>
#include <unordered_map>
#include <string>

#include <tools/resmgr.hxx>

using namespace com::sun::star;

using ::rtl::OUString;

#define C2U(constAsciiStr) (::rtl::OUString( RTL_CONSTASCII_USTRINGPARAM( constAsciiStr ) ))

#define STR_NONNEGATIVE   "NonNegative"
#define STR_INTEGER       "Integer"
#define STR_TIMEOUT       "Timeout"
#define STR_EPSILONLEVEL  "EpsilonLevel"
#define STR_LIMITBBDEPTH  "LimitBBDepth"
#define STR_NONLINEARTEST "NonLinearTest"

// -----------------------------------------------------------------------
//  Resources from tools are used for translated strings

static ResMgr* pSolverResMgr = NULL;

OUString lcl_GetResourceString( sal_uInt32 nId )
{
    if (!pSolverResMgr)
        pSolverResMgr = CREATEVERSIONRESMGR( solver );

    return String( ResId( nId, *pSolverResMgr ) );
}

// -----------------------------------------------------------------------

namespace
{
    enum
    {
        PROP_NONNEGATIVE,
        PROP_INTEGER,
        PROP_TIMEOUT,
        PROP_EPSILONLEVEL,
        PROP_LIMITBBDEPTH,
        PROP_NONLINEARTEST
    };
}

// -----------------------------------------------------------------------

// hash map for the coefficients of a dependent cell (objective or constraint)
// The size of each vector is the number of columns (variable cells) plus one, first entry is initial value.

struct ScSolverCellHash
{
    size_t operator()( const table::CellAddress& rAddress ) const
    {
        return ( rAddress.Sheet << 24 ) | ( rAddress.Column << 16 ) | rAddress.Row;
    }
};

inline bool AddressEqual( const table::CellAddress& rAddr1, const table::CellAddress& rAddr2 )
{
    return rAddr1.Sheet == rAddr2.Sheet && rAddr1.Column == rAddr2.Column && rAddr1.Row == rAddr2.Row;
}

struct ScSolverCellEqual
{
    bool operator()( const table::CellAddress& rAddr1, const table::CellAddress& rAddr2 ) const
    {
        return AddressEqual( rAddr1, rAddr2 );
    }
};

typedef std::hash_map< table::CellAddress, std::vector<double>, ScSolverCellHash, ScSolverCellEqual > ScSolverCellHashMap;

// -----------------------------------------------------------------------

uno::Reference<table::XCell> lcl_GetCell( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc,
                                          const table::CellAddress& rPos )
{
    uno::Reference<container::XIndexAccess> xSheets( xDoc->getSheets(), uno::UNO_QUERY );
    uno::Reference<sheet::XSpreadsheet> xSheet( xSheets->getByIndex( rPos.Sheet ), uno::UNO_QUERY );
    return xSheet->getCellByPosition( rPos.Column, rPos.Row );
}

void lcl_SetValue( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc,
                   const table::CellAddress& rPos, double fValue )
{
    lcl_GetCell( xDoc, rPos )->setValue( fValue );
}

double lcl_GetValue( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc,
                     const table::CellAddress& rPos )
{
    return lcl_GetCell( xDoc, rPos )->getValue();
}

// -------------------------------------------------------------------------

SolverComponent::SolverComponent( const uno::Reference<uno::XComponentContext>& /* rSMgr */ ) :
    OPropertyContainer( GetBroadcastHelper() ),
    mbMaximize( sal_True ),
    mbNonNegative( sal_False ),
    mbInteger( sal_False ),
    mnTimeout( 120 ),
    mnEpsilonLevel( 0 ),
    mbLimitBBDepth( sal_True ),
    mbNonLinearTest( sal_True ),
    mbSuccess( sal_False ),
    mfResultValue( 0.0 )
{
    // for XPropertySet implementation:
    registerProperty( C2U(STR_NONNEGATIVE),  PROP_NONNEGATIVE,  0, &mbNonNegative,  getCppuType( &mbNonNegative )  );
    registerProperty( C2U(STR_INTEGER),      PROP_INTEGER,      0, &mbInteger,      getCppuType( &mbInteger )      );
    registerProperty( C2U(STR_TIMEOUT),      PROP_TIMEOUT,      0, &mnTimeout,      getCppuType( &mnTimeout )      );
    registerProperty( C2U(STR_EPSILONLEVEL), PROP_EPSILONLEVEL, 0, &mnEpsilonLevel, getCppuType( &mnEpsilonLevel ) );
    registerProperty( C2U(STR_LIMITBBDEPTH), PROP_LIMITBBDEPTH, 0, &mbLimitBBDepth, getCppuType( &mbLimitBBDepth ) );
    registerProperty( C2U(STR_NONLINEARTEST), PROP_NONLINEARTEST, 0, &mbNonLinearTest, getCppuType( &mbNonLinearTest ) );
}

SolverComponent::~SolverComponent()
{
}

IMPLEMENT_FORWARD_XINTERFACE2( SolverComponent, SolverComponent_Base, OPropertyContainer )
IMPLEMENT_FORWARD_XTYPEPROVIDER2( SolverComponent, SolverComponent_Base, OPropertyContainer )

cppu::IPropertyArrayHelper* SolverComponent::createArrayHelper() const
{
    uno::Sequence<beans::Property> aProps;
    describeProperties( aProps );
    return new cppu::OPropertyArrayHelper( aProps );
}

cppu::IPropertyArrayHelper& SAL_CALL SolverComponent::getInfoHelper()
{
    return *getArrayHelper();
}

uno::Reference<beans::XPropertySetInfo> SAL_CALL SolverComponent::getPropertySetInfo()
{
    return createPropertySetInfo( getInfoHelper() );
}

// XSolverDescription

OUString SAL_CALL SolverComponent::getComponentDescription()
{
    return lcl_GetResourceString( RID_SOLVER_COMPONENT );
}

OUString SAL_CALL SolverComponent::getStatusDescription()
{
    return maStatus;
}

OUString SAL_CALL SolverComponent::getPropertyDescription( const OUString& rPropertyName )
{
    sal_uInt32 nResId = 0;
    sal_Int32 nHandle = getInfoHelper().getHandleByName( rPropertyName );
    switch (nHandle)
    {
        case PROP_NONNEGATIVE:
            nResId = RID_PROPERTY_NONNEGATIVE;
            break;
        case PROP_INTEGER:
            nResId = RID_PROPERTY_INTEGER;
            break;
        case PROP_TIMEOUT:
            nResId = RID_PROPERTY_TIMEOUT;
            break;
        case PROP_EPSILONLEVEL:
            nResId = RID_PROPERTY_EPSILONLEVEL;
            break;
        case PROP_LIMITBBDEPTH:
            nResId = RID_PROPERTY_LIMITBBDEPTH;
            break;
        case PROP_NONLINEARTEST:
            nResId = RID_PROPERTY_NONLINEARTEST;
            break;
        default:
            {
                // unknown - leave empty
            }
    }
    OUString aRet;
    if ( nResId )
        aRet = lcl_GetResourceString( nResId );
    return aRet;
}

// XSolver: settings

uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL SolverComponent::getDocument()
{
    return mxDoc;
}

void SAL_CALL SolverComponent::setDocument( const uno::Reference<sheet::XSpreadsheetDocument>& _document )
{
    mxDoc = _document;
}

table::CellAddress SAL_CALL SolverComponent::getObjective()
{
    return maObjective;
}

void SAL_CALL SolverComponent::setObjective( const table::CellAddress& _objective )
{
    maObjective = _objective;
}

uno::Sequence<table::CellAddress> SAL_CALL SolverComponent::getVariables()
{
    return maVariables;
}

void SAL_CALL SolverComponent::setVariables( const uno::Sequence<table::CellAddress>& _variables )
{
    maVariables = _variables;
}

uno::Sequence<sheet::SolverConstraint> SAL_CALL SolverComponent::getConstraints()
{
    return maConstraints;
}

void SAL_CALL SolverComponent::setConstraints( const uno::Sequence<sheet::SolverConstraint>& _constraints )
{
    maConstraints = _constraints;
}

sal_Bool SAL_CALL SolverComponent::getMaximize()
{
    return mbMaximize;
}

void SAL_CALL SolverComponent::setMaximize( sal_Bool _maximize )
{
    mbMaximize = _maximize;
}

// XSolver: get results

sal_Bool SAL_CALL SolverComponent::getSuccess()
{
    return mbSuccess;
}

double SAL_CALL SolverComponent::getResultValue()
{
    return mfResultValue;
}

uno::Sequence<double> SAL_CALL SolverComponent::getSolution()
{
    return maSolution;
}

// -------------------------------------------------------------------------

void SAL_CALL SolverComponent::solve()
{
    uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY );
    if ( !xModel.is() )
        throw uno::RuntimeException();

    maStatus = OUString();
    mbSuccess = false;

    xModel->lockControllers();

    // collect variables in vector (?)

    std::vector<table::CellAddress> aVariableCells;
    for (sal_Int32 nPos=0; nPos<maVariables.getLength(); nPos++)
        aVariableCells.push_back( maVariables[nPos] );
    size_t nVariables = aVariableCells.size();
    size_t nVar = 0;

    // collect all dependent cells

    ScSolverCellHashMap aCellsHash;
    aCellsHash[maObjective].reserve( nVariables + 1 );                  // objective function

    for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
    {
        table::CellAddress aCellAddr = maConstraints[nConstrPos].Left;
        aCellsHash[aCellAddr].reserve( nVariables + 1 );                // constraints: left hand side

        if ( maConstraints[nConstrPos].Right >>= aCellAddr )
            aCellsHash[aCellAddr].reserve( nVariables + 1 );            // constraints: right hand side
    }

    // Save the current values of the changing cells for use as a possible
    // initial solution, then reset the cells to zero for model construction.
    std::vector<double> aInitValues(nVariables);
    for (nVar = 0; nVar < nVariables; ++nVar)
    {
        // read current value of the variable cell and store as initial value
        aInitValues[nVar] = lcl_GetValue( mxDoc, aVariableCells[nVar] );
        lcl_SetValue( mxDoc, aVariableCells[nVar], 0.0 );
    }
    std::vector<table::CellAddress>::const_iterator aVarIter;

    // read initial values from all dependent cells
    ScSolverCellHashMap::iterator aCellsIter;
    for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
    {
        double fValue = lcl_GetValue( mxDoc, aCellsIter->first );
        aCellsIter->second.push_back( fValue );                         // store as first element, as-is
    }

    // loop through variables
    for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
    {
        lcl_SetValue( mxDoc, *aVarIter, 1.0 );      // set to 1 to examine influence

        // read value change from all dependent cells
        for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
        {
            double fChanged = lcl_GetValue( mxDoc, aCellsIter->first );
            double fInitial = aCellsIter->second.front();
            aCellsIter->second.push_back( fChanged - fInitial );
        }

        lcl_SetValue( mxDoc, *aVarIter, 2.0 );      // minimal test for linearity

        for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
        {
            double fInitial = aCellsIter->second.front();
            double fCoeff   = aCellsIter->second.back();       // last appended: coefficient for this variable
            double fTwo     = lcl_GetValue( mxDoc, aCellsIter->first );

          if ( mbNonLinearTest )
          {
              bool bLinear ( sal_True );
              bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
              rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
            // second comparison is needed in case fTwo is zero
              if ( !bLinear )
                  maStatus = lcl_GetResourceString( RID_ERROR_NONLINEAR );
           }
        }

        lcl_SetValue( mxDoc, *aVarIter, 0.0 );      // set back to zero for examining next variable
    }

    xModel->unlockControllers();

    if ( maStatus.getLength() )
        return;

    //
    // build parameter arrays for CoinMP
    //

    // set objective function

    const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
    double* pObjectCoeffs = new double[nVariables];
    for (nVar=0; nVar<nVariables; nVar++)
        pObjectCoeffs[nVar] = rObjCoeff[nVar+1];
    double nObjectConst = rObjCoeff[0];             // constant term of objective

    // add rows

    size_t nRows = maConstraints.getLength();
    size_t nCompSize = nVariables * nRows;
    double* pCompMatrix = new double[nCompSize];    // first collect all coefficients, row-wise
    for (size_t i=0; i<nCompSize; i++)
        pCompMatrix[i] = 0.0;

    double* pRHS = new double[nRows];
    char* pRowType = new char[nRows];
    for (size_t i=0; i<nRows; i++)
    {
        pRHS[i] = 0.0;
        pRowType[i] = 'N';
    }

    for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
    {
        // integer constraints are set later
        sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
        if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
             eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
             eOp == sheet::SolverConstraintOperator_EQUAL )
        {
            double fDirectValue = 0.0;
            bool bRightCell = false;
            table::CellAddress aRightAddr;
            const uno::Any& rRightAny = maConstraints[nConstrPos].Right;
            if ( rRightAny >>= aRightAddr )
                bRightCell = true;                  // cell specified as right-hand side
            else
                rRightAny >>= fDirectValue;         // constant value

            table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;

            const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
            double* pValues = &pCompMatrix[nConstrPos * nVariables];
            for (nVar=0; nVar<nVariables; nVar++)
                pValues[nVar] = rLeftCoeff[nVar+1];

            // if left hand cell has a constant term, put into rhs value
            double fRightValue = -rLeftCoeff[0];

            if ( bRightCell )
            {
                const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
                // modify pValues with rhs coefficients
                for (nVar=0; nVar<nVariables; nVar++)
                    pValues[nVar] -= rRightCoeff[nVar+1];

                fRightValue += rRightCoeff[0];      // constant term
            }
            else
                fRightValue += fDirectValue;

            switch ( eOp )
            {
                case sheet::SolverConstraintOperator_LESS_EQUAL:    pRowType[nConstrPos] = 'L'; break;
                case sheet::SolverConstraintOperator_GREATER_EQUAL: pRowType[nConstrPos] = 'G'; break;
                case sheet::SolverConstraintOperator_EQUAL:         pRowType[nConstrPos] = 'E'; break;
                default:
                    OSL_ENSURE( false, "unexpected enum type" );
            }
            pRHS[nConstrPos] = fRightValue;
        }
    }

    // Try to combine complementary <= and >= rows with identical coefficients
    // into a single ranged row 'R' with RANGE = upper - lower.
    // We do this before building the column-wise matrix. When a pair is
    // merged we zero out the coefficients of the removed row so it is
    // ignored when building the sparse column representation.
    // Allocate a row-indexed range array up-front (one entry per original row).
    double* pRangeValues = new double[nRows];
    for (size_t i = 0; i < nRows; ++i) pRangeValues[i] = 0.0;

    // Two-pass approach: first collect best lower/upper per coefficient
    // signature (exact bitwise signature). Second, convert compatibles to
    // ranged rows. This avoids online erase/replace semantics and ensures
    // decisions are based on the original model.
    struct RowPair { size_t lowerIdx; double lowerVal; size_t upperIdx; double upperVal; };
    const size_t npos = static_cast<size_t>(-1);
    std::unordered_map< std::string, RowPair > rowMap;
    rowMap.reserve(nRows * 2);

    // Pass 1: populate rowMap with tightest lower (max G) and tightest
    // upper (min L) for each coefficient signature.
    for (size_t i = 0; i < nRows; ++i)
    {
        char ti = pRowType[i];
        if ( ti != 'L' && ti != 'G' )
            continue;

        const char* data = reinterpret_cast<const char*>(&pCompMatrix[i * nVariables]);
        size_t len = (size_t)nVariables * sizeof(double);
        std::string sig;
        sig.assign(data, len);

        auto it = rowMap.find(sig);
        if ( it == rowMap.end() )
        {
            RowPair rp; rp.lowerIdx = npos; rp.upperIdx = npos; rp.lowerVal = 0.0; rp.upperVal = 0.0;
            std::pair<std::unordered_map<std::string, RowPair>::iterator, bool> res = rowMap.insert(std::make_pair(sig, rp));
            it = res.first;
        }

        RowPair &rp = it->second;
        if ( ti == 'L' )
        {
            double v = pRHS[i];
            if ( rp.upperIdx == npos || v < rp.upperVal )
            {
                rp.upperIdx = i;
                rp.upperVal = v;
            }
        }
        else // 'G'
        {
            double v = pRHS[i];
            if ( rp.lowerIdx == npos || v > rp.lowerVal )
            {
                rp.lowerIdx = i;
                rp.lowerVal = v;
            }
        }
    }

    // Pass 2: perform conversions for entries that have both bounds.
    size_t nMergedRows = 0;
    for (auto &kv : rowMap)
    {
        RowPair &rp = kv.second;
        if ( rp.lowerIdx == npos || rp.upperIdx == npos )
            continue;

        size_t idxLower = rp.lowerIdx;
        size_t idxUpper = rp.upperIdx;
        double lower = rp.lowerVal;
        double upper = rp.upperVal;

        if ( lower <= upper )
        {
            // make upper the ranged row and mark lower as removed
            pRowType[idxUpper] = 'R';
            pRHS[idxUpper] = upper;
            pRangeValues[idxUpper] = upper - lower;

            pRowType[idxLower] = 'N';
            pRHS[idxLower] = 0.0;

            ++nMergedRows;
            OSL_TRACE("Solver: merging rows %lu (G %.17g) and %lu (L %.17g) into ranged row %lu [%.17g, %.17g]\n",
                      static_cast<unsigned long>(idxLower), lower,
                      static_cast<unsigned long>(idxUpper), upper,
                      static_cast<unsigned long>(idxUpper), lower, upper);
        }
        else
        {
            // invalid (contradictory) bounds: leave rows unchanged
            OSL_TRACE("Solver: contradictory bounds for coeff-signature - lowerRow=%lu (%.17g) upperRow=%lu (%.17g); leaving rows unchanged\n",
                      static_cast<unsigned long>(idxLower), lower,
                      static_cast<unsigned long>(idxUpper), upper);
        }
    }

    // After Pass 2 produce a summary trace (rows merged, ranged rows created,
    // rows eliminated). This is the default diagnostic; per-row traces are
    // emitted above and can be enabled/disabled by adjusting trace levels.
    int nRangeCount_tmp = 0;
    int nEliminated = 0;
    for (size_t i = 0; i < nRows; ++i)
    {
        if ( pRowType[i] == 'R' ) ++nRangeCount_tmp;
        if ( pRowType[i] == 'N' ) ++nEliminated;
    }
    OSL_TRACE("Solver: %lu input rows, %d ranged rows created, %d rows eliminated, %lu merged pairs\n",
              static_cast<unsigned long>(nRows), nRangeCount_tmp, nEliminated, static_cast<unsigned long>(nMergedRows));

    // Find non-zero coefficients, column-wise

    int* pMatrixBegin = new int[nVariables+1];
    int* pMatrixCount = new int[nVariables];
    double* pMatrix = new double[nCompSize];    // not always completely used
    int* pMatrixIndex = new int[nCompSize];
    int nMatrixPos = 0;
    for (nVar=0; nVar<nVariables; nVar++)
    {
        int nBegin = nMatrixPos;
        for (size_t nRow=0; nRow<nRows; nRow++)
        {
            if ( pRowType[nRow] == 'N' )
                continue;
            double fCoeff = pCompMatrix[ nRow * nVariables + nVar ];    // row-wise
            if ( fCoeff != 0.0 )
            {
                pMatrix[nMatrixPos] = fCoeff;
                pMatrixIndex[nMatrixPos] = nRow;
                ++nMatrixPos;
            }
        }
        pMatrixBegin[nVar] = nBegin;
        pMatrixCount[nVar] = nMatrixPos - nBegin;
    }
    pMatrixBegin[nVariables] = nMatrixPos;
    delete[] pCompMatrix;
    pCompMatrix = NULL;

    // Count ranged rows and keep the row-indexed pRangeValues allocated above.
    int nRangeCount = 0;
    for (size_t i = 0; i < nRows; ++i)
        if ( pRowType[i] == 'R' )
            ++nRangeCount;

    // apply settings to all variables

    double* pLowerBounds = new double[nVariables];
    double* pUpperBounds = new double[nVariables];
    for (nVar=0; nVar<nVariables; nVar++)
    {
        pLowerBounds[nVar] = mbNonNegative ? 0.0 : -DBL_MAX;
        pUpperBounds[nVar] = DBL_MAX;

        // bounds could possibly be further restricted from single-cell constraints
    }

    char* pColType = new char[nVariables];
    for (nVar=0; nVar<nVariables; nVar++)
        pColType[nVar] = mbInteger ? 'I' : 'C';

    // apply single-var integer constraints

    for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
    {
        sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
        if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
             eOp == sheet::SolverConstraintOperator_BINARY )
        {
            table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
            // find variable index for cell
            for (nVar=0; nVar<nVariables; nVar++)
                if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
                {
                    if ( eOp == sheet::SolverConstraintOperator_INTEGER )
                        pColType[nVar] = 'I';
                    else
                    {
                        pColType[nVar] = 'B';
                        pLowerBounds[nVar] = 0.0;
                        pUpperBounds[nVar] = 1.0;
                    }
                }
        }
    }

    int nObjectSense = mbMaximize ? SOLV_OBJSENS_MAX : SOLV_OBJSENS_MIN;

    HPROB hProb = CoinCreateProblem("");
    int nResult = CoinLoadProblem( hProb, nVariables, nRows, nMatrixPos, nRangeCount,
                    nObjectSense, nObjectConst, pObjectCoeffs,
                    pLowerBounds, pUpperBounds, pRowType, pRHS, pRangeValues,
                    pMatrixBegin, pMatrixCount, pMatrixIndex, pMatrix,
                    NULL, NULL, NULL );
    if ( nResult == SOLV_CALL_SUCCESS )
        nResult = CoinLoadInteger( hProb, pColType );

    if ( pRangeValues )
    {
        delete[] pRangeValues;
        pRangeValues = NULL;
    }

    // Supply the current variable values as a possible initial solution.
    // Pass the spreadsheet values unchanged; CoinMP/CBC is responsible for
    // validating the supplied initial solution.
    if ( nResult == SOLV_CALL_SUCCESS && !aInitValues.empty() )
    {
        int nLoadRc = CoinLoadInitValues( hProb, aInitValues.data() );
        if ( nLoadRc != SOLV_CALL_SUCCESS )
        {
            // Non-fatal: initial values are an optimization hint only; proceed without them.
            OSL_TRACE("CoinLoadInitValues failed: %d\n", nLoadRc);
        }
    }

    delete[] pColType;
    delete[] pMatrixIndex;
    delete[] pMatrix;
    delete[] pMatrixCount;
    delete[] pMatrixBegin;
    delete[] pUpperBounds;
    delete[] pLowerBounds;
    delete[] pRowType;
    delete[] pRHS;
    delete[] pObjectCoeffs;

    CoinSetRealOption( hProb, COIN_REAL_MAXSECONDS, mnTimeout );
    CoinSetRealOption( hProb, COIN_REAL_MIPMAXSEC, mnTimeout );

    // TODO: handle (or remove) settings: epsilon, B&B depth

    // solve model

    nResult = CoinCheckProblem( hProb );
    if (nResult != SOLV_CALL_SUCCESS)
    {
        // report invalid model

       maStatus = lcl_GetResourceString( RID_ERROR_INVALIDMODEL );
        CoinUnloadProblem(hProb);
        return;
    }
    nResult = CoinOptimizeProblem( hProb, 0 );

    mbSuccess = ( nResult == SOLV_CALL_SUCCESS );
    if ( mbSuccess )
    {
        // get solution

        maSolution.realloc( nVariables );
        CoinGetSolutionValues( hProb, maSolution.getArray(), NULL, NULL, NULL );
        mfResultValue = CoinGetObjectValue( hProb );
    }
    else
    {
        int nSolutionStatus = CoinGetSolutionStatus( hProb );
        if ( nSolutionStatus == 1 )
            maStatus = lcl_GetResourceString( RID_ERROR_INFEASIBLE );
        else if ( nSolutionStatus == 2 )
            maStatus = lcl_GetResourceString( RID_ERROR_UNBOUNDED );
    else if ( nSolutionStatus == 3 )
            maStatus = lcl_GetResourceString(  RID_ERROR_ITERATIONLIMIT );
    else if ( nSolutionStatus == 4 )
            maStatus = lcl_GetResourceString( RID_ERROR_SOLVERERROR );
        else if ( nSolutionStatus == 5 )
            maStatus = lcl_GetResourceString( RID_ERROR_USERSTOP );
    else if ( nSolutionStatus >= 6 )
            maStatus = lcl_GetResourceString( RID_ERROR_UNKNOWN );

    }

    CoinUnloadProblem( hProb );
}

// -------------------------------------------------------------------------

// XServiceInfo

uno::Sequence< OUString > SolverComponent_getSupportedServiceNames()
{
    uno::Sequence< OUString > aServiceNames( 1 );
    aServiceNames[ 0 ] = OUString::createFromAscii( "com.sun.star.sheet.Solver" );
    return aServiceNames;
}

OUString SolverComponent_getImplementationName()
{
    return OUString::createFromAscii( "com.sun.star.comp.Calc.Solver" );
}

OUString SAL_CALL SolverComponent::getImplementationName()
{
    return SolverComponent_getImplementationName();
}

sal_Bool SAL_CALL SolverComponent::supportsService( const OUString& rServiceName )
{
    const uno::Sequence< OUString > aServices = SolverComponent_getSupportedServiceNames();
    const OUString* pArray = aServices.getConstArray();
    const OUString* pArrayEnd = pArray + aServices.getLength();
    return ::std::find( pArray, pArrayEnd, rServiceName ) != pArrayEnd;
}

uno::Sequence<OUString> SAL_CALL SolverComponent::getSupportedServiceNames()
{
    return SolverComponent_getSupportedServiceNames();
}

uno::Reference<uno::XInterface> SolverComponent_createInstance( const uno::Reference<uno::XComponentContext>& rSMgr )
{
    return (cppu::OWeakObject*) new SolverComponent( rSMgr );
}

// -------------------------------------------------------------------------

extern "C"
{
    SAL_DLLPUBLIC_EXPORT void SAL_CALL component_getImplementationEnvironment(
        const sal_Char ** ppEnvTypeName, uno_Environment ** )
    {
        *ppEnvTypeName = CPPU_CURRENT_LANGUAGE_BINDING_NAME;
    }

    // -------------------------------------------------------------------------

    SAL_DLLPUBLIC_EXPORT void* SAL_CALL component_getFactory( const sal_Char * pImplName, void * pServiceManager, void * /*pRegistryKey*/ )
    {
        OUString    aImplName( OUString::createFromAscii( pImplName ) );
        void*       pRet = 0;

        if( pServiceManager )
        {
            uno::Reference< lang::XSingleComponentFactory > xFactory;
            if( aImplName.equals( SolverComponent_getImplementationName() ) )
                xFactory = cppu::createSingleComponentFactory(
                        SolverComponent_createInstance,
                        OUString::createFromAscii( pImplName ),
                        SolverComponent_getSupportedServiceNames() );

            if( xFactory.is() )
            {
                xFactory->acquire();
                pRet = xFactory.get();
            }
        }
        return pRet;
    }
}