From 08404bbb90a8978b70698ef057a4a46ad4fceae3 Mon Sep 17 00:00:00 2001 From: Tomaž Vajngerl Date: Mon, 6 Nov 2017 00:54:25 +0100 Subject: Swarm based (uses PSO or DE) experimental non-linear solver MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This is a new, simple non-linear solver that uses a swarm (population) to do global optimization. It uses two algoritms - Particle Swarm Optimization (PSO) or Differential Evolution (DE) to find a (non-optimal) solution. It is experimental as not all functions are implemented and it needs a lot more testing so that it performs well. Change-Id: If55dad7eda17394851a9d178ad892de771eca7c9 Reviewed-on: https://gerrit.libreoffice.org/44382 Tested-by: Jenkins Reviewed-by: Tomaž Vajngerl --- sccomp/CppunitTest_sccomp_swarmsolvertest.mk | 71 +++ sccomp/Library_solver.mk | 3 + sccomp/Module_sccomp.mk | 1 + sccomp/inc/strings.hrc | 2 + sccomp/qa/unit/SwarmSolverTest.cxx | 399 ++++++++++++++ sccomp/qa/unit/data/MultiVariable.ods | Bin 0 -> 7754 bytes sccomp/qa/unit/data/Simple.ods | Bin 0 -> 21518 bytes sccomp/qa/unit/data/TwoVariables.ods | Bin 0 -> 7449 bytes sccomp/source/solver/DifferentialEvolution.hxx | 164 ++++++ sccomp/source/solver/ParticelSwarmOptimization.hxx | 178 +++++++ sccomp/source/solver/SwarmSolver.cxx | 591 +++++++++++++++++++++ sccomp/source/solver/swarmsolver.component | 15 + 12 files changed, 1424 insertions(+) create mode 100644 sccomp/CppunitTest_sccomp_swarmsolvertest.mk create mode 100644 sccomp/qa/unit/SwarmSolverTest.cxx create mode 100644 sccomp/qa/unit/data/MultiVariable.ods create mode 100644 sccomp/qa/unit/data/Simple.ods create mode 100644 sccomp/qa/unit/data/TwoVariables.ods create mode 100644 sccomp/source/solver/DifferentialEvolution.hxx create mode 100644 sccomp/source/solver/ParticelSwarmOptimization.hxx create mode 100644 sccomp/source/solver/SwarmSolver.cxx create mode 100644 sccomp/source/solver/swarmsolver.component (limited to 'sccomp') diff --git a/sccomp/CppunitTest_sccomp_swarmsolvertest.mk b/sccomp/CppunitTest_sccomp_swarmsolvertest.mk new file mode 100644 index 000000000000..f4114b2cd5e7 --- /dev/null +++ b/sccomp/CppunitTest_sccomp_swarmsolvertest.mk @@ -0,0 +1,71 @@ +# -*- Mode: makefile-gmake; tab-width: 4; indent-tabs-mode: t -*- +# +# 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/. +# + +$(eval $(call gb_CppunitTest_CppunitTest,swarm_solver_test)) + +$(eval $(call gb_CppunitTest_add_exception_objects,swarm_solver_test,\ + sccomp/qa/unit/SwarmSolverTest \ +)) + +$(eval $(call gb_CppunitTest_use_externals,swarm_solver_test,\ + boost_headers \ +)) + +$(eval $(call gb_CppunitTest_use_libraries,swarm_solver_test,\ + basegfx \ + comphelper \ + cppu \ + cppuhelper \ + drawinglayer \ + editeng \ + for \ + forui \ + i18nlangtag \ + msfilter \ + oox \ + sal \ + salhelper \ + sax \ + sb \ + sc \ + scqahelper \ + sfx \ + sot \ + subsequenttest \ + svl \ + svt \ + svx \ + svxcore \ + test \ + tk \ + tl \ + ucbhelper \ + unotest \ + utl \ + vbahelper \ + vcl \ + xo \ + $(gb_UWINAPI) \ +)) + +$(eval $(call gb_CppunitTest_set_include,swarm_solver_test,\ + -I$(SRCDIR)/sc/inc \ + $$(INCLUDE) \ +)) + +$(eval $(call gb_CppunitTest_use_sdk_api,swarm_solver_test)) + +$(eval $(call gb_CppunitTest_use_ure,swarm_solver_test)) +$(eval $(call gb_CppunitTest_use_vcl,swarm_solver_test)) + +$(eval $(call gb_CppunitTest_use_rdb,swarm_solver_test,services)) + +$(eval $(call gb_CppunitTest_use_configuration,swarm_solver_test)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/Library_solver.mk b/sccomp/Library_solver.mk index 3339c0ed70df..e23ecac7a5bb 100644 --- a/sccomp/Library_solver.mk +++ b/sccomp/Library_solver.mk @@ -22,6 +22,8 @@ $(eval $(call gb_Library_Library,solver)) $(if $(ENABLE_COINMP),$(eval $(call gb_Library_set_componentfile,solver,sccomp/source/solver/coinmpsolver))) $(if $(ENABLE_LPSOLVE),$(eval $(call gb_Library_set_componentfile,solver,sccomp/source/solver/lpsolvesolver))) +$(eval $(call gb_Library_set_componentfile,solver,sccomp/source/solver/swarmsolver)) + $(eval $(call gb_Library_use_sdk_api,solver)) $(eval $(call gb_Library_set_include,solver,\ @@ -45,6 +47,7 @@ $(eval $(call gb_Library_use_externals,solver,\ )) $(eval $(call gb_Library_add_exception_objects,solver,\ + sccomp/source/solver/SwarmSolver \ sccomp/source/solver/SolverComponent \ $(if $(ENABLE_COINMP), sccomp/source/solver/CoinMPSolver) \ $(if $(ENABLE_LPSOLVE), sccomp/source/solver/LpsolveSolver) \ diff --git a/sccomp/Module_sccomp.mk b/sccomp/Module_sccomp.mk index 318e9d69f484..97b0c2fe356f 100644 --- a/sccomp/Module_sccomp.mk +++ b/sccomp/Module_sccomp.mk @@ -29,6 +29,7 @@ $(eval $(call gb_Module_add_l10n_targets,sccomp,\ $(eval $(call gb_Module_add_check_targets,sccomp,\ CppunitTest_sccomp_solver \ + CppunitTest_sccomp_swarmsolvertest \ )) # vim: set noet sw=4 ts=4: diff --git a/sccomp/inc/strings.hrc b/sccomp/inc/strings.hrc index 4f736374e619..ad6c095e68af 100644 --- a/sccomp/inc/strings.hrc +++ b/sccomp/inc/strings.hrc @@ -24,11 +24,13 @@ #define RID_SOLVER_COMPONENT NC_("RID_SOLVER_COMPONENT", "%PRODUCTNAME Linear Solver") #define RID_COINMP_SOLVER_COMPONENT NC_("RID_COINMP_SOLVER_COMPONENT", "%PRODUCTNAME CoinMP Linear Solver") +#define RID_SWARM_SOLVER_COMPONENT NC_("RID_SWARM_SOLVER_COMPONENT", "%PRODUCTNAME Swarm Non-Linear Solver (experimental)") #define RID_PROPERTY_NONNEGATIVE NC_("RID_PROPERTY_NONNEGATIVE", "Assume variables as non-negative") #define RID_PROPERTY_INTEGER NC_("RID_PROPERTY_INTEGER", "Assume variables as integer") #define RID_PROPERTY_TIMEOUT NC_("RID_PROPERTY_TIMEOUT", "Solving time limit (seconds)") #define RID_PROPERTY_EPSILONLEVEL NC_("RID_PROPERTY_EPSILONLEVEL", "Epsilon level (0-3)") #define RID_PROPERTY_LIMITBBDEPTH NC_("RID_PROPERTY_LIMITBBDEPTH", "Limit branch-and-bound depth") +#define RID_PROPERTY_ALGORITHM NC_("RID_PROPERTY_ALGORITHM", "Swarm algorithm (0 - Differential Evolution, 1 - Particle Swarm Optimization)") #define RID_ERROR_NONLINEAR NC_("RID_ERROR_NONLINEAR", "The model is not linear.") #define RID_ERROR_EPSILONLEVEL NC_("RID_ERROR_EPSILONLEVEL", "The epsilon level is invalid.") #define RID_ERROR_INFEASIBLE NC_("RID_ERROR_INFEASIBLE", "The model is infeasible. Check limiting conditions.") diff --git a/sccomp/qa/unit/SwarmSolverTest.cxx b/sccomp/qa/unit/SwarmSolverTest.cxx new file mode 100644 index 000000000000..18553471ba19 --- /dev/null +++ b/sccomp/qa/unit/SwarmSolverTest.cxx @@ -0,0 +1,399 @@ +/* -*- 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 + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#include + +using namespace css; + +namespace +{ + +class SwarmSolverTest : public CalcUnoApiTest +{ + uno::Reference mxComponent; + void testUnconstrained(); + void testVariableBounded(); + void testVariableConstrained(); + void testTwoVariables(); + void testMultipleVariables(); + +public: + SwarmSolverTest() + : CalcUnoApiTest("sccomp/qa/unit/data") + { + } + + virtual void tearDown() override; + + CPPUNIT_TEST_SUITE(SwarmSolverTest); + CPPUNIT_TEST(testUnconstrained); + CPPUNIT_TEST(testVariableBounded); + CPPUNIT_TEST(testVariableConstrained); + CPPUNIT_TEST(testMultipleVariables); + CPPUNIT_TEST(testTwoVariables); + CPPUNIT_TEST_SUITE_END(); +}; + +void SwarmSolverTest::tearDown() +{ + if (mxComponent.is()) + closeDocument(mxComponent); +} + +void SwarmSolverTest::testUnconstrained() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL("Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is()); + + uno::Reference xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference xCell; + + uno::Reference xSolver; + OUString sSolverName("com.sun.star.comp.Calc.SwarmSolver"); + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext(sSolverName, m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence aVariables(1); + aVariables[0] = table::CellAddress(0, 1, 0); + + // constraints + uno::Sequence aConstraints; + + // initialize solver + xSolver->setDocument(xDocument); + xSolver->setObjective(aObjective); + xSolver->setVariables(aVariables); + xSolver->setConstraints(aConstraints); + xSolver->setMaximize(false); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aSolution.getLength(), aVariables.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(3.0, aSolution[0], 1E-5); +} + +void SwarmSolverTest::testVariableBounded() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL("Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is()); + + uno::Reference xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference xCell; + + uno::Reference xSolver; + OUString sSolverName("com.sun.star.comp.Calc.SwarmSolver"); + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext(sSolverName, m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence aVariables(1); + aVariables[0] = table::CellAddress(0, 1, 0); + + // constraints + uno::Sequence aConstraints(2); + aConstraints[0].Left = table::CellAddress(0, 1, 0); + aConstraints[0].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[0].Right <<= 100.0; + + aConstraints[1].Left = table::CellAddress(0, 1, 0); + aConstraints[1].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[1].Right <<= -100.0; + + // initialize solver + xSolver->setDocument(xDocument); + xSolver->setObjective(aObjective); + xSolver->setVariables(aVariables); + xSolver->setConstraints(aConstraints); + xSolver->setMaximize(false); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aSolution.getLength(), aVariables.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(3.0, aSolution[0], 1E-5); +} + +void SwarmSolverTest::testVariableConstrained() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL("Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is()); + + uno::Reference xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference xCell; + + uno::Reference xSolver; + OUString sSolverName("com.sun.star.comp.Calc.SwarmSolver"); + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext(sSolverName, m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence aVariables(1); + aVariables[0] = table::CellAddress(0, 1, 0); + + // constraints + uno::Sequence aConstraints(3); + aConstraints[0].Left = table::CellAddress(0, 1, 0); + aConstraints[0].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[0].Right <<= -50000.0; + + aConstraints[1].Left = table::CellAddress(0, 1, 0); + aConstraints[1].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[1].Right <<= 0.0; + + aConstraints[2].Left = table::CellAddress(0, 1, 1); + aConstraints[2].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[2].Right <<= 10.0; + + // initialize solver + xSolver->setDocument(xDocument); + xSolver->setObjective(aObjective); + xSolver->setVariables(aVariables); + xSolver->setConstraints(aConstraints); + xSolver->setMaximize(false); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aSolution.getLength(), aVariables.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(-0.741657, aSolution[0], 1E-5); +} + +void SwarmSolverTest::testTwoVariables() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL("TwoVariables.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is()); + + uno::Reference xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference xCell; + + uno::Reference xSolver; + OUString sSolverName("com.sun.star.comp.Calc.SwarmSolver"); + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext(sSolverName, m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 5); + + // "changing cells" - unknown variables + uno::Sequence aVariables(2); + aVariables[0] = table::CellAddress(0, 1, 2); + aVariables[1] = table::CellAddress(0, 1, 3); + + // constraints + uno::Sequence aConstraints(4); + + aConstraints[0].Left = table::CellAddress(0, 1, 2); + aConstraints[0].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[0].Right <<= -100.0; + + aConstraints[1].Left = table::CellAddress(0, 1, 3); + aConstraints[1].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[1].Right <<= -100.0; + + aConstraints[2].Left = table::CellAddress(0, 1, 2); + aConstraints[2].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[2].Right <<= 100.0; + + aConstraints[3].Left = table::CellAddress(0, 1, 3); + aConstraints[3].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[3].Right <<= 100.0; + + // initialize solver + xSolver->setDocument(xDocument); + xSolver->setObjective(aObjective); + xSolver->setVariables(aVariables); + xSolver->setConstraints(aConstraints); + xSolver->setMaximize(true); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(0.666667, aSolution[0], 1E-5); + CPPUNIT_ASSERT_DOUBLES_EQUAL(-1.666667, aSolution[1], 1E-5); +} + +void SwarmSolverTest::testMultipleVariables() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL("MultiVariable.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is()); + + uno::Reference xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference xCell; + + uno::Reference xSolver; + OUString sSolverName("com.sun.star.comp.Calc.SwarmSolver"); + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext(sSolverName, m_xContext), + uno::UNO_QUERY_THROW); + + uno::Reference xPropSet(xSolver, uno::UNO_QUERY_THROW); + xPropSet->setPropertyValue("Integer", uno::makeAny(true)); + + table::CellAddress aObjective(0, 5, 7); + + // "changing cells" - unknown variables + uno::Sequence aVariables(4); + aVariables[0] = table::CellAddress(0, 6, 1); + aVariables[1] = table::CellAddress(0, 6, 2); + aVariables[2] = table::CellAddress(0, 6, 3); + aVariables[3] = table::CellAddress(0, 6, 4); + + // constraints + uno::Sequence aConstraints(12); + + aConstraints[0].Left = table::CellAddress(0, 1, 5); + aConstraints[0].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[0].Right <<= table::CellAddress(0, 1, 6); + + aConstraints[1].Left = table::CellAddress(0, 2, 5); + aConstraints[1].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[1].Right <<= table::CellAddress(0, 2, 6); + + aConstraints[2].Left = table::CellAddress(0, 3, 5); + aConstraints[2].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[2].Right <<= table::CellAddress(0, 3, 6); + + aConstraints[3].Left = table::CellAddress(0, 4, 5); + aConstraints[3].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[3].Right <<= table::CellAddress(0, 4, 6); + + aConstraints[4].Left = table::CellAddress(0, 6, 1); + aConstraints[4].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[4].Right <<= 0.0; + + aConstraints[5].Left = table::CellAddress(0, 6, 2); + aConstraints[5].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[5].Right <<= 0.0; + + aConstraints[6].Left = table::CellAddress(0, 6, 3); + aConstraints[6].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[6].Right <<= 0.0; + + aConstraints[7].Left = table::CellAddress(0, 6, 4); + aConstraints[7].Operator = sheet::SolverConstraintOperator_GREATER_EQUAL; + aConstraints[7].Right <<= 0.0; + + aConstraints[8].Left = table::CellAddress(0, 6, 1); + aConstraints[8].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[8].Right <<= 10000.0; + + aConstraints[9].Left = table::CellAddress(0, 6, 2); + aConstraints[9].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[9].Right <<= 10000.0; + + aConstraints[10].Left = table::CellAddress(0, 6, 3); + aConstraints[10].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[10].Right <<= 10000.0; + + aConstraints[11].Left = table::CellAddress(0, 6, 4); + aConstraints[11].Operator = sheet::SolverConstraintOperator_LESS_EQUAL; + aConstraints[11].Right <<= 10000.0; + + // initialize solver + xSolver->setDocument(xDocument); + xSolver->setObjective(aObjective); + xSolver->setVariables(aVariables); + xSolver->setConstraints(aConstraints); + xSolver->setMaximize(false); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); +#ifndef _WIN32 + // Disable on windows for now, needs algorithm stability improvements + CPPUNIT_ASSERT_DOUBLES_EQUAL(0.0, aSolution[0], 1E-5); + CPPUNIT_ASSERT_DOUBLES_EQUAL(3.0, aSolution[1], 1E-5); + CPPUNIT_ASSERT_DOUBLES_EQUAL(1.0, aSolution[2], 1E-5); + CPPUNIT_ASSERT_DOUBLES_EQUAL(0.0, aSolution[3], 1E-5); +#endif +} + +CPPUNIT_TEST_SUITE_REGISTRATION(SwarmSolverTest); +} + +CPPUNIT_PLUGIN_IMPLEMENT(); + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/qa/unit/data/MultiVariable.ods b/sccomp/qa/unit/data/MultiVariable.ods new file mode 100644 index 000000000000..1e9db736a8fb Binary files /dev/null and b/sccomp/qa/unit/data/MultiVariable.ods differ diff --git a/sccomp/qa/unit/data/Simple.ods b/sccomp/qa/unit/data/Simple.ods new file mode 100644 index 000000000000..2ac8224c0702 Binary files /dev/null and b/sccomp/qa/unit/data/Simple.ods differ diff --git a/sccomp/qa/unit/data/TwoVariables.ods b/sccomp/qa/unit/data/TwoVariables.ods new file mode 100644 index 000000000000..c27e362e011a Binary files /dev/null and b/sccomp/qa/unit/data/TwoVariables.ods differ diff --git a/sccomp/source/solver/DifferentialEvolution.hxx b/sccomp/source/solver/DifferentialEvolution.hxx new file mode 100644 index 000000000000..7d37ef82b9f8 --- /dev/null +++ b/sccomp/source/solver/DifferentialEvolution.hxx @@ -0,0 +1,164 @@ +/* -*- 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/. + * + */ + +#ifndef INCLUDED_SCCOMP_SOURCE_DIFFERENTIALEVOLUTION_HXX +#define INCLUDED_SCCOMP_SOURCE_DIFFERENTIALEVOLUTION_HXX + +#include +#include +#include + +struct Individual +{ + std::vector mVariables; +}; + +template class DifferentialEvolutionAlgorithm +{ + static constexpr double mnDifferentialWeight = 0.5; // [0, 2] + static constexpr double mnCrossoverProbability = 0.9; // [0, 1] + + static constexpr double constAcceptedPrecision = 0.000000001; + + DataProvider& mrDataProvider; + + size_t mnPopulationSize; + std::vector maPopulation; + + std::random_device maRandomDevice; + std::mt19937 maGenerator; + size_t mnDimensionality; + + std::uniform_int_distribution<> maRandomPopulation; + std::uniform_int_distribution<> maRandomDimensionality; + std::uniform_real_distribution<> maRandom01; + + Individual maBestCandidate; + double mfBestFitness; + int mnGeneration; + int mnLastChange; + +public: + DifferentialEvolutionAlgorithm(DataProvider& rDataProvider, size_t nPopulationSize) + : mrDataProvider(rDataProvider) + , mnPopulationSize(nPopulationSize) + , maGenerator(maRandomDevice()) + , mnDimensionality(mrDataProvider.getDimensionality()) + , maRandomPopulation(0, mnPopulationSize - 1) + , maRandomDimensionality(0, mnDimensionality - 1) + , maRandom01(0.0, 1.0) + , mfBestFitness(std::numeric_limits::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector const& getResult() { return maBestCandidate.mVariables; } + + int getGeneration() { return mnGeneration; } + + int getLastChange() { return mnLastChange; } + + void initialize() + { + mnGeneration = 0; + mnLastChange = 0; + maPopulation.clear(); + maBestCandidate.mVariables.clear(); + + // Initialize population with individuals that have been initialized with uniform random + // noise + // uniform noise means random value inside your search space + for (size_t i = 0; i < mnPopulationSize; ++i) + { + maPopulation.emplace_back(); + Individual& rIndividual = maPopulation.back(); + mrDataProvider.initializeVariables(rIndividual.mVariables, maGenerator); + } + } + + // Calculate one generation + bool next() + { + bool bBestChanged = false; + + for (size_t agentIndex = 0; agentIndex < mnPopulationSize; ++agentIndex) + { + // calculate new candidate solution + + // pick random point from population + size_t x = agentIndex; // randomPopulation(generator); + size_t a, b, c; + + // create a copy of choosen random agent in population + Individual& rOriginal = maPopulation[x]; + Individual aCandidate(rOriginal); + + // pick three different random points from population + do + { + a = maRandomPopulation(maGenerator); + } while (a == x); + + do + { + b = maRandomPopulation(maGenerator); + } while (b == x || b == a); + + do + { + c = maRandomPopulation(maGenerator); + + } while (c == x || c == a || c == b); + + size_t randomIndex = maRandomDimensionality(maGenerator); + + for (size_t index = 0; index < mnDimensionality; ++index) + { + double randomCrossoverProbability = maRandom01(maGenerator); + if (index == randomIndex || randomCrossoverProbability < mnCrossoverProbability) + { + double fVarA = maPopulation[a].mVariables[index]; + double fVarB = maPopulation[b].mVariables[index]; + double fVarC = maPopulation[c].mVariables[index]; + + double fNewValue = fVarA + mnDifferentialWeight * (fVarB - fVarC); + fNewValue = mrDataProvider.boundVariable(index, fNewValue); + aCandidate.mVariables[index] = fNewValue; + } + } + + double fCandidateFitness = mrDataProvider.calculateFitness(aCandidate.mVariables); + + // see if is better than original, if so replace + if (fCandidateFitness > mrDataProvider.calculateFitness(rOriginal.mVariables)) + { + maPopulation[x] = aCandidate; + + if (fCandidateFitness > mfBestFitness) + { + if (std::abs(fCandidateFitness - mfBestFitness) > constAcceptedPrecision) + { + bBestChanged = true; + mnLastChange = mnGeneration; + } + mfBestFitness = fCandidateFitness; + maBestCandidate = maPopulation[x]; + } + } + } + mnGeneration++; + return bBestChanged; + } +}; + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/ParticelSwarmOptimization.hxx b/sccomp/source/solver/ParticelSwarmOptimization.hxx new file mode 100644 index 000000000000..6c820ab7978c --- /dev/null +++ b/sccomp/source/solver/ParticelSwarmOptimization.hxx @@ -0,0 +1,178 @@ +/* -*- 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/. + * + */ + +#ifndef INCLUDED_SCCOMP_SOURCE_PARTICLESWARM_HXX +#define INCLUDED_SCCOMP_SOURCE_PARTICLESWARM_HXX + +#include +#include +#include + +struct Particle +{ + Particle(size_t nDimensionality) + : mVelocity(nDimensionality) + , mPosition(nDimensionality) + , mCurrentFitness(std::numeric_limits::lowest()) + , mBestPosition(nDimensionality) + , mBestFitness(std::numeric_limits::lowest()) + { + } + + std::vector mVelocity; + + std::vector mPosition; + double mCurrentFitness; + + std::vector mBestPosition; + double mBestFitness; +}; + +template class ParticleSwarmOptimizationAlgorithm +{ +private: + // inertia + static constexpr double constWeight = 0.729; + // cognitive coefficient + static constexpr double c1 = 1.49445; + // social coefficient + static constexpr double c2 = 1.49445; + + static constexpr double constAcceptedPrecision = 0.000000001; + + DataProvider& mrDataProvider; + + size_t mnNumOfParticles; + + std::vector maSwarm; + + std::random_device maRandomDevice; + std::mt19937 maGenerator; + size_t mnDimensionality; + + std::uniform_real_distribution<> maRandom01; + + std::vector maBestPosition; + double mfBestFitness; + int mnGeneration; + int mnLastChange; + +public: + ParticleSwarmOptimizationAlgorithm(DataProvider& rDataProvider, size_t nNumOfParticles) + : mrDataProvider(rDataProvider) + , mnNumOfParticles(nNumOfParticles) + , maGenerator(maRandomDevice()) + , mnDimensionality(mrDataProvider.getDimensionality()) + , maRandom01(0.0, 1.0) + , maBestPosition(mnDimensionality) + , mfBestFitness(std::numeric_limits::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector const& getResult() { return maBestPosition; } + + int getGeneration() { return mnGeneration; } + + int getLastChange() { return mnLastChange; } + + void initialize() + { + mnGeneration = 0; + mnLastChange = 0; + maSwarm.clear(); + + mfBestFitness = std::numeric_limits::lowest(); + + for (size_t i = 0; i < mnNumOfParticles; i++) + { + maSwarm.emplace_back(mnDimensionality); + Particle& rParticle = maSwarm.back(); + + mrDataProvider.initializeVariables(rParticle.mPosition, maGenerator); + mrDataProvider.initializeVariables(rParticle.mVelocity, maGenerator); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + rParticle.mCurrentFitness = mrDataProvider.calculateFitness(rParticle.mPosition); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + rParticle.mBestPosition.begin()); + rParticle.mBestFitness = rParticle.mCurrentFitness; + + if (rParticle.mCurrentFitness > mfBestFitness) + { + mfBestFitness = rParticle.mCurrentFitness; + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + maBestPosition.begin()); + } + } + } + + bool next() + { + bool bBestChanged = false; + + for (Particle& rParticle : maSwarm) + { + double fRandom1 = maRandom01(maGenerator); + double fRandom2 = maRandom01(maGenerator); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mVelocity[k] + = (constWeight * rParticle.mVelocity[k]) + + (c1 * fRandom1 * (rParticle.mBestPosition[k] - rParticle.mPosition[k])) + + (c2 * fRandom2 * (maBestPosition[k] - rParticle.mPosition[k])); + + mrDataProvider.clampVariable(k, rParticle.mVelocity[k]); + + rParticle.mPosition[k] += rParticle.mVelocity[k]; + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + rParticle.mCurrentFitness = mrDataProvider.calculateFitness(rParticle.mPosition); + + if (rParticle.mCurrentFitness > rParticle.mBestFitness) + { + rParticle.mBestFitness = rParticle.mCurrentFitness; + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + rParticle.mBestPosition.begin()); + } + + if (rParticle.mCurrentFitness > mfBestFitness) + { + if (std::abs(rParticle.mCurrentFitness - mfBestFitness) > constAcceptedPrecision) + { + bBestChanged = true; + mnLastChange = mnGeneration; + } + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + maBestPosition.begin()); + mfBestFitness = rParticle.mCurrentFitness; + } + } + mnGeneration++; + return bBestChanged; + } +}; + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/SwarmSolver.cxx b/sccomp/source/solver/SwarmSolver.cxx new file mode 100644 index 000000000000..809ebb4fde96 --- /dev/null +++ b/sccomp/source/solver/SwarmSolver.cxx @@ -0,0 +1,591 @@ +/* -*- 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 +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +#include +#include +#include + +#include +#include +#include +#include +#include + +#include + +#include "DifferentialEvolution.hxx" +#include "ParticelSwarmOptimization.hxx" + +#include + +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::lowest()) + , upper(std::numeric_limits::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 + SwarmSolver_Base; + +class SwarmSolver : public comphelper::OMutexAndBroadcastHelper, + public comphelper::OPropertyContainer, + public comphelper::OPropertyArrayUsageHelper, + public SwarmSolver_Base +{ +private: + uno::Reference mxDocument; + table::CellAddress maObjective; + uno::Sequence maVariables; + uno::Sequence maConstraints; + bool mbMaximize; + + // set via XPropertySet + bool mbNonNegative; + bool mbInteger; + sal_Int32 mnTimeout; + sal_Int32 mnAlgorithm; + + // results + bool mbSuccess; + double mfResultValue; + + uno::Sequence maSolution; + OUString maStatus; + + std::vector maBounds; + std::vector maNonBoundedConstraints; + +private: + static OUString getResourceString(const char* pId); + + uno::Reference 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::get()); + registerProperty("Integer", PROP_INTEGER, 0, &mbInteger, + cppu::UnoType::get()); + registerProperty("Timeout", PROP_TIMEOUT, 0, &mnTimeout, + cppu::UnoType::get()); + registerProperty("Algorithm", PROP_ALGORITHM, 0, &mnAlgorithm, + cppu::UnoType::get()); + } + + DECLARE_XINTERFACE() + DECLARE_XTYPEPROVIDER() + + virtual uno::Reference 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 aProperties; + describeProperties(aProperties); + return new cppu::OPropertyArrayHelper(aProperties); + } + + // XSolver + virtual uno::Reference SAL_CALL getDocument() override + { + return mxDocument; + } + virtual void SAL_CALL + setDocument(const uno::Reference& 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 SAL_CALL getVariables() override + { + return maVariables; + } + virtual void SAL_CALL setVariables(const uno::Sequence& rVariables) override + { + maVariables = rVariables; + } + + virtual uno::Sequence SAL_CALL getConstraints() override + { + return maConstraints; + } + virtual void SAL_CALL + setConstraints(const uno::Sequence& 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 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 + { + const char* pResId = nullptr; + 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 OUString("com.sun.star.comp.Calc.SwarmSolver"); + } + + sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override + { + return cppu::supportsService(this, rServiceName); + } + + uno::Sequence SAL_CALL getSupportedServiceNames() override + { + uno::Sequence aServiceNames{ "com.sun.star.sheet.Solver" }; + return aServiceNames; + } + +private: + void applyVariables(std::vector const& rVariables); + bool doesViolateConstraints(); + +public: + double calculateFitness(std::vector const& rVariables); + size_t getDimensionality(); + void initializeVariables(std::vector& rVariables, std::mt19937& rGenerator); + double clampVariable(size_t nVarIndex, double fValue); + double boundVariable(size_t nVarIndex, double fValue); +}; + +OUString SwarmSolver::getResourceString(const char* pId) +{ + OUString sString; + if (!pId) + return sString; + + static std::locale aLocale = Translate::Create("scc"); + return Translate::get(pId, aLocale); +} + +uno::Reference SwarmSolver::getCell(const table::CellAddress& rPosition) +{ + uno::Reference xSheets(mxDocument->getSheets(), uno::UNO_QUERY); + uno::Reference 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 const& rVariables) +{ + for (sal_Int32 i = 0; i < maVariables.getLength(); ++i) + { + setValue(maVariables[i], rVariables[i]); + } +} + +double SwarmSolver::calculateFitness(std::vector const& rVariables) +{ + applyVariables(rVariables); + + if (doesViolateConstraints()) + return std::numeric_limits::lowest(); + + double x = getValue(maObjective); + + if (mbMaximize) + return x; + else + return -x; +} + +void SwarmSolver::initializeVariables(std::vector& 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 random(intLower, intUpper); + rVariables[i] = double(random(rGenerator)); + } + else + { + std::uniform_real_distribution 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::max(std::min(fValue, rBound.upper), rBound.lower); + + if (mbInteger) + return sal_Int64(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 sal_Int64(fResult); + + return fResult; +} + +size_t SwarmSolver::getDimensionality() { return maVariables.getLength(); } + +bool SwarmSolver::doesViolateConstraints() +{ + for (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; +} + +template 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 const& solve() + { + using std::chrono::duration_cast; + using std::chrono::milliseconds; + using std::chrono::high_resolution_clock; + + mrAlgorithm.initialize(); + + maEnd = maStart = high_resolution_clock::now(); + + int nLastChange = 0; + + while ((mrAlgorithm.getGeneration() - nLastChange) < constNumberOfGenerationsWithoutChange + && duration_cast(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 xModel(mxDocument, uno::UNO_QUERY_THROW); + + maStatus.clear(); + mbSuccess = false; + + maBounds.resize(maVariables.getLength()); + + xModel->lockControllers(); + + if (mbNonNegative) + { + for (Bound& rBound : maBounds) + rBound.lower = 0; + } + + // Determine variable bounds + for (sheet::SolverConstraint const& rConstraint : maConstraints) + { + table::CellAddress aLeftCellAddress = rConstraint.Left; + sheet::SolverConstraintOperator eOp = rConstraint.Operator; + + size_t index = 0; + bool bFoundVariable = false; + for (table::CellAddress& rVariableCell : maVariables) + { + if (aLeftCellAddress == rVariableCell) + { + bFoundVariable = true; + table::CellAddress aCellAddress; + double fValue; + + if (rConstraint.Right >>= aCellAddress) + { + uno::Reference 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 aSolution; + + if (mnAlgorithm == 0) + { + DifferentialEvolutionAlgorithm aDE(*this, 50); + SwarmRunner> aEvolution(aDE); + aEvolution.setTimeout(mnTimeout); + aSolution = aEvolution.solve(); + } + else + { + ParticleSwarmOptimizationAlgorithm aPSO(*this, 100); + SwarmRunner> aSwarmSolver(aPSO); + aSwarmSolver.setTimeout(mnTimeout); + aSolution = aSwarmSolver.solve(); + } + + xModel->unlockControllers(); + + mbSuccess = true; + + maSolution.realloc(aSolution.size()); + std::copy(aSolution.begin(), aSolution.end(), maSolution.begin()); +} + +extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface* SAL_CALL +com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*, + uno::Sequence const&) +{ + return cppu::acquire(new SwarmSolver()); +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/swarmsolver.component b/sccomp/source/solver/swarmsolver.component new file mode 100644 index 000000000000..0cdd925ee9fd --- /dev/null +++ b/sccomp/source/solver/swarmsolver.component @@ -0,0 +1,15 @@ + + + + + + + + -- cgit