1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*************************************************************************
3 *
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * Copyright 2000, 2010 Oracle and/or its affiliates.
7 *
8 * OpenOffice.org - a multi-platform office productivity suite
9 *
10 * This file is part of OpenOffice.org.
11 *
12 * OpenOffice.org is free software: you can redistribute it and/or modify
13 * it under the terms of the GNU Lesser General Public License version 3
14 * only, as published by the Free Software Foundation.
15 *
16 * OpenOffice.org is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU Lesser General Public License version 3 for more details
20 * (a copy is included in the LICENSE file that accompanied this code).
21 *
22 * You should have received a copy of the GNU Lesser General Public License
23 * version 3 along with OpenOffice.org. If not, see
24 * <http://www.openoffice.org/license.html>
25 * for a copy of the LGPLv3 License.
26 *
27 * This file incorporates work covered by the following license notice:
28 *
29 * Licensed to the Apache Software Foundation (ASF) under one or more
30 * contributor license agreements. See the NOTICE file distributed
31 * with this work for additional information regarding copyright
32 * ownership. The ASF licenses this file to you under the Apache
33 * License, Version 2.0 (the "License"); you may not use this file
34 * except in compliance with the License. You may obtain a copy of
35 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
36 *
37 ************************************************************************/
38
39 #include <sal/config.h>
40
41 #undef LANGUAGE_NONE
42 #if defined _WIN32
43 #define WINAPI __stdcall
44 #endif
45 #define LoadInverseLib FALSE
46 #define LoadLanguageLib FALSE
47 #ifdef SYSTEM_LPSOLVE
48 #include <lpsolve/lp_lib.h>
49 #else
50 #include <lp_lib.h>
51 #endif
52 #undef LANGUAGE_NONE
53
54 #include "SolverComponent.hxx"
55 #include <strings.hrc>
56
57 #include <com/sun/star/frame/XModel.hpp>
58 #include <com/sun/star/table/CellAddress.hpp>
59 #include <rtl/math.hxx>
60 #include <memory>
61 #include <vector>
62
63 namespace com::sun::star::uno { class XComponentContext; }
64
65 using namespace com::sun::star;
66
67 class LpsolveSolver : public SolverComponent
68 {
69 public:
LpsolveSolver()70 LpsolveSolver() {}
71
72 private:
73 virtual void SAL_CALL solve() override;
getImplementationName()74 virtual OUString SAL_CALL getImplementationName() override
75 {
76 return "com.sun.star.comp.Calc.LpsolveSolver";
77 }
getComponentDescription()78 virtual OUString SAL_CALL getComponentDescription() override
79 {
80 return SolverComponent::GetResourceString( RID_SOLVER_COMPONENT );
81 }
82 };
83
solve()84 void SAL_CALL LpsolveSolver::solve()
85 {
86 uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY_THROW );
87
88 maStatus.clear();
89 mbSuccess = false;
90
91 if ( mnEpsilonLevel < EPS_TIGHT || mnEpsilonLevel > EPS_BAGGY )
92 {
93 maStatus = SolverComponent::GetResourceString( RID_ERROR_EPSILONLEVEL );
94 return;
95 }
96
97 xModel->lockControllers();
98
99 // collect variables in vector (?)
100
101 auto aVariableCells = comphelper::sequenceToContainer<std::vector<table::CellAddress>>(maVariables);
102 size_t nVariables = aVariableCells.size();
103 size_t nVar = 0;
104
105 // collect all dependent cells
106
107 ScSolverCellHashMap aCellsHash;
108 aCellsHash[maObjective].reserve( nVariables + 1 ); // objective function
109
110 for (const auto& rConstr : std::as_const(maConstraints))
111 {
112 table::CellAddress aCellAddr = rConstr.Left;
113 aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: left hand side
114
115 if ( rConstr.Right >>= aCellAddr )
116 aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: right hand side
117 }
118
119 // set all variables to zero
120 //! store old values?
121 //! use old values as initial values?
122 for ( const auto& rVarCell : aVariableCells )
123 {
124 SolverComponent::SetValue( mxDoc, rVarCell, 0.0 );
125 }
126
127 // read initial values from all dependent cells
128 for ( auto& rEntry : aCellsHash )
129 {
130 double fValue = SolverComponent::GetValue( mxDoc, rEntry.first );
131 rEntry.second.push_back( fValue ); // store as first element, as-is
132 }
133
134 // loop through variables
135 for ( const auto& rVarCell : aVariableCells )
136 {
137 SolverComponent::SetValue( mxDoc, rVarCell, 1.0 ); // set to 1 to examine influence
138
139 // read value change from all dependent cells
140 for ( auto& rEntry : aCellsHash )
141 {
142 double fChanged = SolverComponent::GetValue( mxDoc, rEntry.first );
143 double fInitial = rEntry.second.front();
144 rEntry.second.push_back( fChanged - fInitial );
145 }
146
147 SolverComponent::SetValue( mxDoc, rVarCell, 2.0 ); // minimal test for linearity
148
149 for ( const auto& rEntry : aCellsHash )
150 {
151 double fInitial = rEntry.second.front();
152 double fCoeff = rEntry.second.back(); // last appended: coefficient for this variable
153 double fTwo = SolverComponent::GetValue( mxDoc, rEntry.first );
154
155 bool bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
156 rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
157 // second comparison is needed in case fTwo is zero
158 if ( !bLinear )
159 maStatus = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR );
160 }
161
162 SolverComponent::SetValue( mxDoc, rVarCell, 0.0 ); // set back to zero for examining next variable
163 }
164
165 xModel->unlockControllers();
166
167 if ( !maStatus.isEmpty() )
168 return;
169
170
171 // build lp_solve model
172
173
174 lprec* lp = make_lp( 0, nVariables );
175 if ( !lp )
176 return;
177
178 set_outputfile( lp, const_cast<char*>( "" ) ); // no output
179
180 // set objective function
181
182 const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
183 std::unique_ptr<REAL[]> pObjVal(new REAL[nVariables+1]);
184 pObjVal[0] = 0.0; // ignored
185 for (nVar=0; nVar<nVariables; nVar++)
186 pObjVal[nVar+1] = rObjCoeff[nVar+1];
187 set_obj_fn( lp, pObjVal.get() );
188 pObjVal.reset();
189 set_rh( lp, 0, rObjCoeff[0] ); // constant term of objective
190
191 // add rows
192
193 set_add_rowmode(lp, TRUE);
194
195 for (const auto& rConstr : std::as_const(maConstraints))
196 {
197 // integer constraints are set later
198 sheet::SolverConstraintOperator eOp = rConstr.Operator;
199 if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
200 eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
201 eOp == sheet::SolverConstraintOperator_EQUAL )
202 {
203 double fDirectValue = 0.0;
204 bool bRightCell = false;
205 table::CellAddress aRightAddr;
206 const uno::Any& rRightAny = rConstr.Right;
207 if ( rRightAny >>= aRightAddr )
208 bRightCell = true; // cell specified as right-hand side
209 else
210 rRightAny >>= fDirectValue; // constant value
211
212 table::CellAddress aLeftAddr = rConstr.Left;
213
214 const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
215 std::unique_ptr<REAL[]> pValues(new REAL[nVariables+1] );
216 pValues[0] = 0.0; // ignored?
217 for (nVar=0; nVar<nVariables; nVar++)
218 pValues[nVar+1] = rLeftCoeff[nVar+1];
219
220 // if left hand cell has a constant term, put into rhs value
221 double fRightValue = -rLeftCoeff[0];
222
223 if ( bRightCell )
224 {
225 const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
226 // modify pValues with rhs coefficients
227 for (nVar=0; nVar<nVariables; nVar++)
228 pValues[nVar+1] -= rRightCoeff[nVar+1];
229
230 fRightValue += rRightCoeff[0]; // constant term
231 }
232 else
233 fRightValue += fDirectValue;
234
235 int nConstrType = LE;
236 switch ( eOp )
237 {
238 case sheet::SolverConstraintOperator_LESS_EQUAL: nConstrType = LE; break;
239 case sheet::SolverConstraintOperator_GREATER_EQUAL: nConstrType = GE; break;
240 case sheet::SolverConstraintOperator_EQUAL: nConstrType = EQ; break;
241 default:
242 OSL_FAIL( "unexpected enum type" );
243 }
244 add_constraint( lp, pValues.get(), nConstrType, fRightValue );
245 }
246 }
247
248 set_add_rowmode(lp, FALSE);
249
250 // apply settings to all variables
251
252 for (nVar=0; nVar<nVariables; nVar++)
253 {
254 if ( !mbNonNegative )
255 set_unbounded(lp, nVar+1); // allow negative (default is non-negative)
256 //! collect bounds from constraints?
257 if ( mbInteger )
258 set_int(lp, nVar+1, TRUE);
259 }
260
261 // apply single-var integer constraints
262
263 for (const auto& rConstr : std::as_const(maConstraints))
264 {
265 sheet::SolverConstraintOperator eOp = rConstr.Operator;
266 if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
267 eOp == sheet::SolverConstraintOperator_BINARY )
268 {
269 table::CellAddress aLeftAddr = rConstr.Left;
270 // find variable index for cell
271 for (nVar=0; nVar<nVariables; nVar++)
272 if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
273 {
274 if ( eOp == sheet::SolverConstraintOperator_INTEGER )
275 set_int(lp, nVar+1, TRUE);
276 else
277 set_binary(lp, nVar+1, TRUE);
278 }
279 }
280 }
281
282 if ( mbMaximize )
283 set_maxim(lp);
284 else
285 set_minim(lp);
286
287 if ( !mbLimitBBDepth )
288 set_bb_depthlimit( lp, 0 );
289
290 set_epslevel( lp, mnEpsilonLevel );
291 set_timeout( lp, mnTimeout );
292
293 // solve model
294
295 int nResult = ::solve( lp );
296
297 mbSuccess = ( nResult == OPTIMAL );
298 if ( mbSuccess )
299 {
300 // get solution
301
302 maSolution.realloc( nVariables );
303
304 REAL* pResultVar = nullptr;
305 get_ptr_variables( lp, &pResultVar );
306 for (nVar=0; nVar<nVariables; nVar++)
307 maSolution[nVar] = pResultVar[nVar];
308
309 mfResultValue = get_objective( lp );
310 }
311 else if ( nResult == INFEASIBLE )
312 maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE );
313 else if ( nResult == UNBOUNDED )
314 maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED );
315 else if ( nResult == TIMEOUT || nResult == SUBOPTIMAL )
316 maStatus = SolverComponent::GetResourceString( RID_ERROR_TIMEOUT );
317 // SUBOPTIMAL is assumed to be caused by a timeout, and reported as an error
318
319 delete_lp( lp );
320 }
321
322 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 &)323 com_sun_star_comp_Calc_LpsolveSolver_get_implementation(
324 css::uno::XComponentContext *,
325 css::uno::Sequence<css::uno::Any> const &)
326 {
327 return cppu::acquire(new LpsolveSolver());
328 }
329
330 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
331