1/*
2 * Copyright 2007-2008, Christof Lutteroth, lutteroth@cs.auckland.ac.nz
3 * Copyright 2007-2008, James Kim, jkim202@ec.auckland.ac.nz
4 * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de>
5 * Distributed under the terms of the MIT License.
6 */
7
8
9#include "LinearSpec.h"
10
11#include <new>
12
13#include "ActiveSetSolver.h"
14
15
16using namespace LinearProgramming;
17
18
19// #define DEBUG_LINEAR_SPECIFICATIONS
20
21#ifdef DEBUG_LINEAR_SPECIFICATIONS
22#include <stdio.h>
23#define TRACE(x...) printf(x)
24#else
25#define TRACE(x...) /* nothing */
26#endif
27
28
29SolverInterface::SolverInterface(LinearSpec* linSpec)
30	:
31	fLinearSpec(linSpec)
32{
33
34}
35
36
37SolverInterface::~SolverInterface()
38{
39}
40
41
42bool
43SolverInterface::AddConstraint(Constraint* constraint, bool notifyListener)
44{
45	return fLinearSpec->AddConstraint(constraint, notifyListener);
46}
47
48
49bool
50SolverInterface::RemoveConstraint(Constraint* constraint, bool deleteConstraint,
51	bool notifyListener)
52{
53	return fLinearSpec->RemoveConstraint(constraint, deleteConstraint,
54		notifyListener);
55}
56
57
58SpecificationListener::~SpecificationListener()
59{
60}
61
62
63void
64SpecificationListener::VariableAdded(Variable* variable)
65{
66}
67
68
69void
70SpecificationListener::VariableRemoved(Variable* variable)
71{
72}
73
74
75void
76SpecificationListener::ConstraintAdded(Constraint* constraint)
77{
78}
79
80
81void
82SpecificationListener::ConstraintRemoved(Constraint* constraint)
83{
84}
85
86
87/**
88 * Constructor.
89 * Creates a new specification for a linear programming problem.
90 */
91LinearSpec::LinearSpec()
92	:
93	fResult(kError),
94	fSolvingTime(0)
95{
96	fSolver = new ActiveSetSolver(this);
97}
98
99
100/**
101 * Destructor.
102 * Removes the specification and deletes all constraints,
103 * objective function summands and variables.
104 */
105LinearSpec::~LinearSpec()
106{
107	for (int32 i = 0; i < fConstraints.CountItems(); i++)
108		delete (Constraint*)fConstraints.ItemAt(i);
109	while (fVariables.CountItems() > 0)
110		RemoveVariable(fVariables.ItemAt(0));
111
112	delete fSolver;
113}
114
115
116bool
117LinearSpec::AddListener(SpecificationListener* listener)
118{
119	return fListeners.AddItem(listener);
120}
121
122
123bool
124LinearSpec::RemoveListener(SpecificationListener* listener)
125{
126	return fListeners.RemoveItem(listener);
127}
128
129
130/**
131 * Adds a new variable to the specification.
132 *
133 * @return the new variable
134 */
135Variable*
136LinearSpec::AddVariable()
137{
138	Variable* variable = new(std::nothrow) Variable(this);
139	if (!variable)
140		return NULL;
141	if (!AddVariable(variable)) {
142		delete variable;
143		return NULL;
144	}
145
146	return variable;
147}
148
149
150bool
151LinearSpec::AddVariable(Variable* variable)
152{
153	if (variable->IsValid())
154		return false;
155
156	if (!fVariables.AddItem(variable))
157		return false;
158
159	if (variable->fLS == NULL)
160		variable->fLS = this;
161
162	if (!fSolver->VariableAdded(variable)) {
163		fVariables.RemoveItem(variable);
164		return false;
165	}
166	variable->fIsValid = true;
167
168	if (!UpdateRange(variable)) {
169		RemoveVariable(variable, false);
170		return false;
171	}
172
173	for (int32 i = 0; i < fListeners.CountItems(); i++)
174		fListeners.ItemAt(i)->VariableAdded(variable);
175
176	return true;
177}
178
179
180bool
181LinearSpec::RemoveVariable(Variable* variable, bool deleteVariable)
182{
183	// must be called first otherwise the index is invalid
184	if (fSolver->VariableRemoved(variable) == false)
185		return false;
186
187	// do we know the variable?
188	if (fVariables.RemoveItem(variable) == false)
189		return false;
190	fUsedVariables.RemoveItem(variable);
191	variable->fIsValid = false;
192
193	// invalidate all constraints that use this variable
194	ConstraintList markedForInvalidation;
195	const ConstraintList& constraints = Constraints();
196	for (int i = 0; i < constraints.CountItems(); i++) {
197		Constraint* constraint = constraints.ItemAt(i);
198
199		SummandList* summands = constraint->LeftSide();
200		for (int j = 0; j < summands->CountItems(); j++) {
201			Summand* summand = summands->ItemAt(j);
202			if (summand->Var() == variable) {
203				markedForInvalidation.AddItem(constraint);
204				break;
205			}
206		}
207	}
208	for (int i = 0; i < markedForInvalidation.CountItems(); i++)
209		RemoveConstraint(markedForInvalidation.ItemAt(i));
210
211	if (deleteVariable)
212		delete variable;
213
214	for (int32 i = 0; i < fListeners.CountItems(); i++)
215		fListeners.ItemAt(i)->VariableRemoved(variable);
216
217	return true;
218}
219
220
221int32
222LinearSpec::IndexOf(const Variable* variable) const
223{
224	return fUsedVariables.IndexOf(variable);
225}
226
227
228int32
229LinearSpec::GlobalIndexOf(const Variable* variable) const
230{
231	return fVariables.IndexOf(variable);
232}
233
234
235bool
236LinearSpec::UpdateRange(Variable* variable)
237{
238	if (!fSolver->VariableRangeChanged(variable))
239		return false;
240	return true;
241}
242
243
244bool
245LinearSpec::AddConstraint(Constraint* constraint)
246{
247	return AddConstraint(constraint, true);
248}
249
250
251bool
252LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint)
253{
254	return RemoveConstraint(constraint, deleteConstraint, true);
255}
256
257
258bool
259LinearSpec::AddConstraint(Constraint* constraint, bool notifyListener)
260{
261	if (!fConstraints.AddItem(constraint))
262		return false;
263
264	// ref count the used variables
265	SummandList* leftSide = constraint->LeftSide();
266	for (int i = 0; i < leftSide->CountItems(); i++) {
267		Variable* var = leftSide->ItemAt(i)->Var();
268		_AddConstraintRef(var);
269	}
270
271	if (!fSolver->ConstraintAdded(constraint)) {
272		RemoveConstraint(constraint, false);
273		return false;
274	}
275
276	constraint->fLS = this;
277
278	if (notifyListener) {
279		for (int32 i = 0; i < fListeners.CountItems(); i++)
280			fListeners.ItemAt(i)->ConstraintAdded(constraint);
281	}
282
283	return true;
284}
285
286
287bool
288LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint,
289	bool notifyListener)
290{
291	if (constraint == NULL)
292		return false;
293	fSolver->ConstraintRemoved(constraint);
294	if (!fConstraints.RemoveItem(constraint))
295		return false;
296
297	SummandList* leftSide = constraint->LeftSide();
298	for (int32 i = 0; i < leftSide->CountItems(); i++) {
299		Variable* var = leftSide->ItemAt(i)->Var();
300		_RemoveConstraintRef(var);
301	}
302
303	if (notifyListener) {
304		for (int32 i = 0; i < fListeners.CountItems(); i++)
305			fListeners.ItemAt(i)->ConstraintRemoved(constraint);
306	}
307
308	constraint->fLS = NULL;
309	if (deleteConstraint)
310		delete constraint;
311
312	return true;
313}
314
315
316void
317LinearSpec::_AddConstraintRef(Variable* var)
318{
319	if (var->AddReference() == 1)
320		fUsedVariables.AddItem(var);
321}
322
323
324void
325LinearSpec::_RemoveConstraintRef(Variable* var)
326{
327	if (var->RemoveReference() == 0)
328		fUsedVariables.RemoveItem(var);
329}
330
331
332bool
333LinearSpec::UpdateLeftSide(Constraint* constraint,
334	const SummandList* oldSummands)
335{
336	SummandList* leftSide = constraint->LeftSide();
337	if (leftSide != NULL) {
338		for (int32 i = 0; i < leftSide->CountItems(); i++) {
339			Variable* var = leftSide->ItemAt(i)->Var();
340			_AddConstraintRef(var);
341		}
342	}
343	if (oldSummands != NULL) {
344		// the summands have changed, update the var ref count
345		for (int32 i = 0; i < oldSummands->CountItems(); i++) {
346			Variable* var = oldSummands->ItemAt(i)->Var();
347			_RemoveConstraintRef(var);
348		}
349	}
350
351	if (!fSolver->LeftSideChanged(constraint))
352		return false;
353	return true;
354}
355
356
357bool
358LinearSpec::UpdateRightSide(Constraint* constraint)
359{
360	if (!fSolver->RightSideChanged(constraint))
361		return false;
362	return true;
363}
364
365
366bool
367LinearSpec::UpdateOperator(Constraint* constraint)
368{
369	if (!fSolver->OperatorChanged(constraint))
370		return false;
371	return true;
372}
373
374
375bool
376LinearSpec::UpdatePenalties(Constraint* constraint)
377{
378	if (!fSolver->PenaltiesChanged(constraint))
379		return false;
380	return true;
381}
382
383
384/**
385 * Adds a new soft linear constraint to the specification.
386 * i.e. a constraint that does not always have to be satisfied.
387 *
388 * @param coeffs		the constraint's coefficients
389 * @param vars			the constraint's variables
390 * @param op			the constraint's operand
391 * @param rightSide		the constant value on the constraint's right side
392 * @param penaltyNeg	the coefficient penalizing negative deviations from the exact solution
393 * @param penaltyPos	the coefficient penalizing positive deviations from the exact solution
394 */
395Constraint*
396LinearSpec::AddConstraint(SummandList* summands, OperatorType op,
397		double rightSide, double penaltyNeg, double penaltyPos)
398{
399	return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos);
400}
401
402
403/**
404 * Adds a new soft linear constraint to the specification with a single summand.
405 *
406 * @param coeff1		the constraint's first coefficient
407 * @param var1			the constraint's first variable
408 * @param op			the constraint's operand
409 * @param rightSide		the constant value on the constraint's right side
410 * @param penaltyNeg	the coefficient penalizing negative deviations from the exact solution
411 * @param penaltyPos	the coefficient penalizing positive deviations from the exact solution
412 */
413Constraint*
414LinearSpec::AddConstraint(double coeff1, Variable* var1,
415		OperatorType op, double rightSide, double penaltyNeg, double penaltyPos)
416{
417	SummandList* summands = new(std::nothrow) SummandList(1);
418	if (!summands)
419		return NULL;
420	summands->AddItem(new(std::nothrow) Summand(coeff1, var1));
421	if (!_CheckSummandList(summands))
422		return NULL;
423	return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos);
424}
425
426
427/**
428 * Adds a new soft linear constraint to the specification with two summands.
429 *
430 * @param coeff1		the constraint's first coefficient
431 * @param var1			the constraint's first variable
432 * @param coeff2		the constraint's second coefficient
433 * @param var2			the constraint's second variable
434 * @param op			the constraint's operand
435 * @param rightSide		the constant value on the constraint's right side
436 * @param penaltyNeg	the coefficient penalizing negative deviations from the exact solution
437 * @param penaltyPos	the coefficient penalizing positive deviations from the exact solution
438 */
439Constraint*
440LinearSpec::AddConstraint(double coeff1, Variable* var1,
441	double coeff2, Variable* var2, OperatorType op, double rightSide,
442	double penaltyNeg, double penaltyPos)
443{
444	SummandList* summands = new(std::nothrow) SummandList(2);
445	if (!summands)
446		return NULL;
447	summands->AddItem(new(std::nothrow) Summand(coeff1, var1));
448	summands->AddItem(new(std::nothrow) Summand(coeff2, var2));
449	if (!_CheckSummandList(summands))
450		return NULL;
451	return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos);
452}
453
454
455/**
456 * Adds a new soft linear constraint to the specification with three summands.
457 *
458 * @param coeff1		the constraint's first coefficient
459 * @param var1			the constraint's first variable
460 * @param coeff2		the constraint's second coefficient
461 * @param var2			the constraint's second variable
462 * @param coeff3		the constraint's third coefficient
463 * @param var3			the constraint's third variable
464 * @param op			the constraint's operand
465 * @param rightSide		the constant value on the constraint's right side
466 * @param penaltyNeg	the coefficient penalizing negative deviations from the exact solution
467 * @param penaltyPos	the coefficient penalizing positive deviations from the exact solution
468 */
469Constraint*
470LinearSpec::AddConstraint(double coeff1, Variable* var1,
471	double coeff2, Variable* var2, double coeff3, Variable* var3,
472	OperatorType op, double rightSide, double penaltyNeg, double penaltyPos)
473{
474	SummandList* summands = new(std::nothrow) SummandList(2);
475	if (!summands)
476		return NULL;
477	summands->AddItem(new(std::nothrow) Summand(coeff1, var1));
478	summands->AddItem(new(std::nothrow) Summand(coeff2, var2));
479	summands->AddItem(new(std::nothrow) Summand(coeff3, var3));
480	if (!_CheckSummandList(summands))
481		return NULL;
482	return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos);
483}
484
485
486/**
487 * Adds a new soft linear constraint to the specification with four summands.
488 *
489 * @param coeff1		the constraint's first coefficient
490 * @param var1			the constraint's first variable
491 * @param coeff2		the constraint's second coefficient
492 * @param var2			the constraint's second variable
493 * @param coeff3		the constraint's third coefficient
494 * @param var3			the constraint's third variable
495 * @param coeff4		the constraint's fourth coefficient
496 * @param var4			the constraint's fourth variable
497 * @param op			the constraint's operand
498 * @param rightSide		the constant value on the constraint's right side
499 * @param penaltyNeg	the coefficient penalizing negative deviations from the exact solution
500 * @param penaltyPos	the coefficient penalizing positive deviations from the exact solution
501 */
502Constraint*
503LinearSpec::AddConstraint(double coeff1, Variable* var1,
504	double coeff2, Variable* var2, double coeff3, Variable* var3,
505	double coeff4, Variable* var4, OperatorType op, double rightSide,
506	double penaltyNeg, double penaltyPos)
507{
508	SummandList* summands = new(std::nothrow) SummandList(2);
509	if (!summands)
510		return NULL;
511	summands->AddItem(new(std::nothrow) Summand(coeff1, var1));
512	summands->AddItem(new(std::nothrow) Summand(coeff2, var2));
513	summands->AddItem(new(std::nothrow) Summand(coeff3, var3));
514	summands->AddItem(new(std::nothrow) Summand(coeff4, var4));
515	if (!_CheckSummandList(summands))
516		return NULL;
517	return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos);
518}
519
520
521ResultType
522LinearSpec::FindMins(const VariableList* variables)
523{
524	fResult = fSolver->FindMins(variables);
525	return fResult;
526}
527
528
529ResultType
530LinearSpec::FindMaxs(const VariableList* variables)
531{
532	fResult = fSolver->FindMaxs(variables);
533	return fResult;
534}
535
536
537bool
538LinearSpec::_CheckSummandList(SummandList* list)
539{
540	bool ok = true;
541	for (int i = 0; i < list->CountItems(); i++) {
542		if (list->ItemAt(i) == NULL) {
543			ok = false;
544			break;
545		}
546	}
547	if (ok)
548		return true;
549
550	for (int i = 0; i < list->CountItems(); i++)
551		delete list->ItemAt(i);
552	delete list;
553	return false;
554}
555
556
557Constraint*
558LinearSpec::_AddConstraint(SummandList* leftSide, OperatorType op,
559	double rightSide, double penaltyNeg, double penaltyPos)
560{
561	Constraint* constraint = new(std::nothrow) Constraint(this, leftSide,
562		op, rightSide, penaltyNeg, penaltyPos);
563	if (constraint == NULL)
564		return NULL;
565	if (!AddConstraint(constraint)) {
566		delete constraint;
567		return NULL;
568	}
569	return constraint;
570}
571
572
573#ifdef DEBUG_LINEAR_SPECIFICATIONS
574static bigtime_t sAverageSolvingTime = 0;
575static int32 sSolvedCount = 0;
576#endif
577
578
579ResultType
580LinearSpec::Solve()
581{
582	bigtime_t startTime = system_time();
583
584	fResult = fSolver->Solve();
585
586	fSolvingTime = system_time() - startTime;
587
588#ifdef DEBUG_LINEAR_SPECIFICATIONS
589	sAverageSolvingTime += fSolvingTime;
590	sSolvedCount++;
591	TRACE("Solving time %i average %i [micro s]\n", (int)fSolvingTime,
592		int(sAverageSolvingTime / sSolvedCount));
593#endif
594
595	return fResult;
596}
597
598
599/**
600 * Writes the specification into a text file.
601 * The file will be overwritten if it exists.
602 *
603 * @param fname	the file name
604 */
605bool
606LinearSpec::Save(const char* fileName)
607{
608	return fSolver->SaveModel(fileName) == B_OK;
609}
610
611
612/**
613 * Gets the constraints generated by calls to Variable::SetRange()
614 *
615 */
616void
617LinearSpec::GetRangeConstraints(const Variable* var, const Constraint** _min,
618	const Constraint** _max) const
619{
620	fSolver->GetRangeConstraints(var, _min, _max);
621}
622
623
624/**
625 * Gets the constraints.
626 *
627 * @return the constraints
628 */
629const ConstraintList&
630LinearSpec::Constraints() const
631{
632	return fConstraints;
633}
634
635
636const VariableList&
637LinearSpec::UsedVariables() const
638{
639	return fUsedVariables;
640}
641
642
643const VariableList&
644LinearSpec::AllVariables() const
645{
646	return fVariables;
647}
648
649
650/**
651 * Gets the result type.
652 *
653 * @return the result type
654 */
655ResultType
656LinearSpec::Result() const
657{
658	return fResult;
659}
660
661
662/**
663 * Gets the solving time.
664 *
665 * @return the solving time
666 */
667bigtime_t
668LinearSpec::SolvingTime() const
669{
670	return fSolvingTime;
671}
672
673
674BString
675LinearSpec::ToString() const
676{
677	BString string;
678	string << "LinearSpec " << (addr_t)this << ":\n";
679	for (int i = 0; i < fVariables.CountItems(); i++) {
680		Variable* variable = fVariables.ItemAt(i);
681		string += variable->ToString();
682		string << "=" << (float)variable->Value() << " ";
683	}
684	string << "\n";
685	for (int i = 0; i < fConstraints.CountItems(); i++) {
686		Constraint* c = fConstraints.ItemAt(i);
687		string << i << ": ";
688		string += c->ToString();
689		string << "\n";
690	}
691	string << "Result=";
692	if (fResult == kError)
693		string << "kError";
694	else if (fResult == kOptimal)
695		string << "kOptimal";
696	else if (fResult == kSuboptimal)
697		string << "kSuboptimal";
698	else if (fResult == kInfeasible)
699		string << "kInfeasible";
700	else if (fResult == kUnbounded)
701		string << "kUnbounded";
702	else if (fResult == kDegenerate)
703		string << "kDegenerate";
704	else if (fResult == kNumFailure)
705		string << "kNumFailure";
706	else
707		string << fResult;
708	string << " SolvingTime=" << fSolvingTime << "micro s";
709	return string;
710}
711
712