LCOV - code coverage report
Current view: top level - sccomp/source/solver - CoinMPSolver.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 162 0.0 %
Date: 2014-04-14 Functions: 0 7 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include <CoinMP.h>
      21             : 
      22             : #include "SolverComponent.hxx"
      23             : #include "solver.hrc"
      24             : 
      25             : #include <com/sun/star/frame/XModel.hpp>
      26             : #include <com/sun/star/table/CellAddress.hpp>
      27             : #include <com/sun/star/uno/XComponentContext.hpp>
      28             : 
      29             : #include <rtl/math.hxx>
      30             : #include <vector>
      31             : 
      32             : using namespace com::sun::star;
      33             : 
      34             : class CoinMPSolver : public SolverComponent
      35             : {
      36             : public:
      37           0 :     CoinMPSolver() {}
      38           0 :     virtual ~CoinMPSolver() {}
      39             : 
      40             : private:
      41             :     virtual void SAL_CALL solve() throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE;
      42           0 :     virtual OUString SAL_CALL getImplementationName()
      43             :         throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE
      44             :     {
      45           0 :         return OUString("com.sun.star.comp.Calc.CoinMPSolver");
      46             :     }
      47           0 :     virtual OUString SAL_CALL getComponentDescription()
      48             :         throw (uno::RuntimeException, std::exception) SAL_OVERRIDE
      49             :     {
      50           0 :         return SolverComponent::GetResourceString( RID_COINMP_SOLVER_COMPONENT );
      51             :     }
      52             : };
      53             : 
      54           0 : void SAL_CALL CoinMPSolver::solve() throw(uno::RuntimeException, std::exception)
      55             : {
      56           0 :     uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY );
      57           0 :     if ( !xModel.is() )
      58           0 :         throw uno::RuntimeException();
      59             : 
      60           0 :     maStatus = "";
      61           0 :     mbSuccess = false;
      62             : 
      63           0 :     xModel->lockControllers();
      64             : 
      65             :     // collect variables in vector (?)
      66             : 
      67           0 :     std::vector<table::CellAddress> aVariableCells;
      68           0 :     for (sal_Int32 nPos=0; nPos<maVariables.getLength(); nPos++)
      69           0 :         aVariableCells.push_back( maVariables[nPos] );
      70           0 :     size_t nVariables = aVariableCells.size();
      71           0 :     size_t nVar = 0;
      72             : 
      73             :     // collect all dependent cells
      74             : 
      75           0 :     ScSolverCellHashMap aCellsHash;
      76           0 :     aCellsHash[maObjective].reserve( nVariables + 1 );                  // objective function
      77             : 
      78           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
      79             :     {
      80           0 :         table::CellAddress aCellAddr = maConstraints[nConstrPos].Left;
      81           0 :         aCellsHash[aCellAddr].reserve( nVariables + 1 );                // constraints: left hand side
      82             : 
      83           0 :         if ( maConstraints[nConstrPos].Right >>= aCellAddr )
      84           0 :             aCellsHash[aCellAddr].reserve( nVariables + 1 );            // constraints: right hand side
      85             :     }
      86             : 
      87             :     // set all variables to zero
      88             :     //! store old values?
      89             :     //! use old values as initial values?
      90           0 :     std::vector<table::CellAddress>::const_iterator aVarIter;
      91           0 :     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
      92             :     {
      93           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );
      94             :     }
      95             : 
      96             :     // read initial values from all dependent cells
      97           0 :     ScSolverCellHashMap::iterator aCellsIter;
      98           0 :     for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
      99             :     {
     100           0 :         double fValue = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     101           0 :         aCellsIter->second.push_back( fValue );                         // store as first element, as-is
     102             :     }
     103             : 
     104             :     // loop through variables
     105           0 :     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
     106             :     {
     107           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 1.0 );      // set to 1 to examine influence
     108             : 
     109             :         // read value change from all dependent cells
     110           0 :         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
     111             :         {
     112           0 :             double fChanged = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     113           0 :             double fInitial = aCellsIter->second.front();
     114           0 :             aCellsIter->second.push_back( fChanged - fInitial );
     115             :         }
     116             : 
     117           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 2.0 );      // minimal test for linearity
     118             : 
     119           0 :         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
     120             :         {
     121           0 :             double fInitial = aCellsIter->second.front();
     122           0 :             double fCoeff   = aCellsIter->second.back();       // last appended: coefficient for this variable
     123           0 :             double fTwo     = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     124             : 
     125           0 :             bool bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
     126           0 :                            rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
     127             :             // second comparison is needed in case fTwo is zero
     128           0 :             if ( !bLinear )
     129           0 :                 maStatus = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR );
     130             :         }
     131             : 
     132           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );      // set back to zero for examining next variable
     133             :     }
     134             : 
     135           0 :     xModel->unlockControllers();
     136             : 
     137           0 :     if ( !maStatus.isEmpty() )
     138           0 :         return;
     139             : 
     140             :     //
     141             :     // build parameter arrays for CoinMP
     142             :     //
     143             : 
     144             :     // set objective function
     145             : 
     146           0 :     const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
     147           0 :     double* pObjectCoeffs = new double[nVariables];
     148           0 :     for (nVar=0; nVar<nVariables; nVar++)
     149           0 :         pObjectCoeffs[nVar] = rObjCoeff[nVar+1];
     150           0 :     double nObjectConst = rObjCoeff[0];             // constant term of objective
     151             : 
     152             :     // add rows
     153             : 
     154           0 :     size_t nRows = maConstraints.getLength();
     155           0 :     size_t nCompSize = nVariables * nRows;
     156           0 :     double* pCompMatrix = new double[nCompSize];    // first collect all coefficients, row-wise
     157           0 :     for (size_t i=0; i<nCompSize; i++)
     158           0 :         pCompMatrix[i] = 0.0;
     159             : 
     160           0 :     double* pRHS = new double[nRows];
     161           0 :     char* pRowType = new char[nRows];
     162           0 :     for (size_t i=0; i<nRows; i++)
     163             :     {
     164           0 :         pRHS[i] = 0.0;
     165           0 :         pRowType[i] = 'N';
     166             :     }
     167             : 
     168           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
     169             :     {
     170             :         // integer constraints are set later
     171           0 :         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
     172           0 :         if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
     173           0 :              eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
     174             :              eOp == sheet::SolverConstraintOperator_EQUAL )
     175             :         {
     176           0 :             double fDirectValue = 0.0;
     177           0 :             bool bRightCell = false;
     178           0 :             table::CellAddress aRightAddr;
     179           0 :             const uno::Any& rRightAny = maConstraints[nConstrPos].Right;
     180           0 :             if ( rRightAny >>= aRightAddr )
     181           0 :                 bRightCell = true;                  // cell specified as right-hand side
     182             :             else
     183           0 :                 rRightAny >>= fDirectValue;         // constant value
     184             : 
     185           0 :             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
     186             : 
     187           0 :             const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
     188           0 :             double* pValues = &pCompMatrix[nConstrPos * nVariables];
     189           0 :             for (nVar=0; nVar<nVariables; nVar++)
     190           0 :                 pValues[nVar] = rLeftCoeff[nVar+1];
     191             : 
     192             :             // if left hand cell has a constant term, put into rhs value
     193           0 :             double fRightValue = -rLeftCoeff[0];
     194             : 
     195           0 :             if ( bRightCell )
     196             :             {
     197           0 :                 const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
     198             :                 // modify pValues with rhs coefficients
     199           0 :                 for (nVar=0; nVar<nVariables; nVar++)
     200           0 :                     pValues[nVar] -= rRightCoeff[nVar+1];
     201             : 
     202           0 :                 fRightValue += rRightCoeff[0];      // constant term
     203             :             }
     204             :             else
     205           0 :                 fRightValue += fDirectValue;
     206             : 
     207           0 :             switch ( eOp )
     208             :             {
     209           0 :                 case sheet::SolverConstraintOperator_LESS_EQUAL:    pRowType[nConstrPos] = 'L'; break;
     210           0 :                 case sheet::SolverConstraintOperator_GREATER_EQUAL: pRowType[nConstrPos] = 'G'; break;
     211           0 :                 case sheet::SolverConstraintOperator_EQUAL:         pRowType[nConstrPos] = 'E'; break;
     212             :                 default:
     213             :                     OSL_ENSURE( false, "unexpected enum type" );
     214             :             }
     215           0 :             pRHS[nConstrPos] = fRightValue;
     216             :         }
     217             :     }
     218             : 
     219             :     // Find non-zero coefficients, column-wise
     220             : 
     221           0 :     int* pMatrixBegin = new int[nVariables+1];
     222           0 :     int* pMatrixCount = new int[nVariables];
     223           0 :     double* pMatrix = new double[nCompSize];    // not always completely used
     224           0 :     int* pMatrixIndex = new int[nCompSize];
     225           0 :     int nMatrixPos = 0;
     226           0 :     for (nVar=0; nVar<nVariables; nVar++)
     227             :     {
     228           0 :         int nBegin = nMatrixPos;
     229           0 :         for (size_t nRow=0; nRow<nRows; nRow++)
     230             :         {
     231           0 :             double fCoeff = pCompMatrix[ nRow * nVariables + nVar ];    // row-wise
     232           0 :             if ( fCoeff != 0.0 )
     233             :             {
     234           0 :                 pMatrix[nMatrixPos] = fCoeff;
     235           0 :                 pMatrixIndex[nMatrixPos] = nRow;
     236           0 :                 ++nMatrixPos;
     237             :             }
     238             :         }
     239           0 :         pMatrixBegin[nVar] = nBegin;
     240           0 :         pMatrixCount[nVar] = nMatrixPos - nBegin;
     241             :     }
     242           0 :     pMatrixBegin[nVariables] = nMatrixPos;
     243           0 :     delete[] pCompMatrix;
     244           0 :     pCompMatrix = NULL;
     245             : 
     246             :     // apply settings to all variables
     247             : 
     248           0 :     double* pLowerBounds = new double[nVariables];
     249           0 :     double* pUpperBounds = new double[nVariables];
     250           0 :     for (nVar=0; nVar<nVariables; nVar++)
     251             :     {
     252           0 :         pLowerBounds[nVar] = mbNonNegative ? 0.0 : -DBL_MAX;
     253           0 :         pUpperBounds[nVar] = DBL_MAX;
     254             : 
     255             :         // bounds could possibly be further restricted from single-cell constraints
     256             :     }
     257             : 
     258           0 :     char* pColType = new char[nVariables];
     259           0 :     for (nVar=0; nVar<nVariables; nVar++)
     260           0 :         pColType[nVar] = mbInteger ? 'I' : 'C';
     261             : 
     262             :     // apply single-var integer constraints
     263             : 
     264           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
     265             :     {
     266           0 :         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
     267           0 :         if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
     268             :              eOp == sheet::SolverConstraintOperator_BINARY )
     269             :         {
     270           0 :             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
     271             :             // find variable index for cell
     272           0 :             for (nVar=0; nVar<nVariables; nVar++)
     273           0 :                 if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
     274             :                 {
     275           0 :                     if ( eOp == sheet::SolverConstraintOperator_INTEGER )
     276           0 :                         pColType[nVar] = 'I';
     277             :                     else
     278             :                     {
     279           0 :                         pColType[nVar] = 'B';
     280           0 :                         pLowerBounds[nVar] = 0.0;
     281           0 :                         pUpperBounds[nVar] = 1.0;
     282             :                     }
     283             :                 }
     284             :         }
     285             :     }
     286             : 
     287           0 :     int nObjectSense = mbMaximize ? SOLV_OBJSENS_MAX : SOLV_OBJSENS_MIN;
     288             : 
     289           0 :     HPROB hProb = CoinCreateProblem("");
     290             :     int nResult = CoinLoadProblem( hProb, nVariables, nRows, nMatrixPos, 0,
     291             :                     nObjectSense, nObjectConst, pObjectCoeffs,
     292             :                     pLowerBounds, pUpperBounds, pRowType, pRHS, NULL,
     293             :                     pMatrixBegin, pMatrixCount, pMatrixIndex, pMatrix,
     294           0 :                     NULL, NULL, NULL );
     295           0 :     nResult = CoinLoadInteger( hProb, pColType );
     296             : 
     297           0 :     delete[] pColType;
     298           0 :     delete[] pMatrixIndex;
     299           0 :     delete[] pMatrix;
     300           0 :     delete[] pMatrixCount;
     301           0 :     delete[] pMatrixBegin;
     302           0 :     delete[] pUpperBounds;
     303           0 :     delete[] pLowerBounds;
     304           0 :     delete[] pRowType;
     305           0 :     delete[] pRHS;
     306           0 :     delete[] pObjectCoeffs;
     307             : 
     308           0 :     CoinSetRealOption( hProb, COIN_REAL_MAXSECONDS, mnTimeout );
     309           0 :     CoinSetRealOption( hProb, COIN_REAL_MIPMAXSEC, mnTimeout );
     310             : 
     311             :     // TODO: handle (or remove) settings: epsilon, B&B depth
     312             : 
     313             :     // solve model
     314             : 
     315           0 :     nResult = CoinCheckProblem( hProb );
     316           0 :     nResult = CoinOptimizeProblem( hProb, 0 );
     317             : 
     318           0 :     mbSuccess = ( nResult == SOLV_CALL_SUCCESS );
     319           0 :     if ( mbSuccess )
     320             :     {
     321             :         // get solution
     322             : 
     323           0 :         maSolution.realloc( nVariables );
     324           0 :         CoinGetSolutionValues( hProb, maSolution.getArray(), NULL, NULL, NULL );
     325           0 :         mfResultValue = CoinGetObjectValue( hProb );
     326             :     }
     327             :     else
     328             :     {
     329           0 :         int nSolutionStatus = CoinGetSolutionStatus( hProb );
     330           0 :         if ( nSolutionStatus == 1 )
     331           0 :             maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE );
     332           0 :         else if ( nSolutionStatus == 2 )
     333           0 :             maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED );
     334             :         // TODO: detect timeout condition and report as RID_ERROR_TIMEOUT
     335             :         // (currently reported as infeasible)
     336             :     }
     337             : 
     338           0 :     CoinUnloadProblem( hProb );
     339             : }
     340             : 
     341             : extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * SAL_CALL
     342           0 : com_sun_star_comp_Calc_CoinMPSolver_get_implementation(
     343             :     css::uno::XComponentContext *,
     344             :     css::uno::Sequence<css::uno::Any> const &)
     345             : {
     346           0 :     return cppu::acquire(new CoinMPSolver());
     347             : }
     348             : 
     349             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10