diff options
Diffstat (limited to '')
| -rw-r--r-- | sccomp/source/solver/SwarmSolver.cxx | 595 |
1 files changed, 595 insertions, 0 deletions
diff --git a/sccomp/source/solver/SwarmSolver.cxx b/sccomp/source/solver/SwarmSolver.cxx new file mode 100644 index 000000000..4aac9f81e --- /dev/null +++ b/sccomp/source/solver/SwarmSolver.cxx @@ -0,0 +1,595 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + */ + +#include <sal/config.h> + +#include <com/sun/star/frame/XModel.hpp> +#include <com/sun/star/container/XIndexAccess.hpp> +#include <com/sun/star/sheet/XSpreadsheetDocument.hpp> +#include <com/sun/star/sheet/XSpreadsheet.hpp> +#include <com/sun/star/sheet/XSolver.hpp> +#include <com/sun/star/sheet/XSolverDescription.hpp> +#include <com/sun/star/table/CellAddress.hpp> +#include <com/sun/star/table/CellContentType.hpp> +#include <com/sun/star/table/XCell.hpp> +#include <com/sun/star/lang/XServiceInfo.hpp> + +#include <rtl/math.hxx> +#include <cppuhelper/implbase.hxx> +#include <cppuhelper/supportsservice.hxx> + +#include <comphelper/broadcasthelper.hxx> +#include <comphelper/propertycontainer.hxx> +#include <comphelper/proparrhlp.hxx> + +#include <cmath> +#include <vector> +#include <limits> +#include <chrono> +#include <random> + +#include <unotools/resmgr.hxx> + +#include "DifferentialEvolution.hxx" +#include "ParticelSwarmOptimization.hxx" + +#include <strings.hrc> + +namespace com::sun::star::uno +{ +class XComponentContext; +} + +using namespace css; + +namespace +{ +struct Bound +{ + double lower; + double upper; + + Bound() + // float bounds should be low/high enough for all practical uses + // otherwise we are too far away from the solution + : lower(std::numeric_limits<float>::lowest()) + , upper(std::numeric_limits<float>::max()) + { + } + + void updateBound(sheet::SolverConstraintOperator eOp, double fValue) + { + if (eOp == sheet::SolverConstraintOperator_LESS_EQUAL) + { + // if we set the bound multiple times use the one which includes both values + // for example bound values 100, 120, 150 -> use 100 -> the lowest one + if (fValue < upper) + upper = fValue; + } + else if (eOp == sheet::SolverConstraintOperator_GREATER_EQUAL) + { + if (fValue > lower) + lower = fValue; + } + else if (eOp == sheet::SolverConstraintOperator_EQUAL) + { + lower = fValue; + upper = fValue; + } + } +}; + +enum +{ + PROP_NONNEGATIVE, + PROP_INTEGER, + PROP_TIMEOUT, + PROP_ALGORITHM, +}; + +} // end anonymous namespace + +typedef cppu::WeakImplHelper<sheet::XSolver, sheet::XSolverDescription, lang::XServiceInfo> + SwarmSolver_Base; + +namespace +{ +class SwarmSolver : public comphelper::OMutexAndBroadcastHelper, + public comphelper::OPropertyContainer, + public comphelper::OPropertyArrayUsageHelper<SwarmSolver>, + public SwarmSolver_Base +{ +private: + uno::Reference<sheet::XSpreadsheetDocument> mxDocument; + table::CellAddress maObjective; + uno::Sequence<table::CellAddress> maVariables; + uno::Sequence<sheet::SolverConstraint> maConstraints; + bool mbMaximize; + + // set via XPropertySet + bool mbNonNegative; + bool mbInteger; + sal_Int32 mnTimeout; + sal_Int32 mnAlgorithm; + + // results + bool mbSuccess; + double mfResultValue; + + uno::Sequence<double> maSolution; + OUString maStatus; + + std::vector<Bound> maBounds; + std::vector<sheet::SolverConstraint> maNonBoundedConstraints; + +private: + static OUString getResourceString(TranslateId aId); + + uno::Reference<table::XCell> getCell(const table::CellAddress& rPosition); + void setValue(const table::CellAddress& rPosition, double fValue); + double getValue(const table::CellAddress& rPosition); + +public: + SwarmSolver() + : OPropertyContainer(GetBroadcastHelper()) + , mbMaximize(true) + , mbNonNegative(false) + , mbInteger(false) + , mnTimeout(60000) + , mnAlgorithm(0) + , mbSuccess(false) + , mfResultValue(0.0) + { + registerProperty("NonNegative", PROP_NONNEGATIVE, 0, &mbNonNegative, + cppu::UnoType<decltype(mbNonNegative)>::get()); + registerProperty("Integer", PROP_INTEGER, 0, &mbInteger, + cppu::UnoType<decltype(mbInteger)>::get()); + registerProperty("Timeout", PROP_TIMEOUT, 0, &mnTimeout, + cppu::UnoType<decltype(mnTimeout)>::get()); + registerProperty("Algorithm", PROP_ALGORITHM, 0, &mnAlgorithm, + cppu::UnoType<decltype(mnAlgorithm)>::get()); + } + + DECLARE_XINTERFACE() + DECLARE_XTYPEPROVIDER() + + virtual uno::Reference<beans::XPropertySetInfo> SAL_CALL getPropertySetInfo() override + { + return createPropertySetInfo(getInfoHelper()); + } + // OPropertySetHelper + virtual cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override + { + return *getArrayHelper(); + } + // OPropertyArrayUsageHelper + virtual cppu::IPropertyArrayHelper* createArrayHelper() const override + { + uno::Sequence<beans::Property> aProperties; + describeProperties(aProperties); + return new cppu::OPropertyArrayHelper(aProperties); + } + + // XSolver + virtual uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL getDocument() override + { + return mxDocument; + } + virtual void SAL_CALL + setDocument(const uno::Reference<sheet::XSpreadsheetDocument>& rDocument) override + { + mxDocument = rDocument; + } + + virtual table::CellAddress SAL_CALL getObjective() override { return maObjective; } + virtual void SAL_CALL setObjective(const table::CellAddress& rObjective) override + { + maObjective = rObjective; + } + + virtual uno::Sequence<table::CellAddress> SAL_CALL getVariables() override + { + return maVariables; + } + virtual void SAL_CALL setVariables(const uno::Sequence<table::CellAddress>& rVariables) override + { + maVariables = rVariables; + } + + virtual uno::Sequence<sheet::SolverConstraint> SAL_CALL getConstraints() override + { + return maConstraints; + } + virtual void SAL_CALL + setConstraints(const uno::Sequence<sheet::SolverConstraint>& rConstraints) override + { + maConstraints = rConstraints; + } + + virtual sal_Bool SAL_CALL getMaximize() override { return mbMaximize; } + virtual void SAL_CALL setMaximize(sal_Bool bMaximize) override { mbMaximize = bMaximize; } + + virtual sal_Bool SAL_CALL getSuccess() override { return mbSuccess; } + virtual double SAL_CALL getResultValue() override { return mfResultValue; } + + virtual uno::Sequence<double> SAL_CALL getSolution() override { return maSolution; } + + virtual void SAL_CALL solve() override; + + // XSolverDescription + virtual OUString SAL_CALL getComponentDescription() override + { + return SwarmSolver::getResourceString(RID_SWARM_SOLVER_COMPONENT); + } + + virtual OUString SAL_CALL getStatusDescription() override { return maStatus; } + + virtual OUString SAL_CALL getPropertyDescription(const OUString& rPropertyName) override + { + TranslateId pResId; + switch (getInfoHelper().getHandleByName(rPropertyName)) + { + case PROP_NONNEGATIVE: + pResId = RID_PROPERTY_NONNEGATIVE; + break; + case PROP_INTEGER: + pResId = RID_PROPERTY_INTEGER; + break; + case PROP_TIMEOUT: + pResId = RID_PROPERTY_TIMEOUT; + break; + case PROP_ALGORITHM: + pResId = RID_PROPERTY_ALGORITHM; + break; + default: + break; + } + return SwarmSolver::getResourceString(pResId); + } + + // XServiceInfo + virtual OUString SAL_CALL getImplementationName() override + { + return "com.sun.star.comp.Calc.SwarmSolver"; + } + + sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override + { + return cppu::supportsService(this, rServiceName); + } + + uno::Sequence<OUString> SAL_CALL getSupportedServiceNames() override + { + return { "com.sun.star.sheet.Solver" }; + } + +private: + void applyVariables(std::vector<double> const& rVariables); + bool doesViolateConstraints(); + +public: + double calculateFitness(std::vector<double> const& rVariables); + size_t getDimensionality() const; + void initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator); + double clampVariable(size_t nVarIndex, double fValue); + double boundVariable(size_t nVarIndex, double fValue); +}; +} + +OUString SwarmSolver::getResourceString(TranslateId aId) +{ + if (!aId) + return OUString(); + + return Translate::get(aId, Translate::Create("scc")); +} + +uno::Reference<table::XCell> SwarmSolver::getCell(const table::CellAddress& rPosition) +{ + uno::Reference<container::XIndexAccess> xSheets(mxDocument->getSheets(), uno::UNO_QUERY); + uno::Reference<sheet::XSpreadsheet> xSheet(xSheets->getByIndex(rPosition.Sheet), + uno::UNO_QUERY); + return xSheet->getCellByPosition(rPosition.Column, rPosition.Row); +} + +void SwarmSolver::setValue(const table::CellAddress& rPosition, double fValue) +{ + getCell(rPosition)->setValue(fValue); +} + +double SwarmSolver::getValue(const table::CellAddress& rPosition) +{ + return getCell(rPosition)->getValue(); +} + +IMPLEMENT_FORWARD_XINTERFACE2(SwarmSolver, SwarmSolver_Base, OPropertyContainer) +IMPLEMENT_FORWARD_XTYPEPROVIDER2(SwarmSolver, SwarmSolver_Base, OPropertyContainer) + +void SwarmSolver::applyVariables(std::vector<double> const& rVariables) +{ + for (sal_Int32 i = 0; i < maVariables.getLength(); ++i) + { + setValue(maVariables[i], rVariables[i]); + } +} + +double SwarmSolver::calculateFitness(std::vector<double> const& rVariables) +{ + applyVariables(rVariables); + + if (doesViolateConstraints()) + return std::numeric_limits<float>::lowest(); + + double x = getValue(maObjective); + + if (mbMaximize) + return x; + else + return -x; +} + +void SwarmSolver::initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator) +{ + int nTry = 1; + bool bConstraintsOK = false; + + while (!bConstraintsOK && nTry < 10) + { + size_t noVariables(maVariables.getLength()); + + rVariables.resize(noVariables); + + for (size_t i = 0; i < noVariables; ++i) + { + Bound const& rBound = maBounds[i]; + if (mbInteger) + { + sal_Int64 intLower(rBound.lower); + sal_Int64 intUpper(rBound.upper); + std::uniform_int_distribution<sal_Int64> random(intLower, intUpper); + rVariables[i] = double(random(rGenerator)); + } + else + { + std::uniform_real_distribution<double> random(rBound.lower, rBound.upper); + rVariables[i] = random(rGenerator); + } + } + + applyVariables(rVariables); + + bConstraintsOK = !doesViolateConstraints(); + nTry++; + } +} + +double SwarmSolver::clampVariable(size_t nVarIndex, double fValue) +{ + Bound const& rBound = maBounds[nVarIndex]; + double fResult = std::clamp(fValue, rBound.lower, rBound.upper); + + if (mbInteger) + return std::trunc(fResult); + + return fResult; +} + +double SwarmSolver::boundVariable(size_t nVarIndex, double fValue) +{ + Bound const& rBound = maBounds[nVarIndex]; + // double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower); + double fResult = fValue; + while (fResult < rBound.lower || fResult > rBound.upper) + { + if (fResult < rBound.lower) + fResult = rBound.upper - (rBound.lower - fResult); + if (fResult > rBound.upper) + fResult = (fResult - rBound.upper) + rBound.lower; + } + + if (mbInteger) + return std::trunc(fResult); + + return fResult; +} + +size_t SwarmSolver::getDimensionality() const { return maVariables.getLength(); } + +bool SwarmSolver::doesViolateConstraints() +{ + for (const sheet::SolverConstraint& rConstraint : maNonBoundedConstraints) + { + double fLeftValue = getValue(rConstraint.Left); + double fRightValue = 0.0; + + table::CellAddress aCellAddress; + + if (rConstraint.Right >>= aCellAddress) + { + fRightValue = getValue(aCellAddress); + } + else if (rConstraint.Right >>= fRightValue) + { + // empty + } + else + { + return false; + } + + sheet::SolverConstraintOperator eOp = rConstraint.Operator; + switch (eOp) + { + case sheet::SolverConstraintOperator_LESS_EQUAL: + { + if (fLeftValue > fRightValue) + return true; + } + break; + case sheet::SolverConstraintOperator_GREATER_EQUAL: + { + if (fLeftValue < fRightValue) + return true; + } + break; + case sheet::SolverConstraintOperator_EQUAL: + { + if (!rtl::math::approxEqual(fLeftValue, fRightValue)) + return true; + } + break; + default: + break; + } + } + return false; +} + +namespace +{ +template <typename SwarmAlgorithm> class SwarmRunner +{ +private: + SwarmAlgorithm& mrAlgorithm; + double mfTimeout; + + static constexpr size_t mnPopulationSize = 40; + static constexpr int constNumberOfGenerationsWithoutChange = 50; + + std::chrono::high_resolution_clock::time_point maStart; + std::chrono::high_resolution_clock::time_point maEnd; + +public: + SwarmRunner(SwarmAlgorithm& rAlgorithm) + : mrAlgorithm(rAlgorithm) + , mfTimeout(5000) + { + } + + void setTimeout(double fTimeout) { mfTimeout = fTimeout; } + + std::vector<double> const& solve() + { + using std::chrono::duration_cast; + using std::chrono::high_resolution_clock; + using std::chrono::milliseconds; + + mrAlgorithm.initialize(); + + maEnd = maStart = high_resolution_clock::now(); + + int nLastChange = 0; + + while ((mrAlgorithm.getGeneration() - nLastChange) < constNumberOfGenerationsWithoutChange + && duration_cast<milliseconds>(maEnd - maStart).count() < mfTimeout) + { + bool bChange = mrAlgorithm.next(); + + if (bChange) + nLastChange = mrAlgorithm.getGeneration(); + + maEnd = high_resolution_clock::now(); + } + return mrAlgorithm.getResult(); + } +}; +} + +void SAL_CALL SwarmSolver::solve() +{ + uno::Reference<frame::XModel> xModel(mxDocument, uno::UNO_QUERY_THROW); + + maStatus.clear(); + mbSuccess = false; + if (!maVariables.getLength()) + return; + + maBounds.resize(maVariables.getLength()); + + xModel->lockControllers(); + + if (mbNonNegative) + { + for (Bound& rBound : maBounds) + rBound.lower = 0; + } + + // Determine variable bounds + for (sheet::SolverConstraint const& rConstraint : std::as_const(maConstraints)) + { + table::CellAddress aLeftCellAddress = rConstraint.Left; + sheet::SolverConstraintOperator eOp = rConstraint.Operator; + + size_t index = 0; + bool bFoundVariable = false; + for (const table::CellAddress& rVariableCell : std::as_const(maVariables)) + { + if (aLeftCellAddress == rVariableCell) + { + bFoundVariable = true; + table::CellAddress aCellAddress; + double fValue; + + if (rConstraint.Right >>= aCellAddress) + { + uno::Reference<table::XCell> xCell = getCell(aCellAddress); + if (xCell->getType() == table::CellContentType_VALUE) + { + maBounds[index].updateBound(eOp, xCell->getValue()); + } + else + { + maNonBoundedConstraints.push_back(rConstraint); + } + } + else if (rConstraint.Right >>= fValue) + { + maBounds[index].updateBound(eOp, fValue); + } + } + index++; + } + if (!bFoundVariable) + maNonBoundedConstraints.push_back(rConstraint); + } + + std::vector<double> aSolution; + + if (mnAlgorithm == 0) + { + DifferentialEvolutionAlgorithm<SwarmSolver> aDE(*this, 50); + SwarmRunner<DifferentialEvolutionAlgorithm<SwarmSolver>> aEvolution(aDE); + aEvolution.setTimeout(mnTimeout); + aSolution = aEvolution.solve(); + } + else + { + ParticleSwarmOptimizationAlgorithm<SwarmSolver> aPSO(*this, 100); + SwarmRunner<ParticleSwarmOptimizationAlgorithm<SwarmSolver>> aSwarmSolver(aPSO); + aSwarmSolver.setTimeout(mnTimeout); + aSolution = aSwarmSolver.solve(); + } + + xModel->unlockControllers(); + + mbSuccess = true; + + maSolution.realloc(aSolution.size()); + std::copy(aSolution.begin(), aSolution.end(), maSolution.getArray()); +} + +extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface* +com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*, + uno::Sequence<uno::Any> const&) +{ + return cppu::acquire(new SwarmSolver()); +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |