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#ifndef	LINEAR_SPEC_H
8#define	LINEAR_SPEC_H
9
10#include <ObjectList.h>
11#include <OS.h>
12#include <Referenceable.h>
13#include <Size.h>
14#include <String.h>
15#include <SupportDefs.h>
16
17#include "Constraint.h"
18#include "LinearProgrammingTypes.h"
19#include "Summand.h"
20#include "Variable.h"
21
22
23namespace LinearProgramming {
24
25
26class LinearSpec;
27
28
29const BSize kMinSize(0, 0);
30const BSize kMaxSize(B_SIZE_UNLIMITED, B_SIZE_UNLIMITED);
31
32
33class SolverInterface {
34public:
35								SolverInterface(LinearSpec* linSpec);
36
37	virtual						~SolverInterface();
38
39	virtual ResultType			Solve() = 0;
40
41	virtual	bool				VariableAdded(Variable* variable) = 0;
42	virtual	bool				VariableRemoved(Variable* variable) = 0;
43	virtual	bool				VariableRangeChanged(Variable* variable) = 0;
44
45	virtual	bool				ConstraintAdded(Constraint* constraint) = 0;
46	virtual	bool				ConstraintRemoved(Constraint* constraint) = 0;
47	virtual	bool				LeftSideChanged(Constraint* constraint) = 0;
48	virtual	bool				RightSideChanged(Constraint* constraint) = 0;
49	virtual	bool				OperatorChanged(Constraint* constraint) = 0;
50	virtual	bool				PenaltiesChanged(Constraint* constraint) = 0;
51
52	virtual bool				SaveModel(const char* fileName) = 0;
53
54	virtual	ResultType			FindMins(const VariableList* variables) = 0;
55	virtual	ResultType			FindMaxs(const VariableList* variables) = 0;
56
57	virtual	void				GetRangeConstraints(const Variable* var,
58									const Constraint** _min,
59									const Constraint** _max) const = 0;
60
61protected:
62			bool				AddConstraint(Constraint* constraint,
63									bool notifyListener);
64			bool				RemoveConstraint(Constraint* constraint,
65									bool deleteConstraint, bool notifyListener);
66
67			LinearSpec*			fLinearSpec;
68};
69
70
71class SpecificationListener {
72public:
73	virtual						~SpecificationListener();
74
75	virtual	void				VariableAdded(Variable* variable);
76	virtual	void				VariableRemoved(Variable* variable);
77	virtual void				ConstraintAdded(Constraint* constraint);
78	virtual void				ConstraintRemoved(Constraint* constraint);
79};
80
81
82/*!
83 * Specification of a linear programming problem.
84 */
85class LinearSpec : public BReferenceable {
86public:
87								LinearSpec();
88	virtual						~LinearSpec();
89
90			/*! Does not takes ownership of the listener. */
91			bool				AddListener(SpecificationListener* listener);
92			bool				RemoveListener(SpecificationListener* listener);
93
94			Variable*			AddVariable();
95			bool				AddVariable(Variable* variable);
96			bool				RemoveVariable(Variable* variable,
97									bool deleteVariable = true);
98			int32				IndexOf(const Variable* variable) const;
99			int32				GlobalIndexOf(const Variable* variable) const;
100			bool				UpdateRange(Variable* variable);
101
102			bool				AddConstraint(Constraint* constraint);
103			bool				RemoveConstraint(Constraint* constraint,
104									bool deleteConstraint = true);
105
106			Constraint*			AddConstraint(SummandList* summands,
107									OperatorType op, double rightSide,
108									double penaltyNeg = -1,
109									double penaltyPos = -1);
110			Constraint*			AddConstraint(double coeff1, Variable* var1,
111									OperatorType op, double rightSide,
112									double penaltyNeg = -1,
113									double penaltyPos = -1);
114			Constraint*			AddConstraint(double coeff1, Variable* var1,
115									double coeff2, Variable* var2,
116									OperatorType op, double rightSide,
117									double penaltyNeg = -1,
118									double penaltyPos = -1);
119			Constraint*			AddConstraint(double coeff1, Variable* var1,
120									double coeff2, Variable* var2,
121									double coeff3, Variable* var3,
122									OperatorType op, double rightSide,
123									double penaltyNeg = -1,
124									double penaltyPos = -1);
125			Constraint*			AddConstraint(double coeff1, Variable* var1,
126									double coeff2, Variable* var2,
127									double coeff3, Variable* var3,
128									double coeff4, Variable* var4,
129									OperatorType op, double rightSide,
130									double penaltyNeg = -1,
131									double penaltyPos = -1);
132
133			ResultType			FindMins(const VariableList* variables);
134			ResultType			FindMaxs(const VariableList* variables);
135
136			ResultType			Solve();
137			bool				Save(const char* fileName);
138
139			int32				CountColumns() const;
140
141			ResultType			Result() const;
142			bigtime_t			SolvingTime() const;
143
144			BString				ToString() const;
145
146			void				GetRangeConstraints(const Variable*,
147									const Constraint** _min,
148								   	const Constraint** _max) const;
149	const	ConstraintList&		Constraints() const;
150	const	VariableList&		UsedVariables() const;
151	const	VariableList&		AllVariables() const;
152
153protected:
154	friend class Constraint;
155	friend class SolverInterface;
156
157 			bool				UpdateLeftSide(Constraint* constraint,
158 									const SummandList* oldSummands);
159			bool				UpdateRightSide(Constraint* constraint);
160			bool				UpdateOperator(Constraint* constraint);
161			bool				UpdatePenalties(Constraint* constraint);
162
163			bool				AddConstraint(Constraint* constraint,
164									bool notifyListener);
165			bool				RemoveConstraint(Constraint* constraint,
166									bool deleteConstraint, bool notifyListener);
167private:
168			/*! Check if all entries != NULL otherwise delete the list and its
169			entries. */
170			bool				_CheckSummandList(SummandList* list);
171			Constraint*			_AddConstraint(SummandList* leftSide,
172									OperatorType op, double rightSide,
173									double penaltyNeg, double penaltyPos);
174
175			void				_AddConstraintRef(Variable* var);
176			void				_RemoveConstraintRef(Variable* var);
177
178			VariableList		fVariables;
179			VariableList		fUsedVariables;
180			ConstraintList		fConstraints;
181			ResultType			fResult;
182			bigtime_t 			fSolvingTime;
183
184			SolverInterface*	fSolver;
185
186			BObjectList<SpecificationListener>	fListeners;
187};
188
189}	// namespace LinearProgramming
190
191using LinearProgramming::LinearSpec;
192
193#endif	// LINEAR_SPEC_H
194