LCOV - code coverage report
Current view: top level - sccomp/source/solver - LpsolveSolver.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 138 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             :  *
       4             :  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
       5             :  *
       6             :  * Copyright 2000, 2010 Oracle and/or its affiliates.
       7             :  *
       8             :  * OpenOffice.org - a multi-platform office productivity suite
       9             :  *
      10             :  * This file is part of OpenOffice.org.
      11             :  *
      12             :  * OpenOffice.org is free software: you can redistribute it and/or modify
      13             :  * it under the terms of the GNU Lesser General Public License version 3
      14             :  * only, as published by the Free Software Foundation.
      15             :  *
      16             :  * OpenOffice.org is distributed in the hope that it will be useful,
      17             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      18             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      19             :  * GNU Lesser General Public License version 3 for more details
      20             :  * (a copy is included in the LICENSE file that accompanied this code).
      21             :  *
      22             :  * You should have received a copy of the GNU Lesser General Public License
      23             :  * version 3 along with OpenOffice.org.  If not, see
      24             :  * <http://www.openoffice.org/license.html>
      25             :  * for a copy of the LGPLv3 License.
      26             :  *
      27             :  * This file incorporates work covered by the following license notice:
      28             :  *
      29             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      30             :  *   contributor license agreements. See the NOTICE file distributed
      31             :  *   with this work for additional information regarding copyright
      32             :  *   ownership. The ASF licenses this file to you under the Apache
      33             :  *   License, Version 2.0 (the "License"); you may not use this file
      34             :  *   except in compliance with the License. You may obtain a copy of
      35             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      36             :  *
      37             :  ************************************************************************/
      38             : 
      39             : #include "sal/config.h"
      40             : #include <config_lgpl.h>
      41             : 
      42             : #undef LANGUAGE_NONE
      43             : #if defined SAL_W32
      44             : #define WINAPI __stdcall
      45             : #endif
      46             : #define LoadInverseLib FALSE
      47             : #define LoadLanguageLib FALSE
      48             : #ifdef SYSTEM_LPSOLVE
      49             : #include <lpsolve/lp_lib.h>
      50             : #else
      51             : #include <lp_lib.h>
      52             : #endif
      53             : #undef LANGUAGE_NONE
      54             : 
      55             : #include "SolverComponent.hxx"
      56             : #include "solver.hrc"
      57             : 
      58             : #include <com/sun/star/frame/XModel.hpp>
      59             : #include <com/sun/star/table/CellAddress.hpp>
      60             : #include <com/sun/star/uno/XComponentContext.hpp>
      61             : #include <rtl/math.hxx>
      62             : #include <cppuhelper/supportsservice.hxx>
      63             : #include <vector>
      64             : 
      65             : using namespace com::sun::star;
      66             : 
      67             : class LpsolveSolver : public SolverComponent
      68             : {
      69             : public:
      70           0 :     LpsolveSolver() {}
      71           0 :     virtual ~LpsolveSolver() {}
      72             : 
      73             : private:
      74             :     virtual void SAL_CALL solve() throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE;
      75           0 :     virtual OUString SAL_CALL getImplementationName()
      76             :         throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE
      77             :     {
      78           0 :         return OUString("com.sun.star.comp.Calc.LpsolveSolver");
      79             :     }
      80           0 :     virtual OUString SAL_CALL getComponentDescription()
      81             :         throw (uno::RuntimeException, std::exception) SAL_OVERRIDE
      82             :     {
      83           0 :         return SolverComponent::GetResourceString( RID_SOLVER_COMPONENT );
      84             :     }
      85             : };
      86             : 
      87           0 : void SAL_CALL LpsolveSolver::solve() throw(uno::RuntimeException, std::exception)
      88             : {
      89           0 :     uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY );
      90           0 :     if ( !xModel.is() )
      91           0 :         throw uno::RuntimeException();
      92             : 
      93           0 :     maStatus = "";
      94           0 :     mbSuccess = false;
      95             : 
      96           0 :     if ( mnEpsilonLevel < EPS_TIGHT || mnEpsilonLevel > EPS_BAGGY )
      97             :     {
      98           0 :         maStatus = SolverComponent::GetResourceString( RID_ERROR_EPSILONLEVEL );
      99           0 :         return;
     100             :     }
     101             : 
     102           0 :     xModel->lockControllers();
     103             : 
     104             :     // collect variables in vector (?)
     105             : 
     106           0 :     std::vector<table::CellAddress> aVariableCells;
     107           0 :     for (sal_Int32 nPos=0; nPos<maVariables.getLength(); nPos++)
     108           0 :         aVariableCells.push_back( maVariables[nPos] );
     109           0 :     size_t nVariables = aVariableCells.size();
     110           0 :     size_t nVar = 0;
     111             : 
     112             :     // collect all dependent cells
     113             : 
     114           0 :     ScSolverCellHashMap aCellsHash;
     115           0 :     aCellsHash[maObjective].reserve( nVariables + 1 );                  // objective function
     116             : 
     117           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
     118             :     {
     119           0 :         table::CellAddress aCellAddr = maConstraints[nConstrPos].Left;
     120           0 :         aCellsHash[aCellAddr].reserve( nVariables + 1 );                // constraints: left hand side
     121             : 
     122           0 :         if ( maConstraints[nConstrPos].Right >>= aCellAddr )
     123           0 :             aCellsHash[aCellAddr].reserve( nVariables + 1 );            // constraints: right hand side
     124             :     }
     125             : 
     126             :     // set all variables to zero
     127             :     //! store old values?
     128             :     //! use old values as initial values?
     129           0 :     std::vector<table::CellAddress>::const_iterator aVarIter;
     130           0 :     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
     131             :     {
     132           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );
     133             :     }
     134             : 
     135             :     // read initial values from all dependent cells
     136           0 :     ScSolverCellHashMap::iterator aCellsIter;
     137           0 :     for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
     138             :     {
     139           0 :         double fValue = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     140           0 :         aCellsIter->second.push_back( fValue );                         // store as first element, as-is
     141             :     }
     142             : 
     143             :     // loop through variables
     144           0 :     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
     145             :     {
     146           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 1.0 );      // set to 1 to examine influence
     147             : 
     148             :         // read value change from all dependent cells
     149           0 :         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
     150             :         {
     151           0 :             double fChanged = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     152           0 :             double fInitial = aCellsIter->second.front();
     153           0 :             aCellsIter->second.push_back( fChanged - fInitial );
     154             :         }
     155             : 
     156           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 2.0 );      // minimal test for linearity
     157             : 
     158           0 :         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
     159             :         {
     160           0 :             double fInitial = aCellsIter->second.front();
     161           0 :             double fCoeff   = aCellsIter->second.back();       // last appended: coefficient for this variable
     162           0 :             double fTwo     = SolverComponent::GetValue( mxDoc, aCellsIter->first );
     163             : 
     164           0 :             bool bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
     165           0 :                            rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
     166             :             // second comparison is needed in case fTwo is zero
     167           0 :             if ( !bLinear )
     168           0 :                 maStatus = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR );
     169             :         }
     170             : 
     171           0 :         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );      // set back to zero for examining next variable
     172             :     }
     173             : 
     174           0 :     xModel->unlockControllers();
     175             : 
     176           0 :     if ( !maStatus.isEmpty() )
     177           0 :         return;
     178             : 
     179             : 
     180             :     // build lp_solve model
     181             : 
     182             : 
     183           0 :     lprec* lp = make_lp( 0, nVariables );
     184           0 :     if ( !lp )
     185           0 :         return;
     186             : 
     187           0 :     set_outputfile( lp, const_cast<char*>( "" ) );  // no output
     188             : 
     189             :     // set objective function
     190             : 
     191           0 :     const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
     192           0 :     REAL* pObjVal = new REAL[nVariables+1];
     193           0 :     pObjVal[0] = 0.0;                           // ignored
     194           0 :     for (nVar=0; nVar<nVariables; nVar++)
     195           0 :         pObjVal[nVar+1] = rObjCoeff[nVar+1];
     196           0 :     set_obj_fn( lp, pObjVal );
     197           0 :     delete[] pObjVal;
     198           0 :     set_rh( lp, 0, rObjCoeff[0] );              // constant term of objective
     199             : 
     200             :     // add rows
     201             : 
     202           0 :     set_add_rowmode(lp, TRUE);
     203             : 
     204           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
     205             :     {
     206             :         // integer constraints are set later
     207           0 :         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
     208           0 :         if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
     209           0 :              eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
     210             :              eOp == sheet::SolverConstraintOperator_EQUAL )
     211             :         {
     212           0 :             double fDirectValue = 0.0;
     213           0 :             bool bRightCell = false;
     214           0 :             table::CellAddress aRightAddr;
     215           0 :             const uno::Any& rRightAny = maConstraints[nConstrPos].Right;
     216           0 :             if ( rRightAny >>= aRightAddr )
     217           0 :                 bRightCell = true;                  // cell specified as right-hand side
     218             :             else
     219           0 :                 rRightAny >>= fDirectValue;         // constant value
     220             : 
     221           0 :             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
     222             : 
     223           0 :             const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
     224           0 :             REAL* pValues = new REAL[nVariables+1];
     225           0 :             pValues[0] = 0.0;                               // ignored?
     226           0 :             for (nVar=0; nVar<nVariables; nVar++)
     227           0 :                 pValues[nVar+1] = rLeftCoeff[nVar+1];
     228             : 
     229             :             // if left hand cell has a constant term, put into rhs value
     230           0 :             double fRightValue = -rLeftCoeff[0];
     231             : 
     232           0 :             if ( bRightCell )
     233             :             {
     234           0 :                 const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
     235             :                 // modify pValues with rhs coefficients
     236           0 :                 for (nVar=0; nVar<nVariables; nVar++)
     237           0 :                     pValues[nVar+1] -= rRightCoeff[nVar+1];
     238             : 
     239           0 :                 fRightValue += rRightCoeff[0];      // constant term
     240             :             }
     241             :             else
     242           0 :                 fRightValue += fDirectValue;
     243             : 
     244           0 :             int nConstrType = LE;
     245           0 :             switch ( eOp )
     246             :             {
     247           0 :                 case sheet::SolverConstraintOperator_LESS_EQUAL:    nConstrType = LE; break;
     248           0 :                 case sheet::SolverConstraintOperator_GREATER_EQUAL: nConstrType = GE; break;
     249           0 :                 case sheet::SolverConstraintOperator_EQUAL:         nConstrType = EQ; break;
     250             :                 default:
     251             :                     OSL_FAIL( "unexpected enum type" );
     252             :             }
     253           0 :             add_constraint( lp, pValues, nConstrType, fRightValue );
     254             : 
     255           0 :             delete[] pValues;
     256             :         }
     257             :     }
     258             : 
     259           0 :     set_add_rowmode(lp, FALSE);
     260             : 
     261             :     // apply settings to all variables
     262             : 
     263           0 :     for (nVar=0; nVar<nVariables; nVar++)
     264             :     {
     265           0 :         if ( !mbNonNegative )
     266           0 :             set_unbounded(lp, nVar+1);          // allow negative (default is non-negative)
     267             :                                                 //! collect bounds from constraints?
     268           0 :         if ( mbInteger )
     269           0 :             set_int(lp, nVar+1, TRUE);
     270             :     }
     271             : 
     272             :     // apply single-var integer constraints
     273             : 
     274           0 :     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
     275             :     {
     276           0 :         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
     277           0 :         if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
     278             :              eOp == sheet::SolverConstraintOperator_BINARY )
     279             :         {
     280           0 :             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
     281             :             // find variable index for cell
     282           0 :             for (nVar=0; nVar<nVariables; nVar++)
     283           0 :                 if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
     284             :                 {
     285           0 :                     if ( eOp == sheet::SolverConstraintOperator_INTEGER )
     286           0 :                         set_int(lp, nVar+1, TRUE);
     287             :                     else
     288           0 :                         set_binary(lp, nVar+1, TRUE);
     289             :                 }
     290             :         }
     291             :     }
     292             : 
     293           0 :     if ( mbMaximize )
     294           0 :         set_maxim(lp);
     295             :     else
     296           0 :         set_minim(lp);
     297             : 
     298           0 :     if ( !mbLimitBBDepth )
     299           0 :         set_bb_depthlimit( lp, 0 );
     300             : 
     301           0 :     set_epslevel( lp, mnEpsilonLevel );
     302           0 :     set_timeout( lp, mnTimeout );
     303             : 
     304             :     // solve model
     305             : 
     306           0 :     int nResult = ::solve( lp );
     307             : 
     308           0 :     mbSuccess = ( nResult == OPTIMAL );
     309           0 :     if ( mbSuccess )
     310             :     {
     311             :         // get solution
     312             : 
     313           0 :         maSolution.realloc( nVariables );
     314             : 
     315           0 :         REAL* pResultVar = NULL;
     316           0 :         get_ptr_variables( lp, &pResultVar );
     317           0 :         for (nVar=0; nVar<nVariables; nVar++)
     318           0 :             maSolution[nVar] = pResultVar[nVar];
     319             : 
     320           0 :         mfResultValue = get_objective( lp );
     321             :     }
     322           0 :     else if ( nResult == INFEASIBLE )
     323           0 :         maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE );
     324           0 :     else if ( nResult == UNBOUNDED )
     325           0 :         maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED );
     326           0 :     else if ( nResult == TIMEOUT || nResult == SUBOPTIMAL )
     327           0 :         maStatus = SolverComponent::GetResourceString( RID_ERROR_TIMEOUT );
     328             :     // SUBOPTIMAL is assumed to be caused by a timeout, and reported as an error
     329             : 
     330           0 :     delete_lp( lp );
     331             : }
     332             : 
     333             : extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * SAL_CALL
     334           0 : com_sun_star_comp_Calc_LpsolveSolver_get_implementation(
     335             :     css::uno::XComponentContext *,
     336             :     css::uno::Sequence<css::uno::Any> const &)
     337             : {
     338           0 :     return cppu::acquire(new LpsolveSolver());
     339             : }
     340             : 
     341             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10