sccomp/source/solver/LpsolveSolver.cxx

   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     LpsolveSolver() {}
  71     virtual ~LpsolveSolver() {}
  72
  73 private:
  74     virtual void SAL_CALL solve() throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE;
  75     virtual OUString SAL_CALL getImplementationName()
  76         throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE
  77     {
  78         return OUString("com.sun.star.comp.Calc.LpsolveSolver");
  79     }
  80     virtual OUString SAL_CALL getComponentDescription()
  81         throw (uno::RuntimeException, std::exception) SAL_OVERRIDE
  82     {
  83         return SolverComponent::GetResourceString( RID_SOLVER_COMPONENT );
  84     }
  85 };
  86
  87 void SAL_CALL LpsolveSolver::solve() throw(uno::RuntimeException, std::exception)
  88 {
  89     uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY );
  90     if ( !xModel.is() )
  91         throw uno::RuntimeException();
  92
  93     maStatus.clear();
  94     mbSuccess = false;
  95
  96     if ( mnEpsilonLevel < EPS_TIGHT || mnEpsilonLevel > EPS_BAGGY )
  97     {
  98         maStatus = SolverComponent::GetResourceString( RID_ERROR_EPSILONLEVEL );
  99         return;
 100     }
 101
 102     xModel->lockControllers();
 103
 104     // collect variables in vector (?)
 105
 106     std::vector<table::CellAddress> aVariableCells;
 107     for (sal_Int32 nPos=0; nPos<maVariables.getLength(); nPos++)
 108         aVariableCells.push_back( maVariables[nPos] );
 109     size_t nVariables = aVariableCells.size();
 110     size_t nVar = 0;
 111
 112     // collect all dependent cells
 113
 114     ScSolverCellHashMap aCellsHash;
 115     aCellsHash[maObjective].reserve( nVariables + 1 );                  // objective function
 116
 117     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
 118     {
 119         table::CellAddress aCellAddr = maConstraints[nConstrPos].Left;
 120         aCellsHash[aCellAddr].reserve( nVariables + 1 );                // constraints: left hand side
 121
 122         if ( maConstraints[nConstrPos].Right >>= aCellAddr )
 123             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     std::vector<table::CellAddress>::const_iterator aVarIter;
 130     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
 131     {
 132         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );
 133     }
 134
 135     // read initial values from all dependent cells
 136     ScSolverCellHashMap::iterator aCellsIter;
 137     for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
 138     {
 139         double fValue = SolverComponent::GetValue( mxDoc, aCellsIter->first );
 140         aCellsIter->second.push_back( fValue );                         // store as first element, as-is
 141     }
 142
 143     // loop through variables
 144     for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
 145     {
 146         SolverComponent::SetValue( mxDoc, *aVarIter, 1.0 );      // set to 1 to examine influence
 147
 148         // read value change from all dependent cells
 149         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
 150         {
 151             double fChanged = SolverComponent::GetValue( mxDoc, aCellsIter->first );
 152             double fInitial = aCellsIter->second.front();
 153             aCellsIter->second.push_back( fChanged - fInitial );
 154         }
 155
 156         SolverComponent::SetValue( mxDoc, *aVarIter, 2.0 );      // minimal test for linearity
 157
 158         for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
 159         {
 160             double fInitial = aCellsIter->second.front();
 161             double fCoeff   = aCellsIter->second.back();       // last appended: coefficient for this variable
 162             double fTwo     = SolverComponent::GetValue( mxDoc, aCellsIter->first );
 163
 164             bool bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
 165                            rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
 166             // second comparison is needed in case fTwo is zero
 167             if ( !bLinear )
 168                 maStatus = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR );
 169         }
 170
 171         SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );      // set back to zero for examining next variable
 172     }
 173
 174     xModel->unlockControllers();
 175
 176     if ( !maStatus.isEmpty() )
 177         return;
 178
 179
 180     // build lp_solve model
 181
 182
 183     lprec* lp = make_lp( 0, nVariables );
 184     if ( !lp )
 185         return;
 186
 187     set_outputfile( lp, const_cast<char*>( "" ) );  // no output
 188
 189     // set objective function
 190
 191     const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
 192     REAL* pObjVal = new REAL[nVariables+1];
 193     pObjVal[0] = 0.0;                           // ignored
 194     for (nVar=0; nVar<nVariables; nVar++)
 195         pObjVal[nVar+1] = rObjCoeff[nVar+1];
 196     set_obj_fn( lp, pObjVal );
 197     delete[] pObjVal;
 198     set_rh( lp, 0, rObjCoeff[0] );              // constant term of objective
 199
 200     // add rows
 201
 202     set_add_rowmode(lp, TRUE);
 203
 204     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
 205     {
 206         // integer constraints are set later
 207         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
 208         if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
 209              eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
 210              eOp == sheet::SolverConstraintOperator_EQUAL )
 211         {
 212             double fDirectValue = 0.0;
 213             bool bRightCell = false;
 214             table::CellAddress aRightAddr;
 215             const uno::Any& rRightAny = maConstraints[nConstrPos].Right;
 216             if ( rRightAny >>= aRightAddr )
 217                 bRightCell = true;                  // cell specified as right-hand side
 218             else
 219                 rRightAny >>= fDirectValue;         // constant value
 220
 221             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
 222
 223             const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
 224             REAL* pValues = new REAL[nVariables+1];
 225             pValues[0] = 0.0;                               // ignored?
 226             for (nVar=0; nVar<nVariables; nVar++)
 227                 pValues[nVar+1] = rLeftCoeff[nVar+1];
 228
 229             // if left hand cell has a constant term, put into rhs value
 230             double fRightValue = -rLeftCoeff[0];
 231
 232             if ( bRightCell )
 233             {
 234                 const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
 235                 // modify pValues with rhs coefficients
 236                 for (nVar=0; nVar<nVariables; nVar++)
 237                     pValues[nVar+1] -= rRightCoeff[nVar+1];
 238
 239                 fRightValue += rRightCoeff[0];      // constant term
 240             }
 241             else
 242                 fRightValue += fDirectValue;
 243
 244             int nConstrType = LE;
 245             switch ( eOp )
 246             {
 247                 case sheet::SolverConstraintOperator_LESS_EQUAL:    nConstrType = LE; break;
 248                 case sheet::SolverConstraintOperator_GREATER_EQUAL: nConstrType = GE; break;
 249                 case sheet::SolverConstraintOperator_EQUAL:         nConstrType = EQ; break;
 250                 default:
 251                     OSL_FAIL( "unexpected enum type" );
 252             }
 253             add_constraint( lp, pValues, nConstrType, fRightValue );
 254
 255             delete[] pValues;
 256         }
 257     }
 258
 259     set_add_rowmode(lp, FALSE);
 260
 261     // apply settings to all variables
 262
 263     for (nVar=0; nVar<nVariables; nVar++)
 264     {
 265         if ( !mbNonNegative )
 266             set_unbounded(lp, nVar+1);          // allow negative (default is non-negative)
 267                                                 //! collect bounds from constraints?
 268         if ( mbInteger )
 269             set_int(lp, nVar+1, TRUE);
 270     }
 271
 272     // apply single-var integer constraints
 273
 274     for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
 275     {
 276         sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
 277         if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
 278              eOp == sheet::SolverConstraintOperator_BINARY )
 279         {
 280             table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
 281             // find variable index for cell
 282             for (nVar=0; nVar<nVariables; nVar++)
 283                 if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
 284                 {
 285                     if ( eOp == sheet::SolverConstraintOperator_INTEGER )
 286                         set_int(lp, nVar+1, TRUE);
 287                     else
 288                         set_binary(lp, nVar+1, TRUE);
 289                 }
 290         }
 291     }
 292
 293     if ( mbMaximize )
 294         set_maxim(lp);
 295     else
 296         set_minim(lp);
 297
 298     if ( !mbLimitBBDepth )
 299         set_bb_depthlimit( lp, 0 );
 300
 301     set_epslevel( lp, mnEpsilonLevel );
 302     set_timeout( lp, mnTimeout );
 303
 304     // solve model
 305
 306     int nResult = ::solve( lp );
 307
 308     mbSuccess = ( nResult == OPTIMAL );
 309     if ( mbSuccess )
 310     {
 311         // get solution
 312
 313         maSolution.realloc( nVariables );
 314
 315         REAL* pResultVar = NULL;
 316         get_ptr_variables( lp, &pResultVar );
 317         for (nVar=0; nVar<nVariables; nVar++)
 318             maSolution[nVar] = pResultVar[nVar];
 319
 320         mfResultValue = get_objective( lp );
 321     }
 322     else if ( nResult == INFEASIBLE )
 323         maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE );
 324     else if ( nResult == UNBOUNDED )
 325         maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED );
 326     else if ( nResult == TIMEOUT || nResult == SUBOPTIMAL )
 327         maStatus = SolverComponent::GetResourceString( RID_ERROR_TIMEOUT );
 328     // SUBOPTIMAL is assumed to be caused by a timeout, and reported as an error
 329
 330     delete_lp( lp );
 331 }
 332
 333 extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * SAL_CALL
 334 com_sun_star_comp_Calc_LpsolveSolver_get_implementation(
 335     css::uno::XComponentContext *,
 336     css::uno::Sequence<css::uno::Any> const &)
 337 {
 338     return cppu::acquire(new LpsolveSolver());
 339 }
 340
 341 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */