diff options
Diffstat (limited to '')
24 files changed, 2830 insertions, 0 deletions
diff --git a/sccomp/AllLangMoTarget_scc.mk b/sccomp/AllLangMoTarget_scc.mk new file mode 100644 index 000000000..9bbbb1b5c --- /dev/null +++ b/sccomp/AllLangMoTarget_scc.mk @@ -0,0 +1,13 @@ +# -*- 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_AllLangMoTarget_AllLangMoTarget,scc)) + +$(eval $(call gb_AllLangMoTarget_set_polocation,scc,sccomp)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/CppunitTest_sccomp_solver.mk b/sccomp/CppunitTest_sccomp_solver.mk new file mode 100644 index 000000000..d634fb7d9 --- /dev/null +++ b/sccomp/CppunitTest_sccomp_solver.mk @@ -0,0 +1,47 @@ +# -*- 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,sccomp_solver)) + +$(eval $(call gb_CppunitTest_add_exception_objects,sccomp_solver,\ + sccomp/qa/unit/solver \ +)) + +$(eval $(call gb_CppunitTest_use_externals,sccomp_solver,\ + boost_headers \ +)) + +$(eval $(call gb_CppunitTest_add_defs,sccomp_solver,\ + $(if $(ENABLE_COINMP), -DENABLE_COINMP) \ + $(if $(ENABLE_LPSOLVE), -DENABLE_LPSOLVE) \ +)) + +$(eval $(call gb_CppunitTest_use_libraries,sccomp_solver,\ + cppu \ + sal \ + test \ + unotest \ +)) + +$(eval $(call gb_CppunitTest_set_include,sccomp_solver,\ + -I$(SRCDIR)/sc/inc \ + $$(INCLUDE) \ +)) + + +$(eval $(call gb_CppunitTest_use_sdk_api,sccomp_solver)) + +$(eval $(call gb_CppunitTest_use_ure,sccomp_solver)) +$(eval $(call gb_CppunitTest_use_vcl,sccomp_solver)) + +$(eval $(call gb_CppunitTest_use_rdb,sccomp_solver,services)) + +$(eval $(call gb_CppunitTest_use_configuration,sccomp_solver)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/CppunitTest_sccomp_swarmsolvertest.mk b/sccomp/CppunitTest_sccomp_swarmsolvertest.mk new file mode 100644 index 000000000..38cc3fa39 --- /dev/null +++ b/sccomp/CppunitTest_sccomp_swarmsolvertest.mk @@ -0,0 +1,72 @@ +# -*- 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,sccomp_swarmsolvertest)) + +$(eval $(call gb_CppunitTest_add_exception_objects,sccomp_swarmsolvertest,\ + sccomp/qa/unit/SwarmSolverTest \ +)) + +$(eval $(call gb_CppunitTest_use_externals,sccomp_swarmsolvertest,\ + boost_headers \ +)) + +$(eval $(call gb_CppunitTest_use_libraries,sccomp_swarmsolvertest,\ + 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 \ + $(call gb_Helper_optional,SCRIPTING, \ + vbahelper) \ + vcl \ + xo \ + $(gb_UWINAPI) \ +)) + +$(eval $(call gb_CppunitTest_set_include,sccomp_swarmsolvertest,\ + -I$(SRCDIR)/sc/inc \ + $$(INCLUDE) \ +)) + +$(eval $(call gb_CppunitTest_use_sdk_api,sccomp_swarmsolvertest)) + +$(eval $(call gb_CppunitTest_use_ure,sccomp_swarmsolvertest)) +$(eval $(call gb_CppunitTest_use_vcl,sccomp_swarmsolvertest)) + +$(eval $(call gb_CppunitTest_use_rdb,sccomp_swarmsolvertest,services)) + +$(eval $(call gb_CppunitTest_use_configuration,sccomp_swarmsolvertest)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/IwyuFilter_sccomp.yaml b/sccomp/IwyuFilter_sccomp.yaml new file mode 100644 index 000000000..be2dc6eb4 --- /dev/null +++ b/sccomp/IwyuFilter_sccomp.yaml @@ -0,0 +1,11 @@ +--- +assumeFilename: sccomp/source/solver/SolverComponent.cxx +excludelist: + sccomp/source/solver/SolverComponent.hxx: + # Base class needs full type + - com/sun/star/sheet/XSolver.hpp + - com/sun/star/sheet/XSolverDescription.hpp + - com/sun/star/lang/XServiceInfo.hpp + sccomp/source/solver/SolverComponent.cxx: + # Actually used + - com/sun/star/sheet/XSpreadsheetDocument.hpp diff --git a/sccomp/Library_solver.mk b/sccomp/Library_solver.mk new file mode 100644 index 000000000..933c0f7b6 --- /dev/null +++ b/sccomp/Library_solver.mk @@ -0,0 +1,58 @@ +# -*- 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/. +# +# 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 . +# + +$(eval $(call gb_Library_Library,solver)) + +$(eval $(call gb_Library_set_componentfile,solver,sccomp/source/solver/solver,services)) + +$(eval $(call gb_Library_add_componentimpls,solver, \ + $(if $(ENABLE_COINMP),coinmp) \ + $(if $(ENABLE_LPSOLVE),lpsolve) \ +)) + +$(eval $(call gb_Library_use_sdk_api,solver)) + +$(eval $(call gb_Library_set_include,solver,\ + $$(INCLUDE) \ + -I$(SRCDIR)/sccomp/inc \ +)) + +$(eval $(call gb_Library_use_libraries,solver,\ + comphelper \ + cppu \ + cppuhelper \ + sal \ + utl \ + i18nlangtag \ +)) + +$(eval $(call gb_Library_use_externals,solver,\ + boost_headers \ + coinmp \ + lpsolve \ +)) + +$(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) \ +)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/Makefile b/sccomp/Makefile new file mode 100644 index 000000000..ccb1c85a0 --- /dev/null +++ b/sccomp/Makefile @@ -0,0 +1,7 @@ +# -*- Mode: makefile-gmake; tab-width: 4; indent-tabs-mode: t -*- + +module_directory:=$(dir $(realpath $(firstword $(MAKEFILE_LIST)))) + +include $(module_directory)/../solenv/gbuild/partial_build.mk + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/Module_sccomp.mk b/sccomp/Module_sccomp.mk new file mode 100644 index 000000000..e211ee26f --- /dev/null +++ b/sccomp/Module_sccomp.mk @@ -0,0 +1,35 @@ +# -*- 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/. +# +# 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 . +# + +$(eval $(call gb_Module_Module,sccomp)) + +$(eval $(call gb_Module_add_targets,sccomp,\ + Library_solver \ +)) + +$(eval $(call gb_Module_add_l10n_targets,sccomp,\ + AllLangMoTarget_scc \ +)) + +$(eval $(call gb_Module_add_check_targets,sccomp,\ + CppunitTest_sccomp_solver \ + $(if $(and $(filter INTEL,$(CPUNAME)),$(filter -fsanitize=%,$(gb_CXX))),,$(if $(filter SCRIPTING,$(BUILD_TYPE)),CppunitTest_sccomp_swarmsolvertest)) \ +)) + +# vim: set noet sw=4 ts=4: diff --git a/sccomp/README.md b/sccomp/README.md new file mode 100644 index 000000000..7927fcda4 --- /dev/null +++ b/sccomp/README.md @@ -0,0 +1,3 @@ +# Linear Solver for LibreOffice Calc + +The (linear) solver for LibreOffice Calc. diff --git a/sccomp/inc/strings.hrc b/sccomp/inc/strings.hrc new file mode 100644 index 000000000..4fe4932de --- /dev/null +++ b/sccomp/inc/strings.hrc @@ -0,0 +1,39 @@ +/* -*- 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/. + * + * 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 . + */ + +#pragma once + +#define NC_(Context, String) TranslateId(Context, reinterpret_cast<char const *>(u8##String)) + +#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.") +#define RID_ERROR_UNBOUNDED NC_("RID_ERROR_UNBOUNDED", "The model is unbounded.") +#define RID_ERROR_TIMEOUT NC_("RID_ERROR_TIMEOUT", "The time limit was reached.") + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/qa/unit/SwarmSolverTest.cxx b/sccomp/qa/unit/SwarmSolverTest.cxx new file mode 100644 index 000000000..250309051 --- /dev/null +++ b/sccomp/qa/unit/SwarmSolverTest.cxx @@ -0,0 +1,354 @@ +/* -*- 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/sheet/XSolver.hpp> +#include <com/sun/star/sheet/XSpreadsheetDocument.hpp> +#include <com/sun/star/sheet/XSpreadsheet.hpp> +#include <com/sun/star/beans/XPropertySet.hpp> + +#include <test/calc_unoapi_test.hxx> + +using namespace css; + +namespace +{ +class SwarmSolverTest : public CalcUnoApiTest +{ + uno::Reference<lang::XComponent> 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(u"Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + uno::Reference<sheet::XSpreadsheetDocument> xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference<container::XIndexAccess> xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference<sheet::XSolver> xSolver; + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext( + "com.sun.star.comp.Calc.SwarmSolver", m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables{ { 0, 1, 0 } }; + + // constraints + uno::Sequence<sheet::SolverConstraint> 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<double> aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); + // It happens that the unconstrained test does not find a solution in the + // timeframe or number of generations it has available as the search space is + // too big and the values might not converge to solution. So for now just run + // the test so we know for sure the algorithm is guaranteed to finish + // and doesn't cause any seg faults. + //CPPUNIT_ASSERT_DOUBLES_EQUAL(3.0, aSolution[0], .9); +} + +void SwarmSolverTest::testVariableBounded() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL(u"Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + uno::Reference<sheet::XSpreadsheetDocument> xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference<container::XIndexAccess> xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference<sheet::XSolver> xSolver; + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext( + "com.sun.star.comp.Calc.SwarmSolver", m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables{ { 0, 1, 0 } }; + + // constraints + uno::Sequence<sheet::SolverConstraint> aConstraints{ + { /* [0] Left */ table::CellAddress(0, 1, 0), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(100.0) }, + { /* [1] Left */ table::CellAddress(0, 1, 0), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(-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<double> aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(3.0, aSolution[0], 1E-5); +} + +void SwarmSolverTest::testVariableConstrained() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL(u"Simple.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + uno::Reference<sheet::XSpreadsheetDocument> xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference<container::XIndexAccess> xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference<sheet::XSolver> xSolver; + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext( + "com.sun.star.comp.Calc.SwarmSolver", m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 1); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables{ { 0, 1, 0 } }; + + // constraints + uno::Sequence<sheet::SolverConstraint> aConstraints{ + { /* [0] Left */ table::CellAddress(0, 1, 0), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(-50000.0) }, + { /* [1] Left */ table::CellAddress(0, 1, 0), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(0.0) }, + { /* [2] Left */ table::CellAddress(0, 1, 1), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(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<double> aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); + CPPUNIT_ASSERT_DOUBLES_EQUAL(-0.741657, aSolution[0], 1E-5); +} + +void SwarmSolverTest::testTwoVariables() +{ + CPPUNIT_ASSERT(!mxComponent.is()); + + OUString aFileURL; + createFileURL(u"TwoVariables.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + uno::Reference<sheet::XSpreadsheetDocument> xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference<container::XIndexAccess> xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference<sheet::XSolver> xSolver; + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext( + "com.sun.star.comp.Calc.SwarmSolver", m_xContext), + uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 1, 5); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables{ { 0, 1, 2 }, { 0, 1, 3 } }; + + // constraints + uno::Sequence<sheet::SolverConstraint> aConstraints{ + { /* [0] Left */ table::CellAddress(0, 1, 2), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(-100.0) }, + { /* [1] Left */ table::CellAddress(0, 1, 3), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(-100.0) }, + { /* [2] Left */ table::CellAddress(0, 1, 2), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(100.0) }, + { /* [3] Left */ table::CellAddress(0, 1, 3), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(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<double> 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(u"MultiVariable.ods", aFileURL); + mxComponent = loadFromDesktop(aFileURL); + + uno::Reference<sheet::XSpreadsheetDocument> xDocument(mxComponent, uno::UNO_QUERY_THROW); + uno::Reference<container::XIndexAccess> xIndex(xDocument->getSheets(), uno::UNO_QUERY_THROW); + uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW); + + uno::Reference<sheet::XSolver> xSolver; + + xSolver.set(m_xContext->getServiceManager()->createInstanceWithContext( + "com.sun.star.comp.Calc.SwarmSolver", m_xContext), + uno::UNO_QUERY_THROW); + + uno::Reference<beans::XPropertySet> xPropSet(xSolver, uno::UNO_QUERY_THROW); + xPropSet->setPropertyValue("Integer", uno::Any(true)); + + table::CellAddress aObjective(0, 5, 7); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables{ + { 0, 6, 1 }, { 0, 6, 2 }, { 0, 6, 3 }, { 0, 6, 4 } + }; + + // constraints + uno::Sequence<sheet::SolverConstraint> aConstraints{ + { /* [ 0] Left */ table::CellAddress(0, 1, 5), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(table::CellAddress(0, 1, 6)) }, + { /* [ 1] Left */ table::CellAddress(0, 2, 5), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(table::CellAddress(0, 2, 6)) }, + { /* [ 2] Left */ table::CellAddress(0, 3, 5), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(table::CellAddress(0, 3, 6)) }, + { /* [ 3] Left */ table::CellAddress(0, 4, 5), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(table::CellAddress(0, 4, 6)) }, + { /* [ 4] Left */ table::CellAddress(0, 6, 1), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(0.0) }, + { /* [ 5] Left */ table::CellAddress(0, 6, 2), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(0.0) }, + { /* [ 6] Left */ table::CellAddress(0, 6, 3), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(0.0) }, + { /* [ 7] Left */ table::CellAddress(0, 6, 4), + /* Operator */ sheet::SolverConstraintOperator_GREATER_EQUAL, + /* Right */ uno::Any(0.0) }, + { /* [ 8] Left */ table::CellAddress(0, 6, 1), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(10000.0) }, + { /* [ 9] Left */ table::CellAddress(0, 6, 2), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(10000.0) }, + { /* [10] Left */ table::CellAddress(0, 6, 3), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(10000.0) }, + { /* [11] Left */ table::CellAddress(0, 6, 4), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(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<double> aSolution = xSolver->getSolution(); + + CPPUNIT_ASSERT_EQUAL(aVariables.getLength(), aSolution.getLength()); +#if 0 + // Disable 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 Binary files differnew file mode 100644 index 000000000..1e9db736a --- /dev/null +++ b/sccomp/qa/unit/data/MultiVariable.ods diff --git a/sccomp/qa/unit/data/Simple.ods b/sccomp/qa/unit/data/Simple.ods Binary files differnew file mode 100644 index 000000000..2ac8224c0 --- /dev/null +++ b/sccomp/qa/unit/data/Simple.ods diff --git a/sccomp/qa/unit/data/TwoVariables.ods b/sccomp/qa/unit/data/TwoVariables.ods Binary files differnew file mode 100644 index 000000000..c27e362e0 --- /dev/null +++ b/sccomp/qa/unit/data/TwoVariables.ods diff --git a/sccomp/qa/unit/solver.cxx b/sccomp/qa/unit/solver.cxx new file mode 100644 index 000000000..c4df7b644 --- /dev/null +++ b/sccomp/qa/unit/solver.cxx @@ -0,0 +1,125 @@ +/* -*- 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/Desktop.hpp> +#include <com/sun/star/sheet/XSolver.hpp> +#include <com/sun/star/sheet/XSolverDescription.hpp> +#include <test/bootstrapfixture.hxx> + +using namespace css; + +namespace { + +class LpSolverTest: public test::BootstrapFixture +{ + uno::Reference<sheet::XSpreadsheetDocument> m_xDocument; + +#ifdef ENABLE_LPSOLVE + void testLpSolver(); +#endif +#ifdef ENABLE_COINMP + void testCoinMPSolver(); +#endif + +#if defined(ENABLE_LPSOLVE) || defined(ENABLE_COINMP) + void testSolver(OUString const & rName); +#endif + +public: + virtual void setUp() override; + virtual void tearDown() override; + + CPPUNIT_TEST_SUITE(LpSolverTest); +#ifdef ENABLE_LPSOLVE + CPPUNIT_TEST(testLpSolver); +#endif +#ifdef ENABLE_COINMP + CPPUNIT_TEST(testCoinMPSolver); +#endif + CPPUNIT_TEST_SUITE_END(); +}; + +void LpSolverTest::setUp() +{ + test::BootstrapFixture::setUp(); + uno::Reference<frame::XDesktop2> xComponentLoader = frame::Desktop::create(m_xContext); + uno::Reference<lang::XComponent> xComponent(xComponentLoader->loadComponentFromURL( + "private:factory/scalc", "_blank", 0, + uno::Sequence < css::beans::PropertyValue >())); + m_xDocument.set(xComponent, uno::UNO_QUERY_THROW); +} + +void LpSolverTest::tearDown() +{ + uno::Reference<lang::XComponent>(m_xDocument, uno::UNO_QUERY_THROW)->dispose(); + m_xDocument.clear(); + test::BootstrapFixture::tearDown(); +} + +#ifdef ENABLE_LPSOLVE +void LpSolverTest::testLpSolver() +{ + testSolver("com.sun.star.comp.Calc.LpsolveSolver"); +} +#endif + +#ifdef ENABLE_COINMP +void LpSolverTest::testCoinMPSolver() +{ + testSolver("com.sun.star.comp.Calc.CoinMPSolver"); +} +#endif + +#if defined(ENABLE_LPSOLVE) || defined(ENABLE_COINMP) +void LpSolverTest::testSolver(OUString const & rName) +{ + uno::Reference<sheet::XSolver> xSolver(m_xContext->getServiceManager()-> + createInstanceWithContext(rName, m_xContext), uno::UNO_QUERY_THROW); + + table::CellAddress aObjective(0, 0, 0); + + // "changing cells" - unknown variables + uno::Sequence<table::CellAddress> aVariables { {0, 0, 0 } }; + + // constraints + uno::Sequence<sheet::SolverConstraint> aConstraints{ + { /* Left */ table::CellAddress(0, 0, 0), + /* Operator */ sheet::SolverConstraintOperator_LESS_EQUAL, + /* Right */ uno::Any(5.0) } + }; + + // initialize solver + xSolver->setDocument( m_xDocument ); + xSolver->setObjective( aObjective ); + xSolver->setVariables( aVariables ); + xSolver->setConstraints( aConstraints ); + xSolver->setMaximize( true ); + + // test results + xSolver->solve(); + CPPUNIT_ASSERT(xSolver->getSuccess()); + uno::Sequence<double> aSolution = xSolver->getSolution(); + CPPUNIT_ASSERT_EQUAL(aSolution.getLength(), aVariables.getLength()); + CPPUNIT_ASSERT_EQUAL(aSolution[0], 5.0); + + uno::Reference<sheet::XSolverDescription> xDesc(xSolver, uno::UNO_QUERY_THROW); + const OString sMessage("Empty description for " + OUStringToOString(rName, RTL_TEXTENCODING_UTF8)); + CPPUNIT_ASSERT_MESSAGE(sMessage.getStr(), !xDesc->getComponentDescription().isEmpty()); +} +#endif + +CPPUNIT_TEST_SUITE_REGISTRATION(LpSolverTest); + +} + +CPPUNIT_PLUGIN_IMPLEMENT(); + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/CoinMPSolver.cxx b/sccomp/source/solver/CoinMPSolver.cxx new file mode 100644 index 000000000..a6b423d2d --- /dev/null +++ b/sccomp/source/solver/CoinMPSolver.cxx @@ -0,0 +1,365 @@ +/* -*- 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/. + * + * 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 <CoinMP.h> +#include <CoinError.hpp> + +#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 <stdexcept> +#include <vector> +#include <float.h> + +namespace com::sun::star::uno { class XComponentContext; } + +using namespace com::sun::star; + +namespace { + +class CoinMPSolver : public SolverComponent +{ +public: + CoinMPSolver() {} + +private: + virtual void SAL_CALL solve() override; + virtual OUString SAL_CALL getImplementationName() override + { + return "com.sun.star.comp.Calc.CoinMPSolver"; + } + virtual OUString SAL_CALL getComponentDescription() override + { + return SolverComponent::GetResourceString( RID_COINMP_SOLVER_COMPONENT ); + } +}; + +} + +void SAL_CALL CoinMPSolver::solve() +{ + uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY_THROW ); + + maStatus.clear(); + mbSuccess = false; + + 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 parameter arrays for CoinMP + // + + // set objective function + + const std::vector<double>& rObjCoeff = aCellsHash[maObjective]; + std::unique_ptr<double[]> pObjectCoeffs(new double[nVariables]); + for (nVar=0; nVar<nVariables; nVar++) + pObjectCoeffs[nVar] = rObjCoeff[nVar+1]; + double nObjectConst = rObjCoeff[0]; // constant term of objective + + // add rows + + size_t nRows = maConstraints.getLength(); + size_t nCompSize = nVariables * nRows; + std::unique_ptr<double[]> pCompMatrix(new double[nCompSize]); // first collect all coefficients, row-wise + for (size_t i=0; i<nCompSize; i++) + pCompMatrix[i] = 0.0; + + std::unique_ptr<double[]> pRHS(new double[nRows]); + std::unique_ptr<char[]> pRowType(new char[nRows]); + for (size_t i=0; i<nRows; i++) + { + pRHS[i] = 0.0; + pRowType[i] = 'N'; + } + + for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos) + { + // integer constraints are set later + sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].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 = maConstraints[nConstrPos].Right; + if ( rRightAny >>= aRightAddr ) + bRightCell = true; // cell specified as right-hand side + else + rRightAny >>= fDirectValue; // constant value + + table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left; + + const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr]; + double* pValues = &pCompMatrix[nConstrPos * nVariables]; + for (nVar=0; nVar<nVariables; nVar++) + pValues[nVar] = 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] -= rRightCoeff[nVar+1]; + + fRightValue += rRightCoeff[0]; // constant term + } + else + fRightValue += fDirectValue; + + switch ( eOp ) + { + case sheet::SolverConstraintOperator_LESS_EQUAL: pRowType[nConstrPos] = 'L'; break; + case sheet::SolverConstraintOperator_GREATER_EQUAL: pRowType[nConstrPos] = 'G'; break; + case sheet::SolverConstraintOperator_EQUAL: pRowType[nConstrPos] = 'E'; break; + default: + OSL_ENSURE( false, "unexpected enum type" ); + } + pRHS[nConstrPos] = fRightValue; + } + } + + // Find non-zero coefficients, column-wise + + std::unique_ptr<int[]> pMatrixBegin(new int[nVariables+1]); + std::unique_ptr<int[]> pMatrixCount(new int[nVariables]); + std::unique_ptr<double[]> pMatrix(new double[nCompSize]); // not always completely used + std::unique_ptr<int[]> pMatrixIndex(new int[nCompSize]); + int nMatrixPos = 0; + for (nVar=0; nVar<nVariables; nVar++) + { + int nBegin = nMatrixPos; + for (size_t nRow=0; nRow<nRows; nRow++) + { + double fCoeff = pCompMatrix[ nRow * nVariables + nVar ]; // row-wise + if ( fCoeff != 0.0 ) + { + pMatrix[nMatrixPos] = fCoeff; + pMatrixIndex[nMatrixPos] = nRow; + ++nMatrixPos; + } + } + pMatrixBegin[nVar] = nBegin; + pMatrixCount[nVar] = nMatrixPos - nBegin; + } + pMatrixBegin[nVariables] = nMatrixPos; + pCompMatrix.reset(); + + // apply settings to all variables + + std::unique_ptr<double[]> pLowerBounds(new double[nVariables]); + std::unique_ptr<double[]> pUpperBounds(new double[nVariables]); + for (nVar=0; nVar<nVariables; nVar++) + { + pLowerBounds[nVar] = mbNonNegative ? 0.0 : -DBL_MAX; + pUpperBounds[nVar] = DBL_MAX; + + // bounds could possibly be further restricted from single-cell constraints + } + + std::unique_ptr<char[]> pColType(new char[nVariables]); + for (nVar=0; nVar<nVariables; nVar++) + pColType[nVar] = mbInteger ? 'I' : 'C'; + + // 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 ) + pColType[nVar] = 'I'; + else + { + pColType[nVar] = 'B'; + pLowerBounds[nVar] = 0.0; + pUpperBounds[nVar] = 1.0; + } + } + } + } + + int nObjectSense = mbMaximize ? SOLV_OBJSENS_MAX : SOLV_OBJSENS_MIN; + + HPROB hProb = CoinCreateProblem(""); + int nResult = CoinLoadProblem( hProb, nVariables, nRows, nMatrixPos, 0, + nObjectSense, nObjectConst, pObjectCoeffs.get(), + pLowerBounds.get(), pUpperBounds.get(), pRowType.get(), pRHS.get(), nullptr, + pMatrixBegin.get(), pMatrixCount.get(), pMatrixIndex.get(), pMatrix.get(), + nullptr, nullptr, nullptr ); + if (nResult == SOLV_CALL_SUCCESS) + { + nResult = CoinLoadInteger( hProb, pColType.get() ); + } + + pColType.reset(); + pMatrixIndex.reset(); + pMatrix.reset(); + pMatrixCount.reset(); + pMatrixBegin.reset(); + pUpperBounds.reset(); + pLowerBounds.reset(); + pRowType.reset(); + pRHS.reset(); + pObjectCoeffs.reset(); + + CoinSetRealOption( hProb, COIN_REAL_MAXSECONDS, mnTimeout ); + CoinSetRealOption( hProb, COIN_REAL_MIPMAXSEC, mnTimeout ); + + // TODO: handle (or remove) settings: epsilon, B&B depth + + // solve model + + if (nResult == SOLV_CALL_SUCCESS) + { + nResult = CoinCheckProblem( hProb ); + } + + if (nResult == SOLV_CALL_SUCCESS) + { + try + { + nResult = CoinOptimizeProblem( hProb, 0 ); + } + catch (const CoinError& e) + { + CoinUnloadProblem(hProb); + throw std::runtime_error(e.message()); + } + } + + mbSuccess = ( nResult == SOLV_CALL_SUCCESS ); + if ( mbSuccess ) + { + // get solution + + maSolution.realloc( nVariables ); + CoinGetSolutionValues( hProb, maSolution.getArray(), nullptr, nullptr, nullptr ); + mfResultValue = CoinGetObjectValue( hProb ); + } + else + { + int nSolutionStatus = CoinGetSolutionStatus( hProb ); + if ( nSolutionStatus == 1 ) + maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE ); + else if ( nSolutionStatus == 2 ) + maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED ); + // TODO: detect timeout condition and report as RID_ERROR_TIMEOUT + // (currently reported as infeasible) + } + + CoinUnloadProblem( hProb ); +} + +extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * +com_sun_star_comp_Calc_CoinMPSolver_get_implementation( + css::uno::XComponentContext *, + css::uno::Sequence<css::uno::Any> const &) +{ + return cppu::acquire(new CoinMPSolver()); +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/DifferentialEvolution.hxx b/sccomp/source/solver/DifferentialEvolution.hxx new file mode 100644 index 000000000..97453437c --- /dev/null +++ b/sccomp/source/solver/DifferentialEvolution.hxx @@ -0,0 +1,162 @@ +/* -*- 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/. + * + */ + +#pragma once + +#include <vector> +#include <random> +#include <limits> + +struct Individual +{ + std::vector<double> mVariables; +}; + +template <typename DataProvider> 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<Individual> 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<double>::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector<double> 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 + maPopulation.reserve(mnPopulationSize); + 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 chosen 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; + } +}; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ 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: */ diff --git a/sccomp/source/solver/ParticelSwarmOptimization.hxx b/sccomp/source/solver/ParticelSwarmOptimization.hxx new file mode 100644 index 000000000..ad1103309 --- /dev/null +++ b/sccomp/source/solver/ParticelSwarmOptimization.hxx @@ -0,0 +1,177 @@ +/* -*- 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/. + * + */ + +#pragma once + +#include <vector> +#include <random> +#include <limits> + +struct Particle +{ + Particle(size_t nDimensionality) + : mVelocity(nDimensionality) + , mPosition(nDimensionality) + , mCurrentFitness(std::numeric_limits<float>::lowest()) + , mBestPosition(nDimensionality) + , mBestFitness(std::numeric_limits<float>::lowest()) + { + } + + std::vector<double> mVelocity; + + std::vector<double> mPosition; + double mCurrentFitness; + + std::vector<double> mBestPosition; + double mBestFitness; +}; + +template <typename DataProvider> 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<Particle> maSwarm; + + std::random_device maRandomDevice; + std::mt19937 maGenerator; + size_t mnDimensionality; + + std::uniform_real_distribution<> maRandom01; + + std::vector<double> 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<float>::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector<double> const& getResult() { return maBestPosition; } + + int getGeneration() { return mnGeneration; } + + int getLastChange() { return mnLastChange; } + + void initialize() + { + mnGeneration = 0; + mnLastChange = 0; + maSwarm.clear(); + + mfBestFitness = std::numeric_limits<float>::lowest(); + + maSwarm.reserve(mnNumOfParticles); + 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]); + } + + rParticle.mBestPosition.insert(rParticle.mBestPosition.begin(), + rParticle.mPosition.begin(), rParticle.mPosition.end()); + rParticle.mBestFitness = rParticle.mCurrentFitness; + + if (rParticle.mCurrentFitness > mfBestFitness) + { + mfBestFitness = rParticle.mCurrentFitness; + maBestPosition.insert(maBestPosition.begin(), rParticle.mPosition.begin(), + rParticle.mPosition.end()); + } + } + } + + 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; + rParticle.mBestPosition.insert(rParticle.mBestPosition.begin(), + rParticle.mPosition.begin(), + rParticle.mPosition.end()); + } + + if (rParticle.mCurrentFitness > mfBestFitness) + { + if (std::abs(rParticle.mCurrentFitness - mfBestFitness) > constAcceptedPrecision) + { + bBestChanged = true; + mnLastChange = mnGeneration; + } + maBestPosition.insert(maBestPosition.begin(), rParticle.mPosition.begin(), + rParticle.mPosition.end()); + mfBestFitness = rParticle.mCurrentFitness; + } + } + mnGeneration++; + return bBestChanged; + } +}; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/SolverComponent.cxx b/sccomp/source/solver/SolverComponent.cxx new file mode 100644 index 000000000..e31a84073 --- /dev/null +++ b/sccomp/source/solver/SolverComponent.cxx @@ -0,0 +1,254 @@ +/* -*- 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/. + * + * 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 "SolverComponent.hxx" +#include <strings.hrc> + +#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/table/CellAddress.hpp> + +#include <cppuhelper/supportsservice.hxx> + +#include <unotools/resmgr.hxx> + +using namespace com::sun::star; + + +constexpr OUStringLiteral STR_NONNEGATIVE = u"NonNegative"; +constexpr OUStringLiteral STR_INTEGER = u"Integer"; +constexpr OUStringLiteral STR_TIMEOUT = u"Timeout"; +constexpr OUStringLiteral STR_EPSILONLEVEL = u"EpsilonLevel"; +constexpr OUStringLiteral STR_LIMITBBDEPTH = u"LimitBBDepth"; + + +// Resources from tools are used for translated strings + +OUString SolverComponent::GetResourceString(TranslateId aId) +{ + return Translate::get(aId, Translate::Create("scc")); +} + +size_t ScSolverCellHash::operator()( const css::table::CellAddress& rAddress ) const +{ + return ( rAddress.Sheet << 24 ) | ( rAddress.Column << 16 ) | rAddress.Row; +} + +bool ScSolverCellEqual::operator()( const css::table::CellAddress& rAddr1, const css::table::CellAddress& rAddr2 ) const +{ + return AddressEqual( rAddr1, rAddr2 ); +} + +namespace +{ + enum + { + PROP_NONNEGATIVE, + PROP_INTEGER, + PROP_TIMEOUT, + PROP_EPSILONLEVEL, + PROP_LIMITBBDEPTH + }; +} + +uno::Reference<table::XCell> SolverComponent::GetCell( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc, + const table::CellAddress& rPos ) +{ + uno::Reference<container::XIndexAccess> xSheets( xDoc->getSheets(), uno::UNO_QUERY ); + uno::Reference<sheet::XSpreadsheet> xSheet( xSheets->getByIndex( rPos.Sheet ), uno::UNO_QUERY ); + return xSheet->getCellByPosition( rPos.Column, rPos.Row ); +} + +void SolverComponent::SetValue( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc, + const table::CellAddress& rPos, double fValue ) +{ + SolverComponent::GetCell( xDoc, rPos )->setValue( fValue ); +} + +double SolverComponent::GetValue( const uno::Reference<sheet::XSpreadsheetDocument>& xDoc, + const table::CellAddress& rPos ) +{ + return SolverComponent::GetCell( xDoc, rPos )->getValue(); +} + +SolverComponent::SolverComponent() : + OPropertyContainer( GetBroadcastHelper() ), + mbMaximize( true ), + mbNonNegative( false ), + mbInteger( false ), + mnTimeout( 100 ), + mnEpsilonLevel( 0 ), + mbLimitBBDepth( true ), + mbSuccess( false ), + mfResultValue( 0.0 ) +{ + // for XPropertySet implementation: + registerProperty( STR_NONNEGATIVE, PROP_NONNEGATIVE, 0, &mbNonNegative, cppu::UnoType<decltype(mbNonNegative)>::get() ); + registerProperty( STR_INTEGER, PROP_INTEGER, 0, &mbInteger, cppu::UnoType<decltype(mbInteger)>::get() ); + registerProperty( STR_TIMEOUT, PROP_TIMEOUT, 0, &mnTimeout, cppu::UnoType<decltype(mnTimeout)>::get() ); + registerProperty( STR_EPSILONLEVEL, PROP_EPSILONLEVEL, 0, &mnEpsilonLevel, cppu::UnoType<decltype(mnEpsilonLevel)>::get() ); + registerProperty( STR_LIMITBBDEPTH, PROP_LIMITBBDEPTH, 0, &mbLimitBBDepth, cppu::UnoType<decltype(mbLimitBBDepth)>::get() ); +} + +SolverComponent::~SolverComponent() +{ +} + +IMPLEMENT_FORWARD_XINTERFACE2( SolverComponent, SolverComponent_Base, OPropertyContainer ) +IMPLEMENT_FORWARD_XTYPEPROVIDER2( SolverComponent, SolverComponent_Base, OPropertyContainer ) + +cppu::IPropertyArrayHelper* SolverComponent::createArrayHelper() const +{ + uno::Sequence<beans::Property> aProps; + describeProperties( aProps ); + return new cppu::OPropertyArrayHelper( aProps ); +} + +cppu::IPropertyArrayHelper& SAL_CALL SolverComponent::getInfoHelper() +{ + return *getArrayHelper(); +} + +uno::Reference<beans::XPropertySetInfo> SAL_CALL SolverComponent::getPropertySetInfo() +{ + return createPropertySetInfo( getInfoHelper() ); +} + +// XSolverDescription + +OUString SAL_CALL SolverComponent::getStatusDescription() +{ + return maStatus; +} + +OUString SAL_CALL SolverComponent::getPropertyDescription( const OUString& rPropertyName ) +{ + TranslateId pResId; + sal_Int32 nHandle = getInfoHelper().getHandleByName( rPropertyName ); + switch (nHandle) + { + 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_EPSILONLEVEL: + pResId = RID_PROPERTY_EPSILONLEVEL; + break; + case PROP_LIMITBBDEPTH: + pResId = RID_PROPERTY_LIMITBBDEPTH; + break; + default: + { + // unknown - leave empty + } + } + OUString aRet; + if (pResId) + aRet = SolverComponent::GetResourceString(pResId); + return aRet; +} + +// XSolver: settings + +uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL SolverComponent::getDocument() +{ + return mxDoc; +} + +void SAL_CALL SolverComponent::setDocument( const uno::Reference<sheet::XSpreadsheetDocument>& _document ) +{ + mxDoc = _document; +} + +table::CellAddress SAL_CALL SolverComponent::getObjective() +{ + return maObjective; +} + +void SAL_CALL SolverComponent::setObjective( const table::CellAddress& _objective ) +{ + maObjective = _objective; +} + +uno::Sequence<table::CellAddress> SAL_CALL SolverComponent::getVariables() +{ + return maVariables; +} + +void SAL_CALL SolverComponent::setVariables( const uno::Sequence<table::CellAddress>& _variables ) +{ + maVariables = _variables; +} + +uno::Sequence<sheet::SolverConstraint> SAL_CALL SolverComponent::getConstraints() +{ + return maConstraints; +} + +void SAL_CALL SolverComponent::setConstraints( const uno::Sequence<sheet::SolverConstraint>& _constraints ) +{ + maConstraints = _constraints; +} + +sal_Bool SAL_CALL SolverComponent::getMaximize() +{ + return mbMaximize; +} + +void SAL_CALL SolverComponent::setMaximize( sal_Bool _maximize ) +{ + mbMaximize = _maximize; +} + +// XSolver: get results + +sal_Bool SAL_CALL SolverComponent::getSuccess() +{ + return mbSuccess; +} + +double SAL_CALL SolverComponent::getResultValue() +{ + return mfResultValue; +} + +uno::Sequence<double> SAL_CALL SolverComponent::getSolution() +{ + return maSolution; +} + +// XServiceInfo + +sal_Bool SAL_CALL SolverComponent::supportsService( const OUString& rServiceName ) +{ + return cppu::supportsService(this, rServiceName); +} + +uno::Sequence<OUString> SAL_CALL SolverComponent::getSupportedServiceNames() +{ + return { "com.sun.star.sheet.Solver" }; +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/SolverComponent.hxx b/sccomp/source/solver/SolverComponent.hxx new file mode 100644 index 000000000..4e10c038a --- /dev/null +++ b/sccomp/source/solver/SolverComponent.hxx @@ -0,0 +1,140 @@ +/* -*- 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/. + * + * 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 . + */ + +#pragma once + +#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/lang/XServiceInfo.hpp> +#include <cppuhelper/implbase.hxx> +#include <comphelper/broadcasthelper.hxx> +#include <comphelper/propertycontainer.hxx> +#include <comphelper/proparrhlp.hxx> +#include <unotools/resmgr.hxx> + +#include <unordered_map> + +namespace com::sun::star::table { class XCell; } + +// hash map for the coefficients of a dependent cell (objective or constraint) +// The size of each vector is the number of columns (variable cells) plus one, first entry is initial value. + +struct ScSolverCellHash +{ + size_t operator()( const css::table::CellAddress& rAddress ) const; +}; + +inline bool AddressEqual( const css::table::CellAddress& rAddr1, const css::table::CellAddress& rAddr2 ) +{ + return rAddr1.Sheet == rAddr2.Sheet && rAddr1.Column == rAddr2.Column && rAddr1.Row == rAddr2.Row; +} + +struct ScSolverCellEqual +{ + bool operator()( const css::table::CellAddress& rAddr1, const css::table::CellAddress& rAddr2 ) const; +}; + +typedef std::unordered_map< css::table::CellAddress, std::vector<double>, ScSolverCellHash, ScSolverCellEqual > ScSolverCellHashMap; + +typedef cppu::WeakImplHelper< + css::sheet::XSolver, + css::sheet::XSolverDescription, + css::lang::XServiceInfo > + SolverComponent_Base; + +class SolverComponent : public comphelper::OMutexAndBroadcastHelper, + public comphelper::OPropertyContainer, + public comphelper::OPropertyArrayUsageHelper< SolverComponent >, + public SolverComponent_Base +{ +protected: + // settings + css::uno::Reference< css::sheet::XSpreadsheetDocument > mxDoc; + css::table::CellAddress maObjective; + css::uno::Sequence< css::table::CellAddress > maVariables; + css::uno::Sequence< css::sheet::SolverConstraint > maConstraints; + bool mbMaximize; + // set via XPropertySet + bool mbNonNegative; + bool mbInteger; + sal_Int32 mnTimeout; + sal_Int32 mnEpsilonLevel; + bool mbLimitBBDepth; + // results + bool mbSuccess; + double mfResultValue; + css::uno::Sequence< double > maSolution; + OUString maStatus; + + static OUString GetResourceString(TranslateId aId); + static css::uno::Reference<css::table::XCell> GetCell( + const css::uno::Reference<css::sheet::XSpreadsheetDocument>& xDoc, + const css::table::CellAddress& rPos ); + static void SetValue( + const css::uno::Reference<css::sheet::XSpreadsheetDocument>& xDoc, + const css::table::CellAddress& rPos, double fValue ); + static double GetValue( + const css::uno::Reference<css::sheet::XSpreadsheetDocument>& xDoc, + const css::table::CellAddress& rPos ); + +public: + SolverComponent(); + virtual ~SolverComponent() override; + + DECLARE_XINTERFACE() + DECLARE_XTYPEPROVIDER() + + virtual css::uno::Reference< css::beans::XPropertySetInfo > SAL_CALL getPropertySetInfo() override; + virtual ::cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override; // from OPropertySetHelper + virtual ::cppu::IPropertyArrayHelper* createArrayHelper() const override; // from OPropertyArrayUsageHelper + + // XSolver + virtual css::uno::Reference< css::sheet::XSpreadsheetDocument > SAL_CALL getDocument() override; + virtual void SAL_CALL setDocument( const css::uno::Reference< + css::sheet::XSpreadsheetDocument >& _document ) override; + virtual css::table::CellAddress SAL_CALL getObjective() override; + virtual void SAL_CALL setObjective( const css::table::CellAddress& _objective ) override; + virtual css::uno::Sequence< css::table::CellAddress > SAL_CALL getVariables() override; + virtual void SAL_CALL setVariables( const css::uno::Sequence< + css::table::CellAddress >& _variables ) override; + virtual css::uno::Sequence< css::sheet::SolverConstraint > SAL_CALL getConstraints() override; + virtual void SAL_CALL setConstraints( const css::uno::Sequence< + css::sheet::SolverConstraint >& _constraints ) override; + virtual sal_Bool SAL_CALL getMaximize() override; + virtual void SAL_CALL setMaximize( sal_Bool _maximize ) override; + + virtual sal_Bool SAL_CALL getSuccess() override; + virtual double SAL_CALL getResultValue() override; + virtual css::uno::Sequence< double > SAL_CALL getSolution() override; + + virtual void SAL_CALL solve() override = 0; + + // XSolverDescription + virtual OUString SAL_CALL getComponentDescription() override = 0; + virtual OUString SAL_CALL getStatusDescription() override; + virtual OUString SAL_CALL getPropertyDescription( const OUString& aPropertyName ) override; + + // XServiceInfo + virtual OUString SAL_CALL getImplementationName() override = 0; + virtual sal_Bool SAL_CALL supportsService( const OUString& ServiceName ) override; + virtual css::uno::Sequence< OUString > SAL_CALL getSupportedServiceNames() override; +}; + +/* 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 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: */ diff --git a/sccomp/source/solver/solver.component b/sccomp/source/solver/solver.component new file mode 100644 index 000000000..496be6628 --- /dev/null +++ b/sccomp/source/solver/solver.component @@ -0,0 +1,25 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + * 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/. + --> +<component loader="com.sun.star.loader.SharedLibrary" environment="@CPPU_ENV@" + xmlns="http://openoffice.org/2010/uno-components"> + <implementation name="com.sun.star.comp.Calc.CoinMPSolver" + constructor="com_sun_star_comp_Calc_CoinMPSolver_get_implementation"> + <service name="com.sun.star.sheet.Solver"/> + <optional/> + </implementation> + <implementation name="com.sun.star.comp.Calc.LpsolveSolver" + constructor="com_sun_star_comp_Calc_LpsolveSolver_get_implementation"> + <service name="com.sun.star.sheet.Solver"/> + <optional/> + </implementation> + <implementation name="com.sun.star.comp.Calc.SwarmSolver" + constructor="com_sun_star_comp_Calc_SwarmSolver_get_implementation"> + <service name="com.sun.star.sheet.Solver"/> + </implementation> +</component> diff --git a/sccomp/source/solver/solver.component.coinmp b/sccomp/source/solver/solver.component.coinmp new file mode 100644 index 000000000..1ced6f61b --- /dev/null +++ b/sccomp/source/solver/solver.component.coinmp @@ -0,0 +1,7 @@ +# 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/. + +com.sun.star.comp.Calc.CoinMPSolver diff --git a/sccomp/source/solver/solver.component.lpsolve b/sccomp/source/solver/solver.component.lpsolve new file mode 100644 index 000000000..3b571fbc3 --- /dev/null +++ b/sccomp/source/solver/solver.component.lpsolve @@ -0,0 +1,7 @@ +# 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/. + +com.sun.star.comp.Calc.LpsolveSolver |