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
Bound__anon6167e3090111::Bound59 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
updateBound__anon6167e3090111::Bound67 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:
SwarmSolver()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()
DECLARE_XTYPEPROVIDER()157 DECLARE_XTYPEPROVIDER()
158
159 virtual uno::Reference<beans::XPropertySetInfo> SAL_CALL getPropertySetInfo() override
160 {
161 return createPropertySetInfo(getInfoHelper());
162 }
163 // OPropertySetHelper
getInfoHelper()164 virtual cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override
165 {
166 return *getArrayHelper();
167 }
168 // OPropertyArrayUsageHelper
createArrayHelper() const169 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
getDocument()177 virtual uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL getDocument() override
178 {
179 return mxDocument;
180 }
181 virtual void SAL_CALL
setDocument(const uno::Reference<sheet::XSpreadsheetDocument> & rDocument)182 setDocument(const uno::Reference<sheet::XSpreadsheetDocument>& rDocument) override
183 {
184 mxDocument = rDocument;
185 }
186
getObjective()187 virtual table::CellAddress SAL_CALL getObjective() override { return maObjective; }
setObjective(const table::CellAddress & rObjective)188 virtual void SAL_CALL setObjective(const table::CellAddress& rObjective) override
189 {
190 maObjective = rObjective;
191 }
192
getVariables()193 virtual uno::Sequence<table::CellAddress> SAL_CALL getVariables() override
194 {
195 return maVariables;
196 }
setVariables(const uno::Sequence<table::CellAddress> & rVariables)197 virtual void SAL_CALL setVariables(const uno::Sequence<table::CellAddress>& rVariables) override
198 {
199 maVariables = rVariables;
200 }
201
getConstraints()202 virtual uno::Sequence<sheet::SolverConstraint> SAL_CALL getConstraints() override
203 {
204 return maConstraints;
205 }
206 virtual void SAL_CALL
setConstraints(const uno::Sequence<sheet::SolverConstraint> & rConstraints)207 setConstraints(const uno::Sequence<sheet::SolverConstraint>& rConstraints) override
208 {
209 maConstraints = rConstraints;
210 }
211
getMaximize()212 virtual sal_Bool SAL_CALL getMaximize() override { return mbMaximize; }
setMaximize(sal_Bool bMaximize)213 virtual void SAL_CALL setMaximize(sal_Bool bMaximize) override { mbMaximize = bMaximize; }
214
getSuccess()215 virtual sal_Bool SAL_CALL getSuccess() override { return mbSuccess; }
getResultValue()216 virtual double SAL_CALL getResultValue() override { return 0; }
217
getSolution()218 virtual uno::Sequence<double> SAL_CALL getSolution() override { return maSolution; }
219
220 virtual void SAL_CALL solve() override;
221
222 // XSolverDescription
getComponentDescription()223 virtual OUString SAL_CALL getComponentDescription() override
224 {
225 return SwarmSolver::getResourceString(RID_SWARM_SOLVER_COMPONENT);
226 }
227
getStatusDescription()228 virtual OUString SAL_CALL getStatusDescription() override { return maStatus; }
229
getPropertyDescription(const OUString & rPropertyName)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
getImplementationName()254 virtual OUString SAL_CALL getImplementationName() override
255 {
256 return "com.sun.star.comp.Calc.SwarmSolver";
257 }
258
supportsService(const OUString & rServiceName)259 sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override
260 {
261 return cppu::supportsService(this, rServiceName);
262 }
263
getSupportedServiceNames()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
getResourceString(const char * pId)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
getCell(const table::CellAddress & rPosition)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
setValue(const table::CellAddress & rPosition,double fValue)298 void SwarmSolver::setValue(const table::CellAddress& rPosition, double fValue)
299 {
300 getCell(rPosition)->setValue(fValue);
301 }
302
getValue(const table::CellAddress & rPosition)303 double SwarmSolver::getValue(const table::CellAddress& rPosition)
304 {
305 return getCell(rPosition)->getValue();
306 }
307
IMPLEMENT_FORWARD_XINTERFACE2(SwarmSolver,SwarmSolver_Base,OPropertyContainer)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
calculateFitness(std::vector<double> const & rVariables)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
initializeVariables(std::vector<double> & rVariables,std::mt19937 & rGenerator)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
clampVariable(size_t nVarIndex,double fValue)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
boundVariable(size_t nVarIndex,double fValue)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
getDimensionality() const399 size_t SwarmSolver::getDimensionality() const { return maVariables.getLength(); }
400
doesViolateConstraints()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:
SwarmRunner(SwarmAlgorithm & rAlgorithm)464 SwarmRunner(SwarmAlgorithm& rAlgorithm)
465 : mrAlgorithm(rAlgorithm)
466 , mfTimeout(5000)
467 {
468 }
469
setTimeout(double fTimeout)470 void setTimeout(double fTimeout) { mfTimeout = fTimeout; }
471
solve()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
solve()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 if (!maVariables.getLength())
505 return;
506
507 maBounds.resize(maVariables.getLength());
508
509 xModel->lockControllers();
510
511 if (mbNonNegative)
512 {
513 for (Bound& rBound : maBounds)
514 rBound.lower = 0;
515 }
516
517 // Determine variable bounds
518 for (sheet::SolverConstraint const& rConstraint : std::as_const(maConstraints))
519 {
520 table::CellAddress aLeftCellAddress = rConstraint.Left;
521 sheet::SolverConstraintOperator eOp = rConstraint.Operator;
522
523 size_t index = 0;
524 bool bFoundVariable = false;
525 for (const table::CellAddress& rVariableCell : std::as_const(maVariables))
526 {
527 if (aLeftCellAddress == rVariableCell)
528 {
529 bFoundVariable = true;
530 table::CellAddress aCellAddress;
531 double fValue;
532
533 if (rConstraint.Right >>= aCellAddress)
534 {
535 uno::Reference<table::XCell> xCell = getCell(aCellAddress);
536 if (xCell->getType() == table::CellContentType_VALUE)
537 {
538 maBounds[index].updateBound(eOp, xCell->getValue());
539 }
540 else
541 {
542 maNonBoundedConstraints.push_back(rConstraint);
543 }
544 }
545 else if (rConstraint.Right >>= fValue)
546 {
547 maBounds[index].updateBound(eOp, fValue);
548 }
549 }
550 index++;
551 }
552 if (!bFoundVariable)
553 maNonBoundedConstraints.push_back(rConstraint);
554 }
555
556 std::vector<double> aSolution;
557
558 if (mnAlgorithm == 0)
559 {
560 DifferentialEvolutionAlgorithm<SwarmSolver> aDE(*this, 50);
561 SwarmRunner<DifferentialEvolutionAlgorithm<SwarmSolver>> aEvolution(aDE);
562 aEvolution.setTimeout(mnTimeout);
563 aSolution = aEvolution.solve();
564 }
565 else
566 {
567 ParticleSwarmOptimizationAlgorithm<SwarmSolver> aPSO(*this, 100);
568 SwarmRunner<ParticleSwarmOptimizationAlgorithm<SwarmSolver>> aSwarmSolver(aPSO);
569 aSwarmSolver.setTimeout(mnTimeout);
570 aSolution = aSwarmSolver.solve();
571 }
572
573 xModel->unlockControllers();
574
575 mbSuccess = true;
576
577 maSolution.realloc(aSolution.size());
578 std::copy(aSolution.begin(), aSolution.end(), maSolution.begin());
579 }
580
581 extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface*
com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext *,uno::Sequence<uno::Any> const &)582 com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*,
583 uno::Sequence<uno::Any> const&)
584 {
585 return cppu::acquire(new SwarmSolver());
586 }
587
588 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
589