Line data Source code
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 : #include <config_lgpl.h>
41 :
42 : #undef LANGUAGE_NONE
43 : #if defined SAL_W32
44 : #define WINAPI __stdcall
45 : #endif
46 : #define LoadInverseLib FALSE
47 : #define LoadLanguageLib FALSE
48 : #ifdef SYSTEM_LPSOLVE
49 : #include <lpsolve/lp_lib.h>
50 : #else
51 : #include <lp_lib.h>
52 : #endif
53 : #undef LANGUAGE_NONE
54 :
55 : #include "SolverComponent.hxx"
56 : #include "solver.hrc"
57 :
58 : #include <com/sun/star/frame/XModel.hpp>
59 : #include <com/sun/star/table/CellAddress.hpp>
60 : #include <com/sun/star/uno/XComponentContext.hpp>
61 : #include <rtl/math.hxx>
62 : #include <cppuhelper/supportsservice.hxx>
63 : #include <vector>
64 :
65 : using namespace com::sun::star;
66 :
67 : class LpsolveSolver : public SolverComponent
68 : {
69 : public:
70 0 : LpsolveSolver() {}
71 0 : virtual ~LpsolveSolver() {}
72 :
73 : private:
74 : virtual void SAL_CALL solve() throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE;
75 0 : virtual OUString SAL_CALL getImplementationName()
76 : throw(css::uno::RuntimeException, std::exception) SAL_OVERRIDE
77 : {
78 0 : return OUString("com.sun.star.comp.Calc.LpsolveSolver");
79 : }
80 0 : virtual OUString SAL_CALL getComponentDescription()
81 : throw (uno::RuntimeException, std::exception) SAL_OVERRIDE
82 : {
83 0 : return SolverComponent::GetResourceString( RID_SOLVER_COMPONENT );
84 : }
85 : };
86 :
87 0 : void SAL_CALL LpsolveSolver::solve() throw(uno::RuntimeException, std::exception)
88 : {
89 0 : uno::Reference<frame::XModel> xModel( mxDoc, uno::UNO_QUERY );
90 0 : if ( !xModel.is() )
91 0 : throw uno::RuntimeException();
92 :
93 0 : maStatus.clear();
94 0 : mbSuccess = false;
95 :
96 0 : if ( mnEpsilonLevel < EPS_TIGHT || mnEpsilonLevel > EPS_BAGGY )
97 : {
98 0 : maStatus = SolverComponent::GetResourceString( RID_ERROR_EPSILONLEVEL );
99 0 : return;
100 : }
101 :
102 0 : xModel->lockControllers();
103 :
104 : // collect variables in vector (?)
105 :
106 0 : std::vector<table::CellAddress> aVariableCells;
107 0 : for (sal_Int32 nPos=0; nPos<maVariables.getLength(); nPos++)
108 0 : aVariableCells.push_back( maVariables[nPos] );
109 0 : size_t nVariables = aVariableCells.size();
110 0 : size_t nVar = 0;
111 :
112 : // collect all dependent cells
113 :
114 0 : ScSolverCellHashMap aCellsHash;
115 0 : aCellsHash[maObjective].reserve( nVariables + 1 ); // objective function
116 :
117 0 : for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
118 : {
119 0 : table::CellAddress aCellAddr = maConstraints[nConstrPos].Left;
120 0 : aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: left hand side
121 :
122 0 : if ( maConstraints[nConstrPos].Right >>= aCellAddr )
123 0 : aCellsHash[aCellAddr].reserve( nVariables + 1 ); // constraints: right hand side
124 : }
125 :
126 : // set all variables to zero
127 : //! store old values?
128 : //! use old values as initial values?
129 0 : std::vector<table::CellAddress>::const_iterator aVarIter;
130 0 : for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
131 : {
132 0 : SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 );
133 : }
134 :
135 : // read initial values from all dependent cells
136 0 : ScSolverCellHashMap::iterator aCellsIter;
137 0 : for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
138 : {
139 0 : double fValue = SolverComponent::GetValue( mxDoc, aCellsIter->first );
140 0 : aCellsIter->second.push_back( fValue ); // store as first element, as-is
141 : }
142 :
143 : // loop through variables
144 0 : for ( aVarIter = aVariableCells.begin(); aVarIter != aVariableCells.end(); ++aVarIter )
145 : {
146 0 : SolverComponent::SetValue( mxDoc, *aVarIter, 1.0 ); // set to 1 to examine influence
147 :
148 : // read value change from all dependent cells
149 0 : for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
150 : {
151 0 : double fChanged = SolverComponent::GetValue( mxDoc, aCellsIter->first );
152 0 : double fInitial = aCellsIter->second.front();
153 0 : aCellsIter->second.push_back( fChanged - fInitial );
154 : }
155 :
156 0 : SolverComponent::SetValue( mxDoc, *aVarIter, 2.0 ); // minimal test for linearity
157 :
158 0 : for ( aCellsIter = aCellsHash.begin(); aCellsIter != aCellsHash.end(); ++aCellsIter )
159 : {
160 0 : double fInitial = aCellsIter->second.front();
161 0 : double fCoeff = aCellsIter->second.back(); // last appended: coefficient for this variable
162 0 : double fTwo = SolverComponent::GetValue( mxDoc, aCellsIter->first );
163 :
164 0 : bool bLinear = rtl::math::approxEqual( fTwo, fInitial + 2.0 * fCoeff ) ||
165 0 : rtl::math::approxEqual( fInitial, fTwo - 2.0 * fCoeff );
166 : // second comparison is needed in case fTwo is zero
167 0 : if ( !bLinear )
168 0 : maStatus = SolverComponent::GetResourceString( RID_ERROR_NONLINEAR );
169 : }
170 :
171 0 : SolverComponent::SetValue( mxDoc, *aVarIter, 0.0 ); // set back to zero for examining next variable
172 : }
173 :
174 0 : xModel->unlockControllers();
175 :
176 0 : if ( !maStatus.isEmpty() )
177 0 : return;
178 :
179 :
180 : // build lp_solve model
181 :
182 :
183 0 : lprec* lp = make_lp( 0, nVariables );
184 0 : if ( !lp )
185 0 : return;
186 :
187 0 : set_outputfile( lp, const_cast<char*>( "" ) ); // no output
188 :
189 : // set objective function
190 :
191 0 : const std::vector<double>& rObjCoeff = aCellsHash[maObjective];
192 0 : REAL* pObjVal = new REAL[nVariables+1];
193 0 : pObjVal[0] = 0.0; // ignored
194 0 : for (nVar=0; nVar<nVariables; nVar++)
195 0 : pObjVal[nVar+1] = rObjCoeff[nVar+1];
196 0 : set_obj_fn( lp, pObjVal );
197 0 : delete[] pObjVal;
198 0 : set_rh( lp, 0, rObjCoeff[0] ); // constant term of objective
199 :
200 : // add rows
201 :
202 0 : set_add_rowmode(lp, TRUE);
203 :
204 0 : for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
205 : {
206 : // integer constraints are set later
207 0 : sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
208 0 : if ( eOp == sheet::SolverConstraintOperator_LESS_EQUAL ||
209 0 : eOp == sheet::SolverConstraintOperator_GREATER_EQUAL ||
210 : eOp == sheet::SolverConstraintOperator_EQUAL )
211 : {
212 0 : double fDirectValue = 0.0;
213 0 : bool bRightCell = false;
214 0 : table::CellAddress aRightAddr;
215 0 : const uno::Any& rRightAny = maConstraints[nConstrPos].Right;
216 0 : if ( rRightAny >>= aRightAddr )
217 0 : bRightCell = true; // cell specified as right-hand side
218 : else
219 0 : rRightAny >>= fDirectValue; // constant value
220 :
221 0 : table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
222 :
223 0 : const std::vector<double>& rLeftCoeff = aCellsHash[aLeftAddr];
224 0 : REAL* pValues = new REAL[nVariables+1];
225 0 : pValues[0] = 0.0; // ignored?
226 0 : for (nVar=0; nVar<nVariables; nVar++)
227 0 : pValues[nVar+1] = rLeftCoeff[nVar+1];
228 :
229 : // if left hand cell has a constant term, put into rhs value
230 0 : double fRightValue = -rLeftCoeff[0];
231 :
232 0 : if ( bRightCell )
233 : {
234 0 : const std::vector<double>& rRightCoeff = aCellsHash[aRightAddr];
235 : // modify pValues with rhs coefficients
236 0 : for (nVar=0; nVar<nVariables; nVar++)
237 0 : pValues[nVar+1] -= rRightCoeff[nVar+1];
238 :
239 0 : fRightValue += rRightCoeff[0]; // constant term
240 : }
241 : else
242 0 : fRightValue += fDirectValue;
243 :
244 0 : int nConstrType = LE;
245 0 : switch ( eOp )
246 : {
247 0 : case sheet::SolverConstraintOperator_LESS_EQUAL: nConstrType = LE; break;
248 0 : case sheet::SolverConstraintOperator_GREATER_EQUAL: nConstrType = GE; break;
249 0 : case sheet::SolverConstraintOperator_EQUAL: nConstrType = EQ; break;
250 : default:
251 : OSL_FAIL( "unexpected enum type" );
252 : }
253 0 : add_constraint( lp, pValues, nConstrType, fRightValue );
254 :
255 0 : delete[] pValues;
256 : }
257 : }
258 :
259 0 : set_add_rowmode(lp, FALSE);
260 :
261 : // apply settings to all variables
262 :
263 0 : for (nVar=0; nVar<nVariables; nVar++)
264 : {
265 0 : if ( !mbNonNegative )
266 0 : set_unbounded(lp, nVar+1); // allow negative (default is non-negative)
267 : //! collect bounds from constraints?
268 0 : if ( mbInteger )
269 0 : set_int(lp, nVar+1, TRUE);
270 : }
271 :
272 : // apply single-var integer constraints
273 :
274 0 : for (sal_Int32 nConstrPos = 0; nConstrPos < maConstraints.getLength(); ++nConstrPos)
275 : {
276 0 : sheet::SolverConstraintOperator eOp = maConstraints[nConstrPos].Operator;
277 0 : if ( eOp == sheet::SolverConstraintOperator_INTEGER ||
278 : eOp == sheet::SolverConstraintOperator_BINARY )
279 : {
280 0 : table::CellAddress aLeftAddr = maConstraints[nConstrPos].Left;
281 : // find variable index for cell
282 0 : for (nVar=0; nVar<nVariables; nVar++)
283 0 : if ( AddressEqual( aVariableCells[nVar], aLeftAddr ) )
284 : {
285 0 : if ( eOp == sheet::SolverConstraintOperator_INTEGER )
286 0 : set_int(lp, nVar+1, TRUE);
287 : else
288 0 : set_binary(lp, nVar+1, TRUE);
289 : }
290 : }
291 : }
292 :
293 0 : if ( mbMaximize )
294 0 : set_maxim(lp);
295 : else
296 0 : set_minim(lp);
297 :
298 0 : if ( !mbLimitBBDepth )
299 0 : set_bb_depthlimit( lp, 0 );
300 :
301 0 : set_epslevel( lp, mnEpsilonLevel );
302 0 : set_timeout( lp, mnTimeout );
303 :
304 : // solve model
305 :
306 0 : int nResult = ::solve( lp );
307 :
308 0 : mbSuccess = ( nResult == OPTIMAL );
309 0 : if ( mbSuccess )
310 : {
311 : // get solution
312 :
313 0 : maSolution.realloc( nVariables );
314 :
315 0 : REAL* pResultVar = NULL;
316 0 : get_ptr_variables( lp, &pResultVar );
317 0 : for (nVar=0; nVar<nVariables; nVar++)
318 0 : maSolution[nVar] = pResultVar[nVar];
319 :
320 0 : mfResultValue = get_objective( lp );
321 : }
322 0 : else if ( nResult == INFEASIBLE )
323 0 : maStatus = SolverComponent::GetResourceString( RID_ERROR_INFEASIBLE );
324 0 : else if ( nResult == UNBOUNDED )
325 0 : maStatus = SolverComponent::GetResourceString( RID_ERROR_UNBOUNDED );
326 0 : else if ( nResult == TIMEOUT || nResult == SUBOPTIMAL )
327 0 : maStatus = SolverComponent::GetResourceString( RID_ERROR_TIMEOUT );
328 : // SUBOPTIMAL is assumed to be caused by a timeout, and reported as an error
329 :
330 0 : delete_lp( lp );
331 : }
332 :
333 : extern "C" SAL_DLLPUBLIC_EXPORT css::uno::XInterface * SAL_CALL
334 0 : com_sun_star_comp_Calc_LpsolveSolver_get_implementation(
335 : css::uno::XComponentContext *,
336 : css::uno::Sequence<css::uno::Any> const &)
337 : {
338 0 : return cppu::acquire(new LpsolveSolver());
339 : }
340 :
341 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
