diff options
Diffstat (limited to '')
| -rw-r--r-- | sccomp/source/solver/LpsolveSolver.cxx | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/sccomp/source/solver/LpsolveSolver.cxx b/sccomp/source/solver/LpsolveSolver.cxx new file mode 100644 index 000000000..78cd25e81 --- /dev/null +++ b/sccomp/source/solver/LpsolveSolver.cxx @@ -0,0 +1,334 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/************************************************************************* + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * Copyright 2000, 2010 Oracle and/or its affiliates. + * + * OpenOffice.org - a multi-platform office productivity suite + * + * This file is part of OpenOffice.org. + * + * OpenOffice.org is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License version 3 + * only, as published by the Free Software Foundation. + * + * OpenOffice.org is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License version 3 for more details + * (a copy is included in the LICENSE file that accompanied this code). + * + * You should have received a copy of the GNU Lesser General Public License + * version 3 along with OpenOffice.org. If not, see + * <http://www.openoffice.org/license.html> + * for a copy of the LGPLv3 License. + * + * This file incorporates work covered by the following license notice: + * + * 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 . + * + ************************************************************************/ + +#include <sal/config.h> + +#undef LANGUAGE_NONE +#if defined _WIN32 +#define WINAPI __stdcall +#endif +#define LoadInverseLib FALSE +#define LoadLanguageLib FALSE +#ifdef SYSTEM_LPSOLVE +#include <lpsolve/lp_lib.h> +#else +#include <lp_lib.h> +#endif +#undef LANGUAGE_NONE + +#include "SolverComponent.hxx" +#include <strings.hrc> + +#include <com/sun/star/frame/XModel.hpp> +#include <com/sun/star/table/CellAddress.hpp> +#include <rtl/math.hxx> +#include <algorithm> +#include <memory> +#include <vector> + +namespace com::sun::star::uno { class XComponentContext; } + +using namespace com::sun::star; + +namespace { + +class LpsolveSolver : public SolverComponent +{ +public: + LpsolveSolver() {} + +private: + virtual void SAL_CALL solve() override; + virtual OUString SAL_CALL getImplementationName() override + { + return "com.sun.star.comp.Calc.LpsolveSolver"; + } + virtual OUString SAL_CALL getComponentDescription() override + { + return SolverComponent::GetResourceString( RID_SOLVER_COMPONENT ); + } +}; + +} + +void SAL_CALL LpsolveSolver::solve() +{ + uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY_THROW ); + + maStatus.clear(); + mbSuccess = false; + + if ( mnEpsilonLevel < EPS_TIGHT || mnEpsilonLevel > EPS_BAGGY ) + { + maStatus = SolverComponent::GetResourceString( RID_ERROR_EPSILONLEVEL ); + return; + } + + xModel->lockControllers(); + + // collect variables in vector (?) + + const auto & aVariableCells = maVariables; + size_t nVariables = aVariableCells.size(); + size_t nVar = 0; + + // collect all dependent cells + + ScSolverCellHashMap aCellsHash; + aCellsHash[maObjective].reserve( nVariables + 1 ); // objective function + + for (const auto& rConstr : std::as_const(maConstraints)) + { + table::CellAddress aCellAddr = rConstr.Left; + aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: left hand side + + if ( rConstr.Right >>= aCellAddr ) + aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: right hand side + } + + // set all variables to zero + //! store old values? + //! use old values as initial values? + for ( const auto& rVarCell : aVariableCells ) + { + SolverComponent::SetValue( mxDoc, rVarCell, 0.0 ); + } + + // read initial values from all dependent cells + for ( auto& rEntry : aCellsHash ) + { + double fValue = SolverComponent::GetValue( mxDoc, rEntry.first ); + rEntry.second.push_back( fValue ); // store as first element, as-is + } + + // loop through variables + for ( const auto& rVarCell : aVariableCells ) + { + SolverComponent::SetValue( mxDoc, rVarCell, 1.0 ); // set to 1 to examine influence + + // read value change from all dependent cells + for ( auto& rEntry : aCellsHash ) + { + double fChanged = SolverComponent::GetValue( mxDoc, rEntry.first ); + double fInitial = rEntry.second.front(); + rEntry.second.push_back( fChanged - fInitial ); + } + + SolverComponent::SetValue( mxDoc, rVarCell, 2.0 ); // minimal test for linearity + + for ( const auto& rEntry : aCellsHash ) + { + double fInitial = rEntry.second.front(); + double fCoeff = rEntry.second.back(); // last appended: coefficient for this variable + double fTwo = SolverComponent::GetValue( mxDoc, rEntry.first ); + + bool 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 = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR ); + } + + SolverComponent::SetValue( mxDoc, rVarCell, 0.0 ); // set back to zero for examining next variable + } + + xModel->unlockControllers(); + + if ( !maStatus.isEmpty() ) + return; + + + // build lp_solve model + + + lprec* lp = make_lp( 0, nVariables ); + if ( !lp ) + return; + + set_outputfile( lp, const_cast<char*>( "" ) ); // no output + + // set objective function + + const std::vector<double>& rObjCoeff = aCellsHash[maObjective]; + std::unique_ptr<REAL[]> pObjVal(new REAL[nVariables+1]); + pObjVal[0] = 0.0; // ignored + for (nVar=0; nVar<nVariables; nVar++) + pObjVal[nVar+1] = rObjCoeff[nVar+1]; + set_obj_fn( lp, pObjVal.get() ); + pObjVal.reset(); + set_rh( lp, 0, rObjCoeff[0] ); // constant term of objective + + // add rows + + set_add_rowmode(lp, TRUE); + + for (const auto& rConstr : std::as_const(maConstraints)) + { + // integer constraints are set later + sheet::SolverConstraintOperator eOp = rConstr.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 = rConstr.Right; + if ( rRightAny >>= aRightAddr ) + bRightCell = true; // cell specified as right-hand side + else + rRightAny >>= fDirectValue; // constant value + + table::CellAddress aLeftAddr = rConstr.Left; + + const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr]; + std::unique_ptr<REAL[]> pValues(new REAL[nVariables+1] ); + pValues[0] = 0.0; // ignored? + for (nVar=0; nVar<nVariables; nVar++) + pValues[nVar+1] = 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+1] -= rRightCoeff[nVar+1]; + + fRightValue += rRightCoeff[0]; // constant term + } + else + fRightValue += fDirectValue; + + int nConstrType = LE; + switch ( eOp ) + { + case sheet::SolverConstraintOperator_LESS_EQUAL: nConstrType = LE; break; + case sheet::SolverConstraintOperator_GREATER_EQUAL: nConstrType = GE; break; + case sheet::SolverConstraintOperator_EQUAL: nConstrType = EQ; break; + default: + OSL_FAIL( "unexpected enum type" ); + } + add_constraint( lp, pValues.get(), nConstrType, fRightValue ); + } + } + + set_add_rowmode(lp, FALSE); + + // apply settings to all variables + + for (nVar=0; nVar<nVariables; nVar++) + { + if ( !mbNonNegative ) + set_unbounded(lp, nVar+1); // allow negative (default is non-negative) + //! collect bounds from constraints? + if ( mbInteger ) + set_int(lp, nVar+1, TRUE); + } + + // apply single-var integer constraints + + for (const auto& rConstr : std::as_const(maConstraints)) + { + sheet::SolverConstraintOperator eOp = rConstr.Operator; + if ( eOp == sheet::SolverConstraintOperator_INTEGER || + eOp == sheet::SolverConstraintOperator_BINARY ) + { + table::CellAddress aLeftAddr = rConstr.Left; + // find variable index for cell + for (nVar=0; nVar<nVariables; nVar++) + if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) ) + { + if ( eOp == sheet::SolverConstraintOperator_INTEGER ) + set_int(lp, nVar+1, TRUE); + else + set_binary(lp, nVar+1, TRUE); + } + } + } + + if ( mbMaximize ) + set_maxim(lp); + else + set_minim(lp); + + if ( !mbLimitBBDepth ) + set_bb_depthlimit( lp, 0 ); + + set_epslevel( lp, mnEpsilonLevel ); + set_timeout( lp, mnTimeout ); + + // solve model + + int nResult = ::solve( lp ); + + mbSuccess = ( nResult == OPTIMAL ); + if ( mbSuccess ) + { + // get solution + + maSolution.realloc( nVariables ); + + REAL* pResultVar = nullptr; + get_ptr_variables( lp, &pResultVar ); + std::copy_n(pResultVar, nVariables, maSolution.getArray()); + + mfResultValue = get_objective( lp ); + } + else if ( nResult == INFEASIBLE ) + maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE ); + else if ( nResult == UNBOUNDED ) + maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED ); + else if ( nResult == TIMEOUT || nResult == SUBOPTIMAL ) + maStatus = SolverComponent::GetResourceString( RID_ERROR_TIMEOUT ); + // SUBOPTIMAL is assumed to be caused by a timeout, and reported as an error + + delete_lp( lp ); +} + +extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * +com_sun_star_comp_Calc_LpsolveSolver_get_implementation( + css::uno::XComponentContext *, + css::uno::Sequence<css::uno::Any> const &) +{ + return cppu::acquire(new LpsolveSolver()); +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |