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 class SwarmSolver : public comphelper::OMutexAndBroadcastHelper,
 103                     public comphelper::OPropertyContainer,
 104                     public comphelper::OPropertyArrayUsageHelper<SwarmSolver>,
 105                     public SwarmSolver_Base
 106 {
 107 private:
 108     uno::Reference<sheet::XSpreadsheetDocument> mxDocument;
 109     table::CellAddress maObjective;
 110     uno::Sequence<table::CellAddress> maVariables;
 111     uno::Sequence<sheet::SolverConstraint> maConstraints;
 112     bool mbMaximize;
 113
 114     // set via XPropertySet
 115     bool mbNonNegative;
 116     bool mbInteger;
 117     sal_Int32 mnTimeout;
 118     sal_Int32 mnAlgorithm;
 119
 120     // results
 121     bool mbSuccess;
 122
 123     uno::Sequence<double> maSolution;
 124     OUString maStatus;
 125
 126     std::vector<Bound> maBounds;
 127     std::vector<sheet::SolverConstraint> maNonBoundedConstraints;
 128
 129 private:
 130     static OUString getResourceString(const char* pId);
 131
 132     uno::Reference<table::XCell> getCell(const table::CellAddress& rPosition);
 133     void setValue(const table::CellAddress& rPosition, double fValue);
 134     double getValue(const table::CellAddress& rPosition);
 135
 136 public:
 137     SwarmSolver()
 138         : OPropertyContainer(GetBroadcastHelper())
 139         , mbMaximize(true)
 140         , mbNonNegative(false)
 141         , mbInteger(false)
 142         , mnTimeout(60000)
 143         , mnAlgorithm(0)
 144         , mbSuccess(false)
 145     {
 146         registerProperty("NonNegative", PROP_NONNEGATIVE, 0, &mbNonNegative,
 147                          cppu::UnoType<decltype(mbNonNegative)>::get());
 148         registerProperty("Integer", PROP_INTEGER, 0, &mbInteger,
 149                          cppu::UnoType<decltype(mbInteger)>::get());
 150         registerProperty("Timeout", PROP_TIMEOUT, 0, &mnTimeout,
 151                          cppu::UnoType<decltype(mnTimeout)>::get());
 152         registerProperty("Algorithm", PROP_ALGORITHM, 0, &mnAlgorithm,
 153                          cppu::UnoType<decltype(mnAlgorithm)>::get());
 154     }
 155
 156     DECLARE_XINTERFACE()
 157     DECLARE_XTYPEPROVIDER()
 158
 159     virtual uno::Reference<beans::XPropertySetInfo> SAL_CALL getPropertySetInfo() override
 160     {
 161         return createPropertySetInfo(getInfoHelper());
 162     }
 163     // OPropertySetHelper
 164     virtual cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override
 165     {
 166         return *getArrayHelper();
 167     }
 168     // OPropertyArrayUsageHelper
 169     virtual cppu::IPropertyArrayHelper* createArrayHelper() const override
 170     {
 171         uno::Sequence<beans::Property> aProperties;
 172         describeProperties(aProperties);
 173         return new cppu::OPropertyArrayHelper(aProperties);
 174     }
 175
 176     // XSolver
 177     virtual uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL getDocument() override
 178     {
 179         return mxDocument;
 180     }
 181     virtual void SAL_CALL
 182     setDocument(const uno::Reference<sheet::XSpreadsheetDocument>& rDocument) override
 183     {
 184         mxDocument = rDocument;
 185     }
 186
 187     virtual table::CellAddress SAL_CALL getObjective() override { return maObjective; }
 188     virtual void SAL_CALL setObjective(const table::CellAddress& rObjective) override
 189     {
 190         maObjective = rObjective;
 191     }
 192
 193     virtual uno::Sequence<table::CellAddress> SAL_CALL getVariables() override
 194     {
 195         return maVariables;
 196     }
 197     virtual void SAL_CALL setVariables(const uno::Sequence<table::CellAddress>& rVariables) override
 198     {
 199         maVariables = rVariables;
 200     }
 201
 202     virtual uno::Sequence<sheet::SolverConstraint> SAL_CALL getConstraints() override
 203     {
 204         return maConstraints;
 205     }
 206     virtual void SAL_CALL
 207     setConstraints(const uno::Sequence<sheet::SolverConstraint>& rConstraints) override
 208     {
 209         maConstraints = rConstraints;
 210     }
 211
 212     virtual sal_Bool SAL_CALL getMaximize() override { return mbMaximize; }
 213     virtual void SAL_CALL setMaximize(sal_Bool bMaximize) override { mbMaximize = bMaximize; }
 214
 215     virtual sal_Bool SAL_CALL getSuccess() override { return mbSuccess; }
 216     virtual double SAL_CALL getResultValue() override { return 0; }
 217
 218     virtual uno::Sequence<double> SAL_CALL getSolution() override { return maSolution; }
 219
 220     virtual void SAL_CALL solve() override;
 221
 222     // XSolverDescription
 223     virtual OUString SAL_CALL getComponentDescription() override
 224     {
 225         return SwarmSolver::getResourceString(RID_SWARM_SOLVER_COMPONENT);
 226     }
 227
 228     virtual OUString SAL_CALL getStatusDescription() override { return maStatus; }
 229
 230     virtual OUString SAL_CALL getPropertyDescription(const OUString& rPropertyName) override
 231     {
 232         const char* pResId = nullptr;
 233         switch (getInfoHelper().getHandleByName(rPropertyName))
 234         {
 235             case PROP_NONNEGATIVE:
 236                 pResId = RID_PROPERTY_NONNEGATIVE;
 237                 break;
 238             case PROP_INTEGER:
 239                 pResId = RID_PROPERTY_INTEGER;
 240                 break;
 241             case PROP_TIMEOUT:
 242                 pResId = RID_PROPERTY_TIMEOUT;
 243                 break;
 244             case PROP_ALGORITHM:
 245                 pResId = RID_PROPERTY_ALGORITHM;
 246                 break;
 247             default:
 248                 break;
 249         }
 250         return SwarmSolver::getResourceString(pResId);
 251     }
 252
 253     // XServiceInfo
 254     virtual OUString SAL_CALL getImplementationName() override
 255     {
 256         return "com.sun.star.comp.Calc.SwarmSolver";
 257     }
 258
 259     sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override
 260     {
 261         return cppu::supportsService(this, rServiceName);
 262     }
 263
 264     uno::Sequence<OUString> SAL_CALL getSupportedServiceNames() override
 265     {
 266         uno::Sequence<OUString> aServiceNames{ "com.sun.star.sheet.Solver" };
 267         return aServiceNames;
 268     }
 269
 270 private:
 271     void applyVariables(std::vector<double> const& rVariables);
 272     bool doesViolateConstraints();
 273
 274 public:
 275     double calculateFitness(std::vector<double> const& rVariables);
 276     size_t getDimensionality() const;
 277     void initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator);
 278     double clampVariable(size_t nVarIndex, double fValue);
 279     double boundVariable(size_t nVarIndex, double fValue);
 280 };
 281
 282 OUString SwarmSolver::getResourceString(const char* pId)
 283 {
 284     if (!pId)
 285         return OUString();
 286
 287     return Translate::get(pId, Translate::Create("scc"));
 288 }
 289
 290 uno::Reference<table::XCell> SwarmSolver::getCell(const table::CellAddress& rPosition)
 291 {
 292     uno::Reference<container::XIndexAccess> xSheets(mxDocument->getSheets(), uno::UNO_QUERY);
 293     uno::Reference<sheet::XSpreadsheet> xSheet(xSheets->getByIndex(rPosition.Sheet),
 294                                                uno::UNO_QUERY);
 295     return xSheet->getCellByPosition(rPosition.Column, rPosition.Row);
 296 }
 297
 298 void SwarmSolver::setValue(const table::CellAddress& rPosition, double fValue)
 299 {
 300     getCell(rPosition)->setValue(fValue);
 301 }
 302
 303 double SwarmSolver::getValue(const table::CellAddress& rPosition)
 304 {
 305     return getCell(rPosition)->getValue();
 306 }
 307
 308 IMPLEMENT_FORWARD_XINTERFACE2(SwarmSolver, SwarmSolver_Base, OPropertyContainer)
 309 IMPLEMENT_FORWARD_XTYPEPROVIDER2(SwarmSolver, SwarmSolver_Base, OPropertyContainer)
 310
 311 void SwarmSolver::applyVariables(std::vector<double> const& rVariables)
 312 {
 313     for (sal_Int32 i = 0; i < maVariables.getLength(); ++i)
 314     {
 315         setValue(maVariables[i], rVariables[i]);
 316     }
 317 }
 318
 319 double SwarmSolver::calculateFitness(std::vector<double> const& rVariables)
 320 {
 321     applyVariables(rVariables);
 322
 323     if (doesViolateConstraints())
 324         return std::numeric_limits<float>::lowest();
 325
 326     double x = getValue(maObjective);
 327
 328     if (mbMaximize)
 329         return x;
 330     else
 331         return -x;
 332 }
 333
 334 void SwarmSolver::initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator)
 335 {
 336     int nTry = 1;
 337     bool bConstraintsOK = false;
 338
 339     while (!bConstraintsOK && nTry < 10)
 340     {
 341         size_t noVariables(maVariables.getLength());
 342
 343         rVariables.resize(noVariables);
 344
 345         for (size_t i = 0; i < noVariables; ++i)
 346         {
 347             Bound const& rBound = maBounds[i];
 348             if (mbInteger)
 349             {
 350                 sal_Int64 intLower(rBound.lower);
 351                 sal_Int64 intUpper(rBound.upper);
 352                 std::uniform_int_distribution<sal_Int64> random(intLower, intUpper);
 353                 rVariables[i] = double(random(rGenerator));
 354             }
 355             else
 356             {
 357                 std::uniform_real_distribution<double> random(rBound.lower, rBound.upper);
 358                 rVariables[i] = random(rGenerator);
 359             }
 360         }
 361
 362         applyVariables(rVariables);
 363
 364         bConstraintsOK = !doesViolateConstraints();
 365         nTry++;
 366     }
 367 }
 368
 369 double SwarmSolver::clampVariable(size_t nVarIndex, double fValue)
 370 {
 371     Bound const& rBound = maBounds[nVarIndex];
 372     double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower);
 373
 374     if (mbInteger)
 375         return std::trunc(fResult);
 376
 377     return fResult;
 378 }
 379
 380 double SwarmSolver::boundVariable(size_t nVarIndex, double fValue)
 381 {
 382     Bound const& rBound = maBounds[nVarIndex];
 383     // double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower);
 384     double fResult = fValue;
 385     while (fResult < rBound.lower || fResult > rBound.upper)
 386     {
 387         if (fResult < rBound.lower)
 388             fResult = rBound.upper - (rBound.lower - fResult);
 389         if (fResult > rBound.upper)
 390             fResult = (fResult - rBound.upper) + rBound.lower;
 391     }
 392
 393     if (mbInteger)
 394         return std::trunc(fResult);
 395
 396     return fResult;
 397 }
 398
 399 size_t SwarmSolver::getDimensionality() const { return maVariables.getLength(); }
 400
 401 bool SwarmSolver::doesViolateConstraints()
 402 {
 403     for (const sheet::SolverConstraint& rConstraint : maNonBoundedConstraints)
 404     {
 405         double fLeftValue = getValue(rConstraint.Left);
 406         double fRightValue = 0.0;
 407
 408         table::CellAddress aCellAddress;
 409
 410         if (rConstraint.Right >>= aCellAddress)
 411         {
 412             fRightValue = getValue(aCellAddress);
 413         }
 414         else if (rConstraint.Right >>= fRightValue)
 415         {
 416             // empty
 417         }
 418         else
 419         {
 420             return false;
 421         }
 422
 423         sheet::SolverConstraintOperator eOp = rConstraint.Operator;
 424         switch (eOp)
 425         {
 426             case sheet::SolverConstraintOperator_LESS_EQUAL:
 427             {
 428                 if (fLeftValue > fRightValue)
 429                     return true;
 430             }
 431             break;
 432             case sheet::SolverConstraintOperator_GREATER_EQUAL:
 433             {
 434                 if (fLeftValue < fRightValue)
 435                     return true;
 436             }
 437             break;
 438             case sheet::SolverConstraintOperator_EQUAL:
 439             {
 440                 if (!rtl::math::approxEqual(fLeftValue, fRightValue))
 441                     return true;
 442             }
 443             break;
 444             default:
 445                 break;
 446         }
 447     }
 448     return false;
 449 }
 450
 451 template <typename SwarmAlgorithm> class SwarmRunner
 452 {
 453 private:
 454     SwarmAlgorithm& mrAlgorithm;
 455     double mfTimeout;
 456
 457     static constexpr size_t mnPopulationSize = 40;
 458     static constexpr int constNumberOfGenerationsWithoutChange = 50;
 459
 460     std::chrono::high_resolution_clock::time_point maStart;
 461     std::chrono::high_resolution_clock::time_point maEnd;
 462
 463 public:
 464     SwarmRunner(SwarmAlgorithm& rAlgorithm)
 465         : mrAlgorithm(rAlgorithm)
 466         , mfTimeout(5000)
 467     {
 468     }
 469
 470     void setTimeout(double fTimeout) { mfTimeout = fTimeout; }
 471
 472     std::vector<double> const& solve()
 473     {
 474         using std::chrono::duration_cast;
 475         using std::chrono::high_resolution_clock;
 476         using std::chrono::milliseconds;
 477
 478         mrAlgorithm.initialize();
 479
 480         maEnd = maStart = high_resolution_clock::now();
 481
 482         int nLastChange = 0;
 483
 484         while ((mrAlgorithm.getGeneration() - nLastChange) < constNumberOfGenerationsWithoutChange
 485                && duration_cast<milliseconds>(maEnd - maStart).count() < mfTimeout)
 486         {
 487             bool bChange = mrAlgorithm.next();
 488
 489             if (bChange)
 490                 nLastChange = mrAlgorithm.getGeneration();
 491
 492             maEnd = high_resolution_clock::now();
 493         }
 494         return mrAlgorithm.getResult();
 495     }
 496 };
 497
 498 void SAL_CALL SwarmSolver::solve()
 499 {
 500     uno::Reference<frame::XModel> xModel(mxDocument, uno::UNO_QUERY_THROW);
 501
 502     maStatus.clear();
 503     mbSuccess = false;
 504
 505     maBounds.resize(maVariables.getLength());
 506
 507     xModel->lockControllers();
 508
 509     if (mbNonNegative)
 510     {
 511         for (Bound& rBound : maBounds)
 512             rBound.lower = 0;
 513     }
 514
 515     // Determine variable bounds
 516     for (sheet::SolverConstraint const& rConstraint : std::as_const(maConstraints))
 517     {
 518         table::CellAddress aLeftCellAddress = rConstraint.Left;
 519         sheet::SolverConstraintOperator eOp = rConstraint.Operator;
 520
 521         size_t index = 0;
 522         bool bFoundVariable = false;
 523         for (const table::CellAddress& rVariableCell : std::as_const(maVariables))
 524         {
 525             if (aLeftCellAddress == rVariableCell)
 526             {
 527                 bFoundVariable = true;
 528                 table::CellAddress aCellAddress;
 529                 double fValue;
 530
 531                 if (rConstraint.Right >>= aCellAddress)
 532                 {
 533                     uno::Reference<table::XCell> xCell = getCell(aCellAddress);
 534                     if (xCell->getType() == table::CellContentType_VALUE)
 535                     {
 536                         maBounds[index].updateBound(eOp, xCell->getValue());
 537                     }
 538                     else
 539                     {
 540                         maNonBoundedConstraints.push_back(rConstraint);
 541                     }
 542                 }
 543                 else if (rConstraint.Right >>= fValue)
 544                 {
 545                     maBounds[index].updateBound(eOp, fValue);
 546                 }
 547             }
 548             index++;
 549         }
 550         if (!bFoundVariable)
 551             maNonBoundedConstraints.push_back(rConstraint);
 552     }
 553
 554     std::vector<double> aSolution;
 555
 556     if (mnAlgorithm == 0)
 557     {
 558         DifferentialEvolutionAlgorithm<SwarmSolver> aDE(*this, 50);
 559         SwarmRunner<DifferentialEvolutionAlgorithm<SwarmSolver>> aEvolution(aDE);
 560         aEvolution.setTimeout(mnTimeout);
 561         aSolution = aEvolution.solve();
 562     }
 563     else
 564     {
 565         ParticleSwarmOptimizationAlgorithm<SwarmSolver> aPSO(*this, 100);
 566         SwarmRunner<ParticleSwarmOptimizationAlgorithm<SwarmSolver>> aSwarmSolver(aPSO);
 567         aSwarmSolver.setTimeout(mnTimeout);
 568         aSolution = aSwarmSolver.solve();
 569     }
 570
 571     xModel->unlockControllers();
 572
 573     mbSuccess = true;
 574
 575     maSolution.realloc(aSolution.size());
 576     std::copy(aSolution.begin(), aSolution.end(), maSolution.begin());
 577 }
 578
 579 extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface*
 580 com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*,
 581                                                       uno::Sequence<uno::Any> const&)
 582 {
 583     return cppu::acquire(new SwarmSolver());
 584 }
 585
 586 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */