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