sccomp/source/solver/SwarmSolver.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  */
  10
  11 #include <sal/config.h>
  12
  13 #include <com/sun/star/frame/XModel.hpp>
  14 #include <com/sun/star/container/XIndexAccess.hpp>
  15 #include <com/sun/star/sheet/XSpreadsheetDocument.hpp>
  16 #include <com/sun/star/sheet/XSpreadsheet.hpp>
  17 #include <com/sun/star/sheet/XSolver.hpp>
  18 #include <com/sun/star/sheet/XSolverDescription.hpp>
  19 #include <com/sun/star/table/CellAddress.hpp>
  20 #include <com/sun/star/table/CellContentType.hpp>
  21 #include <com/sun/star/table/XCell.hpp>
  22 #include <com/sun/star/lang/XServiceInfo.hpp>
  23
  24 #include <rtl/math.hxx>
  25 #include <cppuhelper/implbase.hxx>
  26 #include <cppuhelper/supportsservice.hxx>
  27
  28 #include <comphelper/broadcasthelper.hxx>
  29 #include <comphelper/propertycontainer.hxx>
  30 #include <comphelper/proparrhlp.hxx>
  31
  32 #include <cmath>
  33 #include <vector>
  34 #include <limits>
  35 #include <chrono>
  36 #include <random>
  37
  38 #include <unotools/resmgr.hxx>
  39
  40 #include "DifferentialEvolution.hxx"
  41 #include "ParticelSwarmOptimization.hxx"
  42
  43 #include <strings.hrc>
  44
  45 namespace com::sun::star::uno
  46 {
  47 class XComponentContext;
  48 }
  49
  50 using namespace css;
  51
  52 namespace
  53 {
  54 struct Bound
  55 {
  56     double lower;
  57     double upper;
  58
  59     Bound()
  60         // float bounds should be low/high enough for all practical uses
  61         // otherwise we are too far away from the solution
  62         : lower(std::numeric_limits<float>::lowest())
  63         , upper(std::numeric_limits<float>::max())
  64     {
  65     }
  66
  67     void updateBound(sheet::SolverConstraintOperator eOp, double fValue)
  68     {
  69         if (eOp == sheet::SolverConstraintOperator_LESS_EQUAL)
  70         {
  71             // if we set the bound multiple times use the one which includes both values
  72             // for example bound values 100, 120, 150 -> use 100 -> the lowest one
  73             if (fValue < upper)
  74                 upper = fValue;
  75         }
  76         else if (eOp == sheet::SolverConstraintOperator_GREATER_EQUAL)
  77         {
  78             if (fValue > lower)
  79                 lower = fValue;
  80         }
  81         else if (eOp == sheet::SolverConstraintOperator_EQUAL)
  82         {
  83             lower = fValue;
  84             upper = fValue;
  85         }
  86     }
  87 };
  88
  89 enum
  90 {
  91     PROP_NONNEGATIVE,
  92     PROP_INTEGER,
  93     PROP_TIMEOUT,
  94     PROP_ALGORITHM,
  95 };
  96
  97 } // end anonymous namespace
  98
  99 typedef cppu::WeakImplHelper<sheet::XSolver, sheet::XSolverDescription, lang::XServiceInfo>
 100     SwarmSolver_Base;
 101
 102 namespace
 103 {
 104 class SwarmSolver : public comphelper::OMutexAndBroadcastHelper,
 105                     public comphelper::OPropertyContainer,
 106                     public comphelper::OPropertyArrayUsageHelper<SwarmSolver>,
 107                     public SwarmSolver_Base
 108 {
 109 private:
 110     uno::Reference<sheet::XSpreadsheetDocument> mxDocument;
 111     table::CellAddress maObjective;
 112     uno::Sequence<table::CellAddress> maVariables;
 113     uno::Sequence<sheet::SolverConstraint> maConstraints;
 114     bool mbMaximize;
 115
 116     // set via XPropertySet
 117     bool mbNonNegative;
 118     bool mbInteger;
 119     sal_Int32 mnTimeout;
 120     sal_Int32 mnAlgorithm;
 121
 122     // results
 123     bool mbSuccess;
 124     double mfResultValue;
 125
 126     uno::Sequence<double> maSolution;
 127     OUString maStatus;
 128
 129     std::vector<Bound> maBounds;
 130     std::vector<sheet::SolverConstraint> maNonBoundedConstraints;
 131
 132 private:
 133     static OUString getResourceString(const char* pId);
 134
 135     uno::Reference<table::XCell> getCell(const table::CellAddress& rPosition);
 136     void setValue(const table::CellAddress& rPosition, double fValue);
 137     double getValue(const table::CellAddress& rPosition);
 138
 139 public:
 140     SwarmSolver()
 141         : OPropertyContainer(GetBroadcastHelper())
 142         , mbMaximize(true)
 143         , mbNonNegative(false)
 144         , mbInteger(false)
 145         , mnTimeout(60000)
 146         , mnAlgorithm(0)
 147         , mbSuccess(false)
 148         , mfResultValue(0.0)
 149     {
 150         registerProperty("NonNegative", PROP_NONNEGATIVE, 0, &mbNonNegative,
 151                          cppu::UnoType<decltype(mbNonNegative)>::get());
 152         registerProperty("Integer", PROP_INTEGER, 0, &mbInteger,
 153                          cppu::UnoType<decltype(mbInteger)>::get());
 154         registerProperty("Timeout", PROP_TIMEOUT, 0, &mnTimeout,
 155                          cppu::UnoType<decltype(mnTimeout)>::get());
 156         registerProperty("Algorithm", PROP_ALGORITHM, 0, &mnAlgorithm,
 157                          cppu::UnoType<decltype(mnAlgorithm)>::get());
 158     }
 159
 160     DECLARE_XINTERFACE()
 161     DECLARE_XTYPEPROVIDER()
 162
 163     virtual uno::Reference<beans::XPropertySetInfo> SAL_CALL getPropertySetInfo() override
 164     {
 165         return createPropertySetInfo(getInfoHelper());
 166     }
 167     // OPropertySetHelper
 168     virtual cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override
 169     {
 170         return *getArrayHelper();
 171     }
 172     // OPropertyArrayUsageHelper
 173     virtual cppu::IPropertyArrayHelper* createArrayHelper() const override
 174     {
 175         uno::Sequence<beans::Property> aProperties;
 176         describeProperties(aProperties);
 177         return new cppu::OPropertyArrayHelper(aProperties);
 178     }
 179
 180     // XSolver
 181     virtual uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL getDocument() override
 182     {
 183         return mxDocument;
 184     }
 185     virtual void SAL_CALL
 186     setDocument(const uno::Reference<sheet::XSpreadsheetDocument>& rDocument) override
 187     {
 188         mxDocument = rDocument;
 189     }
 190
 191     virtual table::CellAddress SAL_CALL getObjective() override { return maObjective; }
 192     virtual void SAL_CALL setObjective(const table::CellAddress& rObjective) override
 193     {
 194         maObjective = rObjective;
 195     }
 196
 197     virtual uno::Sequence<table::CellAddress> SAL_CALL getVariables() override
 198     {
 199         return maVariables;
 200     }
 201     virtual void SAL_CALL setVariables(const uno::Sequence<table::CellAddress>& rVariables) override
 202     {
 203         maVariables = rVariables;
 204     }
 205
 206     virtual uno::Sequence<sheet::SolverConstraint> SAL_CALL getConstraints() override
 207     {
 208         return maConstraints;
 209     }
 210     virtual void SAL_CALL
 211     setConstraints(const uno::Sequence<sheet::SolverConstraint>& rConstraints) override
 212     {
 213         maConstraints = rConstraints;
 214     }
 215
 216     virtual sal_Bool SAL_CALL getMaximize() override { return mbMaximize; }
 217     virtual void SAL_CALL setMaximize(sal_Bool bMaximize) override { mbMaximize = bMaximize; }
 218
 219     virtual sal_Bool SAL_CALL getSuccess() override { return mbSuccess; }
 220     virtual double SAL_CALL getResultValue() override { return mfResultValue; }
 221
 222     virtual uno::Sequence<double> SAL_CALL getSolution() override { return maSolution; }
 223
 224     virtual void SAL_CALL solve() override;
 225
 226     // XSolverDescription
 227     virtual OUString SAL_CALL getComponentDescription() override
 228     {
 229         return SwarmSolver::getResourceString(RID_SWARM_SOLVER_COMPONENT);
 230     }
 231
 232     virtual OUString SAL_CALL getStatusDescription() override { return maStatus; }
 233
 234     virtual OUString SAL_CALL getPropertyDescription(const OUString& rPropertyName) override
 235     {
 236         const char* pResId = nullptr;
 237         switch (getInfoHelper().getHandleByName(rPropertyName))
 238         {
 239             case PROP_NONNEGATIVE:
 240                 pResId = RID_PROPERTY_NONNEGATIVE;
 241                 break;
 242             case PROP_INTEGER:
 243                 pResId = RID_PROPERTY_INTEGER;
 244                 break;
 245             case PROP_TIMEOUT:
 246                 pResId = RID_PROPERTY_TIMEOUT;
 247                 break;
 248             case PROP_ALGORITHM:
 249                 pResId = RID_PROPERTY_ALGORITHM;
 250                 break;
 251             default:
 252                 break;
 253         }
 254         return SwarmSolver::getResourceString(pResId);
 255     }
 256
 257     // XServiceInfo
 258     virtual OUString SAL_CALL getImplementationName() override
 259     {
 260         return "com.sun.star.comp.Calc.SwarmSolver";
 261     }
 262
 263     sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override
 264     {
 265         return cppu::supportsService(this, rServiceName);
 266     }
 267
 268     uno::Sequence<OUString> SAL_CALL getSupportedServiceNames() override
 269     {
 270         return { "com.sun.star.sheet.Solver" };
 271     }
 272
 273 private:
 274     void applyVariables(std::vector<double> const& rVariables);
 275     bool doesViolateConstraints();
 276
 277 public:
 278     double calculateFitness(std::vector<double> const& rVariables);
 279     size_t getDimensionality() const;
 280     void initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator);
 281     double clampVariable(size_t nVarIndex, double fValue);
 282     double boundVariable(size_t nVarIndex, double fValue);
 283 };
 284 }
 285
 286 OUString SwarmSolver::getResourceString(const char* pId)
 287 {
 288     if (!pId)
 289         return OUString();
 290
 291     return Translate::get(pId, Translate::Create("scc"));
 292 }
 293
 294 uno::Reference<table::XCell> SwarmSolver::getCell(const table::CellAddress& rPosition)
 295 {
 296     uno::Reference<container::XIndexAccess> xSheets(mxDocument->getSheets(), uno::UNO_QUERY);
 297     uno::Reference<sheet::XSpreadsheet> xSheet(xSheets->getByIndex(rPosition.Sheet),
 298                                                uno::UNO_QUERY);
 299     return xSheet->getCellByPosition(rPosition.Column, rPosition.Row);
 300 }
 301
 302 void SwarmSolver::setValue(const table::CellAddress& rPosition, double fValue)
 303 {
 304     getCell(rPosition)->setValue(fValue);
 305 }
 306
 307 double SwarmSolver::getValue(const table::CellAddress& rPosition)
 308 {
 309     return getCell(rPosition)->getValue();
 310 }
 311
 312 IMPLEMENT_FORWARD_XINTERFACE2(SwarmSolver, SwarmSolver_Base, OPropertyContainer)
 313 IMPLEMENT_FORWARD_XTYPEPROVIDER2(SwarmSolver, SwarmSolver_Base, OPropertyContainer)
 314
 315 void SwarmSolver::applyVariables(std::vector<double> const& rVariables)
 316 {
 317     for (sal_Int32 i = 0; i < maVariables.getLength(); ++i)
 318     {
 319         setValue(maVariables[i], rVariables[i]);
 320     }
 321 }
 322
 323 double SwarmSolver::calculateFitness(std::vector<double> const& rVariables)
 324 {
 325     applyVariables(rVariables);
 326
 327     if (doesViolateConstraints())
 328         return std::numeric_limits<float>::lowest();
 329
 330     double x = getValue(maObjective);
 331
 332     if (mbMaximize)
 333         return x;
 334     else
 335         return -x;
 336 }
 337
 338 void SwarmSolver::initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator)
 339 {
 340     int nTry = 1;
 341     bool bConstraintsOK = false;
 342
 343     while (!bConstraintsOK && nTry < 10)
 344     {
 345         size_t noVariables(maVariables.getLength());
 346
 347         rVariables.resize(noVariables);
 348
 349         for (size_t i = 0; i < noVariables; ++i)
 350         {
 351             Bound const& rBound = maBounds[i];
 352             if (mbInteger)
 353             {
 354                 sal_Int64 intLower(rBound.lower);
 355                 sal_Int64 intUpper(rBound.upper);
 356                 std::uniform_int_distribution<sal_Int64> random(intLower, intUpper);
 357                 rVariables[i] = double(random(rGenerator));
 358             }
 359             else
 360             {
 361                 std::uniform_real_distribution<double> random(rBound.lower, rBound.upper);
 362                 rVariables[i] = random(rGenerator);
 363             }
 364         }
 365
 366         applyVariables(rVariables);
 367
 368         bConstraintsOK = !doesViolateConstraints();
 369         nTry++;
 370     }
 371 }
 372
 373 double SwarmSolver::clampVariable(size_t nVarIndex, double fValue)
 374 {
 375     Bound const& rBound = maBounds[nVarIndex];
 376     double fResult = std::clamp(fValue, rBound.lower, rBound.upper);
 377
 378     if (mbInteger)
 379         return std::trunc(fResult);
 380
 381     return fResult;
 382 }
 383
 384 double SwarmSolver::boundVariable(size_t nVarIndex, double fValue)
 385 {
 386     Bound const& rBound = maBounds[nVarIndex];
 387     // double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower);
 388     double fResult = fValue;
 389     while (fResult < rBound.lower || fResult > rBound.upper)
 390     {
 391         if (fResult < rBound.lower)
 392             fResult = rBound.upper - (rBound.lower - fResult);
 393         if (fResult > rBound.upper)
 394             fResult = (fResult - rBound.upper) + rBound.lower;
 395     }
 396
 397     if (mbInteger)
 398         return std::trunc(fResult);
 399
 400     return fResult;
 401 }
 402
 403 size_t SwarmSolver::getDimensionality() const { return maVariables.getLength(); }
 404
 405 bool SwarmSolver::doesViolateConstraints()
 406 {
 407     for (const sheet::SolverConstraint& rConstraint : maNonBoundedConstraints)
 408     {
 409         double fLeftValue = getValue(rConstraint.Left);
 410         double fRightValue = 0.0;
 411
 412         table::CellAddress aCellAddress;
 413
 414         if (rConstraint.Right >>= aCellAddress)
 415         {
 416             fRightValue = getValue(aCellAddress);
 417         }
 418         else if (rConstraint.Right >>= fRightValue)
 419         {
 420             // empty
 421         }
 422         else
 423         {
 424             return false;
 425         }
 426
 427         sheet::SolverConstraintOperator eOp = rConstraint.Operator;
 428         switch (eOp)
 429         {
 430             case sheet::SolverConstraintOperator_LESS_EQUAL:
 431             {
 432                 if (fLeftValue > fRightValue)
 433                     return true;
 434             }
 435             break;
 436             case sheet::SolverConstraintOperator_GREATER_EQUAL:
 437             {
 438                 if (fLeftValue < fRightValue)
 439                     return true;
 440             }
 441             break;
 442             case sheet::SolverConstraintOperator_EQUAL:
 443             {
 444                 if (!rtl::math::approxEqual(fLeftValue, fRightValue))
 445                     return true;
 446             }
 447             break;
 448             default:
 449                 break;
 450         }
 451     }
 452     return false;
 453 }
 454
 455 namespace
 456 {
 457 template <typename SwarmAlgorithm> class SwarmRunner
 458 {
 459 private:
 460     SwarmAlgorithm& mrAlgorithm;
 461     double mfTimeout;
 462
 463     static constexpr size_t mnPopulationSize = 40;
 464     static constexpr int constNumberOfGenerationsWithoutChange = 50;
 465
 466     std::chrono::high_resolution_clock::time_point maStart;
 467     std::chrono::high_resolution_clock::time_point maEnd;
 468
 469 public:
 470     SwarmRunner(SwarmAlgorithm& rAlgorithm)
 471         : mrAlgorithm(rAlgorithm)
 472         , mfTimeout(5000)
 473     {
 474     }
 475
 476     void setTimeout(double fTimeout) { mfTimeout = fTimeout; }
 477
 478     std::vector<double> const& solve()
 479     {
 480         using std::chrono::duration_cast;
 481         using std::chrono::high_resolution_clock;
 482         using std::chrono::milliseconds;
 483
 484         mrAlgorithm.initialize();
 485
 486         maEnd = maStart = high_resolution_clock::now();
 487
 488         int nLastChange = 0;
 489
 490         while ((mrAlgorithm.getGeneration() - nLastChange) < constNumberOfGenerationsWithoutChange
 491                && duration_cast<milliseconds>(maEnd - maStart).count() < mfTimeout)
 492         {
 493             bool bChange = mrAlgorithm.next();
 494
 495             if (bChange)
 496                 nLastChange = mrAlgorithm.getGeneration();
 497
 498             maEnd = high_resolution_clock::now();
 499         }
 500         return mrAlgorithm.getResult();
 501     }
 502 };
 503 }
 504
 505 void SAL_CALL SwarmSolver::solve()
 506 {
 507     uno::Reference<frame::XModel> xModel(mxDocument, uno::UNO_QUERY_THROW);
 508
 509     maStatus.clear();
 510     mbSuccess = false;
 511     if (!maVariables.getLength())
 512         return;
 513
 514     maBounds.resize(maVariables.getLength());
 515
 516     xModel->lockControllers();
 517
 518     if (mbNonNegative)
 519     {
 520         for (Bound& rBound : maBounds)
 521             rBound.lower = 0;
 522     }
 523
 524     // Determine variable bounds
 525     for (sheet::SolverConstraint const& rConstraint : std::as_const(maConstraints))
 526     {
 527         table::CellAddress aLeftCellAddress = rConstraint.Left;
 528         sheet::SolverConstraintOperator eOp = rConstraint.Operator;
 529
 530         size_t index = 0;
 531         bool bFoundVariable = false;
 532         for (const table::CellAddress& rVariableCell : std::as_const(maVariables))
 533         {
 534             if (aLeftCellAddress == rVariableCell)
 535             {
 536                 bFoundVariable = true;
 537                 table::CellAddress aCellAddress;
 538                 double fValue;
 539
 540                 if (rConstraint.Right >>= aCellAddress)
 541                 {
 542                     uno::Reference<table::XCell> xCell = getCell(aCellAddress);
 543                     if (xCell->getType() == table::CellContentType_VALUE)
 544                     {
 545                         maBounds[index].updateBound(eOp, xCell->getValue());
 546                     }
 547                     else
 548                     {
 549                         maNonBoundedConstraints.push_back(rConstraint);
 550                     }
 551                 }
 552                 else if (rConstraint.Right >>= fValue)
 553                 {
 554                     maBounds[index].updateBound(eOp, fValue);
 555                 }
 556             }
 557             index++;
 558         }
 559         if (!bFoundVariable)
 560             maNonBoundedConstraints.push_back(rConstraint);
 561     }
 562
 563     std::vector<double> aSolution;
 564
 565     if (mnAlgorithm == 0)
 566     {
 567         DifferentialEvolutionAlgorithm<SwarmSolver> aDE(*this, 50);
 568         SwarmRunner<DifferentialEvolutionAlgorithm<SwarmSolver>> aEvolution(aDE);
 569         aEvolution.setTimeout(mnTimeout);
 570         aSolution = aEvolution.solve();
 571     }
 572     else
 573     {
 574         ParticleSwarmOptimizationAlgorithm<SwarmSolver> aPSO(*this, 100);
 575         SwarmRunner<ParticleSwarmOptimizationAlgorithm<SwarmSolver>> aSwarmSolver(aPSO);
 576         aSwarmSolver.setTimeout(mnTimeout);
 577         aSolution = aSwarmSolver.solve();
 578     }
 579
 580     xModel->unlockControllers();
 581
 582     mbSuccess = true;
 583
 584     maSolution.realloc(aSolution.size());
 585     std::copy(aSolution.begin(), aSolution.end(), maSolution.begin());
 586 }
 587
 588 extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface*
 589 com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*,
 590                                                       uno::Sequence<uno::Any> const&)
 591 {
 592     return cppu::acquire(new SwarmSolver());
 593 }
 594
 595 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */