1 /* MIP_Problem class implementation: inline functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_MIP_Problem_inlines_hh
25 #define PPL_MIP_Problem_inlines_hh 1
26
27 #include "Constraint_defs.hh"
28 #include <stdexcept>
29
30 namespace Parma_Polyhedra_Library {
31
32 inline dimension_type
max_space_dimension()33 MIP_Problem::max_space_dimension() {
34 return Constraint::max_space_dimension();
35 }
36
37 inline dimension_type
space_dimension() const38 MIP_Problem::space_dimension() const {
39 return external_space_dim;
40 }
41
42
43 inline
MIP_Problem(const MIP_Problem & y)44 MIP_Problem::MIP_Problem(const MIP_Problem& y)
45 : external_space_dim(y.external_space_dim),
46 internal_space_dim(y.internal_space_dim),
47 tableau(y.tableau),
48 working_cost(y.working_cost),
49 mapping(y.mapping),
50 base(y.base),
51 status(y.status),
52 pricing(y.pricing),
53 initialized(y.initialized),
54 input_cs(),
55 inherited_constraints(0),
56 first_pending_constraint(),
57 input_obj_function(y.input_obj_function),
58 opt_mode(y.opt_mode),
59 last_generator(y.last_generator),
60 i_variables(y.i_variables) {
61 input_cs.reserve(y.input_cs.size());
62 for (Constraint_Sequence::const_iterator i = y.input_cs.begin(),
63 i_end = y.input_cs.end(); i != i_end; ++i) {
64 add_constraint_helper(*(*i));
65 }
66 PPL_ASSERT(OK());
67 }
68
69 inline
MIP_Problem(const MIP_Problem & y,Inherit_Constraints)70 MIP_Problem::MIP_Problem(const MIP_Problem& y, Inherit_Constraints)
71 : external_space_dim(y.external_space_dim),
72 internal_space_dim(y.internal_space_dim),
73 tableau(y.tableau),
74 working_cost(y.working_cost),
75 mapping(y.mapping),
76 base(y.base),
77 status(y.status),
78 pricing(y.pricing),
79 initialized(y.initialized),
80 input_cs(y.input_cs),
81 // NOTE: The constraints are inherited, NOT copied!
82 inherited_constraints(y.input_cs.size()),
83 first_pending_constraint(y.first_pending_constraint),
84 input_obj_function(y.input_obj_function),
85 opt_mode(y.opt_mode),
86 last_generator(y.last_generator),
87 i_variables(y.i_variables) {
88 PPL_ASSERT(OK());
89 }
90
91 inline void
add_constraint_helper(const Constraint & c)92 MIP_Problem::add_constraint_helper(const Constraint& c) {
93 // For exception safety, reserve space for the new element.
94 const dimension_type size = input_cs.size();
95 if (size == input_cs.capacity()) {
96 const dimension_type max_size = input_cs.max_size();
97 if (size == max_size) {
98 throw std::length_error("MIP_Problem::add_constraint(): "
99 "too many constraints");
100 }
101 // Use an exponential grow policy to avoid too many reallocations.
102 input_cs.reserve(compute_capacity(size + 1, max_size));
103 }
104
105 // This operation does not throw, because the space for the new element
106 // has already been reserved: hence the new-ed Constraint is safe.
107 input_cs.push_back(new Constraint(c));
108 }
109
110 inline
~MIP_Problem()111 MIP_Problem::~MIP_Problem() {
112 // NOTE: do NOT delete inherited constraints; they are owned
113 // (and will eventually be deleted) by ancestors.
114 for (Constraint_Sequence::const_iterator
115 i = nth_iter(input_cs, inherited_constraints),
116 i_end = input_cs.end(); i != i_end; ++i) {
117 delete *i;
118 }
119 }
120
121
122 inline void
set_optimization_mode(const Optimization_Mode mode)123 MIP_Problem::set_optimization_mode(const Optimization_Mode mode) {
124 if (opt_mode != mode) {
125 opt_mode = mode;
126 if (status == UNBOUNDED || status == OPTIMIZED) {
127 status = SATISFIABLE;
128 }
129 PPL_ASSERT(OK());
130 }
131 }
132
133 inline const Linear_Expression&
objective_function() const134 MIP_Problem::objective_function() const {
135 return input_obj_function;
136 }
137
138 inline Optimization_Mode
optimization_mode() const139 MIP_Problem::optimization_mode() const {
140 return opt_mode;
141 }
142
143 inline void
optimal_value(Coefficient & numer,Coefficient & denom) const144 MIP_Problem::optimal_value(Coefficient& numer, Coefficient& denom) const {
145 const Generator& g = optimizing_point();
146 evaluate_objective_function(g, numer, denom);
147 }
148
149 inline MIP_Problem::const_iterator
constraints_begin() const150 MIP_Problem::constraints_begin() const {
151 return const_iterator(input_cs.begin());
152 }
153
154 inline MIP_Problem::const_iterator
constraints_end() const155 MIP_Problem::constraints_end() const {
156 return const_iterator(input_cs.end());
157 }
158
159 inline const Variables_Set&
integer_space_dimensions() const160 MIP_Problem::integer_space_dimensions() const {
161 return i_variables;
162 }
163
164 inline MIP_Problem::Control_Parameter_Value
get_control_parameter(Control_Parameter_Name name) const165 MIP_Problem::get_control_parameter(Control_Parameter_Name name) const {
166 PPL_USED(name);
167 PPL_ASSERT(name == PRICING);
168 return pricing;
169 }
170
171 inline void
set_control_parameter(Control_Parameter_Value value)172 MIP_Problem::set_control_parameter(Control_Parameter_Value value) {
173 pricing = value;
174 }
175
176 inline void
m_swap(MIP_Problem & y)177 MIP_Problem::m_swap(MIP_Problem& y) {
178 using std::swap;
179 swap(external_space_dim, y.external_space_dim);
180 swap(internal_space_dim, y.internal_space_dim);
181 swap(tableau, y.tableau);
182 swap(working_cost, y.working_cost);
183 swap(mapping, y.mapping);
184 swap(initialized, y.initialized);
185 swap(base, y.base);
186 swap(status, y.status);
187 swap(pricing, y.pricing);
188 swap(input_cs, y.input_cs);
189 swap(inherited_constraints, y.inherited_constraints);
190 swap(first_pending_constraint, y.first_pending_constraint);
191 swap(input_obj_function, y.input_obj_function);
192 swap(opt_mode, y.opt_mode);
193 swap(last_generator, y.last_generator);
194 swap(i_variables, y.i_variables);
195 }
196
197 inline MIP_Problem&
operator =(const MIP_Problem & y)198 MIP_Problem::operator=(const MIP_Problem& y) {
199 MIP_Problem tmp(y);
200 m_swap(tmp);
201 return *this;
202 }
203
204 inline void
clear()205 MIP_Problem::clear() {
206 MIP_Problem tmp;
207 m_swap(tmp);
208 }
209
210
211 inline memory_size_type
external_memory_in_bytes() const212 MIP_Problem::external_memory_in_bytes() const {
213 memory_size_type n
214 = working_cost.external_memory_in_bytes()
215 + tableau.external_memory_in_bytes()
216 + input_obj_function.external_memory_in_bytes()
217 + last_generator.external_memory_in_bytes();
218
219 // Adding the external memory for `input_cs'.
220 // NOTE: disregard inherited constraints, as they are owned by ancestors.
221 n += input_cs.capacity() * sizeof(Constraint*);
222 for (Constraint_Sequence::const_iterator
223 i = nth_iter(input_cs, inherited_constraints),
224 i_end = input_cs.end(); i != i_end; ++i) {
225 n += ((*i)->total_memory_in_bytes());
226 }
227
228 // Adding the external memory for `base'.
229 n += base.capacity() * sizeof(dimension_type);
230 // Adding the external memory for `mapping'.
231 n += mapping.capacity() * sizeof(std::pair<dimension_type, dimension_type>);
232 return n;
233 }
234
235 inline memory_size_type
total_memory_in_bytes() const236 MIP_Problem::total_memory_in_bytes() const {
237 return sizeof(*this) + external_memory_in_bytes();
238 }
239
240 inline
const_iterator(Base b)241 MIP_Problem::const_iterator::const_iterator(Base b)
242 : itr(b) {
243 }
244
245 inline MIP_Problem::const_iterator::difference_type
operator -(const const_iterator & y) const246 MIP_Problem::const_iterator::operator-(const const_iterator& y) const {
247 return itr - y.itr;
248 }
249
250 inline MIP_Problem::const_iterator&
operator ++()251 MIP_Problem::const_iterator::operator++() {
252 ++itr;
253 return *this;
254 }
255
256 inline MIP_Problem::const_iterator&
operator --()257 MIP_Problem::const_iterator::operator--() {
258 --itr;
259 return *this;
260 }
261
262 inline MIP_Problem::const_iterator
operator ++(int)263 MIP_Problem::const_iterator::operator++(int) {
264 const_iterator x = *this;
265 operator++();
266 return x;
267 }
268
269 inline MIP_Problem::const_iterator
operator --(int)270 MIP_Problem::const_iterator::operator--(int) {
271 const_iterator x = *this;
272 operator--();
273 return x;
274 }
275
276 inline MIP_Problem::const_iterator
operator +(difference_type n) const277 MIP_Problem::const_iterator::operator+(difference_type n) const {
278 return const_iterator(itr + n);
279 }
280
281 inline MIP_Problem::const_iterator
operator -(difference_type n) const282 MIP_Problem::const_iterator::operator-(difference_type n) const {
283 return const_iterator(itr - n);
284 }
285
286 inline MIP_Problem::const_iterator&
operator +=(difference_type n)287 MIP_Problem::const_iterator::operator+=(difference_type n) {
288 itr += n;
289 return *this;
290 }
291
292 inline MIP_Problem::const_iterator&
operator -=(difference_type n)293 MIP_Problem::const_iterator::operator-=(difference_type n) {
294 itr -= n;
295 return *this;
296 }
297
298 inline MIP_Problem::const_iterator::reference
operator *() const299 MIP_Problem::const_iterator::operator*() const {
300 return *(*itr);
301 }
302
303 inline MIP_Problem::const_iterator::pointer
operator ->() const304 MIP_Problem::const_iterator::operator->() const {
305 return *itr;
306 }
307
308 inline bool
operator ==(const const_iterator & y) const309 MIP_Problem::const_iterator::operator==(const const_iterator& y) const {
310 return itr == y.itr;
311 }
312
313 inline bool
operator !=(const const_iterator & y) const314 MIP_Problem::const_iterator::operator!=(const const_iterator& y) const {
315 return itr != y.itr;
316 }
317
318 /*! \relates MIP_Problem */
319 inline void
swap(MIP_Problem & x,MIP_Problem & y)320 swap(MIP_Problem& x, MIP_Problem& y) {
321 x.m_swap(y);
322 }
323
324 } // namespace Parma_Polyhedra_Library
325
326 #endif // !defined(PPL_MIP_Problem_inlines_hh)
327