1 /* PIP_Problem class implementation: non-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 #include "ppl-config.h"
25 #include "PIP_Problem_defs.hh"
26 #include "PIP_Tree_defs.hh"
27
28 namespace PPL = Parma_Polyhedra_Library;
29
30 /*! \relates Parma_Polyhedra_Library::PIP_Problem */
31 std::ostream&
operator <<(std::ostream & s,const PIP_Problem & pip)32 PPL::IO_Operators::operator<<(std::ostream& s, const PIP_Problem& pip) {
33 s << "Space dimension: " << pip.space_dimension();
34 s << "\nConstraints:";
35 for (PIP_Problem::const_iterator i = pip.constraints_begin(),
36 i_end = pip.constraints_end(); i != i_end; ++i) {
37 s << "\n" << *i;
38 }
39 s << "\nProblem parameters: " << pip.parameter_space_dimensions();
40 if (pip.get_big_parameter_dimension() == not_a_dimension()) {
41 s << "\nNo big-parameter set.\n";
42 }
43 else {
44 s << "\nBig-parameter: " << Variable(pip.get_big_parameter_dimension());
45 }
46 s << "\n";
47 return s;
48 }
49
PIP_Problem(const dimension_type dim)50 PPL::PIP_Problem::PIP_Problem(const dimension_type dim)
51 : external_space_dim(dim),
52 internal_space_dim(0),
53 status(PARTIALLY_SATISFIABLE),
54 current_solution(0),
55 input_cs(),
56 first_pending_constraint(0),
57 parameters(),
58 initial_context(),
59 big_parameter_dimension(not_a_dimension()) {
60 // Check for space dimension overflow.
61 if (dim > max_space_dimension()) {
62 throw std::length_error("PPL::PIP_Problem::PIP_Problem(dim):\n"
63 "dim exceeds the maximum allowed "
64 "space dimension.");
65 }
66 control_parameters_init();
67 PPL_ASSERT(OK());
68 }
69
PIP_Problem(const PIP_Problem & y)70 PPL::PIP_Problem::PIP_Problem(const PIP_Problem& y)
71 : external_space_dim(y.external_space_dim),
72 internal_space_dim(y.internal_space_dim),
73 status(y.status),
74 current_solution(0),
75 input_cs(y.input_cs),
76 first_pending_constraint(y.first_pending_constraint),
77 parameters(y.parameters),
78 initial_context(y.initial_context),
79 big_parameter_dimension(y.big_parameter_dimension) {
80 if (y.current_solution != 0) {
81 current_solution = y.current_solution->clone();
82 current_solution->set_owner(this);
83 }
84 control_parameters_copy(y);
85 PPL_ASSERT(OK());
86 }
87
~PIP_Problem()88 PPL::PIP_Problem::~PIP_Problem() {
89 delete current_solution;
90 }
91
92 void
control_parameters_init()93 PPL::PIP_Problem::control_parameters_init() {
94 control_parameters[CUTTING_STRATEGY] = CUTTING_STRATEGY_FIRST;
95 control_parameters[PIVOT_ROW_STRATEGY] = PIVOT_ROW_STRATEGY_FIRST;
96 }
97
98 void
control_parameters_copy(const PIP_Problem & y)99 PPL::PIP_Problem::control_parameters_copy(const PIP_Problem& y) {
100 for (dimension_type i = CONTROL_PARAMETER_NAME_SIZE; i-- > 0; ) {
101 control_parameters[i] = y.control_parameters[i];
102 }
103 }
104
105 PPL::PIP_Problem_Status
solve() const106 PPL::PIP_Problem::solve() const {
107 switch (status) {
108
109 case UNSATISFIABLE:
110 PPL_ASSERT(OK());
111 return UNFEASIBLE_PIP_PROBLEM;
112
113 case OPTIMIZED:
114 PPL_ASSERT(OK());
115 return OPTIMIZED_PIP_PROBLEM;
116
117 case PARTIALLY_SATISFIABLE:
118 {
119 PIP_Problem& x = const_cast<PIP_Problem&>(*this);
120 // Allocate PIP solution tree root, if needed.
121 if (current_solution == 0) {
122 x.current_solution = new PIP_Solution_Node(this);
123 }
124
125 // Properly resize context matrix.
126 const dimension_type new_num_cols = parameters.size() + 1;
127 const dimension_type old_num_cols = initial_context.num_columns();
128 if (old_num_cols < new_num_cols) {
129 x.initial_context.add_zero_columns(new_num_cols - old_num_cols);
130 }
131
132 // Computed once for all (to be used inside loop).
133 const Variables_Set::const_iterator param_begin = parameters.begin();
134 const Variables_Set::const_iterator param_end = parameters.end();
135
136 // This flag will be set if we insert a pending constraint
137 // in the initial context.
138 bool check_feasible_context = false;
139
140 // Go through all pending constraints.
141 for (Constraint_Sequence::const_iterator
142 cs_i = nth_iter(input_cs, first_pending_constraint),
143 cs_end = input_cs.end(); cs_i != cs_end; ++cs_i) {
144 const Constraint& c = *cs_i;
145 const dimension_type c_space_dim = c.space_dimension();
146 PPL_ASSERT(external_space_dim >= c_space_dim);
147
148 // Constraints having a non-zero variable coefficient
149 // should not be inserted in context.
150 if (!c.expression().all_zeroes_except(parameters, 1, c_space_dim + 1)) {
151 continue;
152 }
153
154 check_feasible_context = true;
155
156 x.initial_context.add_zero_rows(1);
157
158 Row& row = x.initial_context[x.initial_context.num_rows()-1];
159
160 {
161 Row::iterator itr = row.end();
162
163 if (c.inhomogeneous_term() != 0) {
164 itr = row.insert(0, c.inhomogeneous_term());
165 // Adjust inhomogeneous term if strict.
166 if (c.is_strict_inequality()) {
167 --(*itr);
168 }
169 }
170 else {
171 // Adjust inhomogeneous term if strict.
172 if (c.is_strict_inequality()) {
173 itr = row.insert(0, -1);
174 }
175 }
176 dimension_type i = 1;
177
178 // TODO: This loop may be optimized more, if needed.
179 // If the size of param_end is expected to be greater than the
180 // number of nonzeroes of c in most cases, then this implementation
181 // can't be optimized further.
182 // itr may still be end(), but it can still be used as hint.
183 for (Variables_Set::const_iterator
184 pi = param_begin; pi != param_end; ++pi, ++i) {
185 if (*pi < c_space_dim) {
186 Coefficient_traits::const_reference coeff_pi
187 = c.coefficient(Variable(*pi));
188 if (coeff_pi != 0) {
189 itr = row.insert(itr, i, coeff_pi);
190 }
191 }
192 else {
193 break;
194 }
195 }
196 }
197
198 // If it is an equality, also insert its negation.
199 if (c.is_equality()) {
200 x.initial_context.add_zero_rows(1);
201
202 // The reference `row' has been invalidated.
203
204 Row& last_row = x.initial_context[x.initial_context.num_rows()-1];
205
206 last_row = x.initial_context[x.initial_context.num_rows()-2];
207
208 for (Row::iterator i = last_row.begin(),
209 i_end = last_row.end(); i != i_end; ++i) {
210 neg_assign(*i);
211 }
212 }
213 }
214
215 if (check_feasible_context) {
216 // Check for feasibility of initial context.
217 Matrix<Row> ctx_copy(initial_context);
218 if (!PIP_Solution_Node::compatibility_check(ctx_copy)) {
219 // Problem found to be unfeasible.
220 delete x.current_solution;
221 x.current_solution = 0;
222 x.status = UNSATISFIABLE;
223 PPL_ASSERT(OK());
224 return UNFEASIBLE_PIP_PROBLEM;
225 }
226 }
227
228 // Update tableau and mark constraints as no longer pending.
229 x.current_solution->update_tableau(*this,
230 external_space_dim,
231 first_pending_constraint,
232 input_cs,
233 parameters);
234 x.internal_space_dim = external_space_dim;
235 x.first_pending_constraint = input_cs.size();
236
237 // Actually solve problem.
238 x.current_solution = x.current_solution->solve(*this,
239 check_feasible_context,
240 initial_context,
241 parameters,
242 external_space_dim,
243 /*indent_level=*/ 0);
244 // Update problem status.
245 x.status = (x.current_solution != 0) ? OPTIMIZED : UNSATISFIABLE;
246
247 PPL_ASSERT(OK());
248 return (x.current_solution != 0)
249 ? OPTIMIZED_PIP_PROBLEM
250 : UNFEASIBLE_PIP_PROBLEM;
251 } // End of handler for PARTIALLY_SATISFIABLE case.
252
253 } // End of switch.
254
255 // We should not be here!
256 PPL_UNREACHABLE;
257 return UNFEASIBLE_PIP_PROBLEM;
258 }
259
260 PPL::PIP_Tree
solution() const261 PPL::PIP_Problem::solution() const {
262 if (status == PARTIALLY_SATISFIABLE) {
263 solve();
264 }
265 return current_solution;
266 }
267
268 PPL::PIP_Tree
optimizing_solution() const269 PPL::PIP_Problem::optimizing_solution() const {
270 if (status == PARTIALLY_SATISFIABLE) {
271 solve();
272 }
273 return current_solution;
274 }
275
276 bool
OK() const277 PPL::PIP_Problem::OK() const {
278 #ifndef NDEBUG
279 using std::endl;
280 using std::cerr;
281 #endif
282
283 if (external_space_dim < internal_space_dim) {
284 #ifndef NDEBUG
285 cerr << "The internal space dimension of the PIP_Problem is "
286 << "greater than its external space dimension."
287 << endl;
288 ascii_dump(cerr);
289 #endif
290 return false;
291 }
292
293 // Constraint system should be space dimension compatible.
294 const dimension_type input_cs_num_rows = input_cs.size();
295 for (dimension_type i = input_cs_num_rows; i-- > 0; ) {
296 if (input_cs[i].space_dimension() > external_space_dim) {
297 #ifndef NDEBUG
298 cerr << "The space dimension of the PIP_Problem is smaller than "
299 << "the space dimension of one of its constraints."
300 << endl;
301 ascii_dump(cerr);
302 #endif
303 return false;
304 }
305 }
306
307 // Test validity of control parameter values.
308 Control_Parameter_Value strategy = control_parameters[CUTTING_STRATEGY];
309 if (strategy != CUTTING_STRATEGY_FIRST
310 && strategy != CUTTING_STRATEGY_DEEPEST
311 && strategy != CUTTING_STRATEGY_ALL) {
312 #ifndef NDEBUG
313 cerr << "Invalid value for the CUTTING_STRATEGY control parameter."
314 << endl;
315 ascii_dump(cerr);
316 #endif
317 return false;
318 }
319
320 strategy = control_parameters[PIVOT_ROW_STRATEGY];
321 if (strategy < PIVOT_ROW_STRATEGY_FIRST
322 || strategy > PIVOT_ROW_STRATEGY_MAX_COLUMN) {
323 #ifndef NDEBUG
324 cerr << "Invalid value for the PIVOT_ROW_STRATEGY control parameter."
325 << endl;
326 ascii_dump(cerr);
327 #endif
328 return false;
329 }
330
331 if (big_parameter_dimension != not_a_dimension()
332 && parameters.count(big_parameter_dimension) == 0) {
333 #ifndef NDEBUG
334 cerr << "The big parameter is set, but it is not a parameter." << endl;
335 ascii_dump(cerr);
336 #endif
337 return false;
338 }
339
340 if (!parameters.OK()) {
341 return false;
342 }
343 if (!initial_context.OK()) {
344 return false;
345 }
346
347 if (current_solution != 0) {
348 // Check well formedness of the solution tree.
349 if (!current_solution->OK()) {
350 #ifndef NDEBUG
351 cerr << "The computed solution tree is broken.\n";
352 ascii_dump(cerr);
353 #endif
354 return false;
355 }
356 // Check that all nodes in the solution tree belong to *this.
357 if (!current_solution->check_ownership(this)) {
358 #ifndef NDEBUG
359 cerr << "There are nodes in the solution tree "
360 << "that are not owned by *this.\n";
361 ascii_dump(cerr);
362 #endif
363 return false;
364 }
365 }
366
367 // All checks passed.
368 return true;
369 }
370
371 void
ascii_dump(std::ostream & s) const372 PPL::PIP_Problem::ascii_dump(std::ostream& s) const {
373 using namespace IO_Operators;
374 s << "\nexternal_space_dim: " << external_space_dim << "\n";
375 s << "\ninternal_space_dim: " << internal_space_dim << "\n";
376
377 const dimension_type input_cs_size = input_cs.size();
378
379 s << "\ninput_cs( " << input_cs_size << " )\n";
380 for (dimension_type i = 0; i < input_cs_size; ++i) {
381 input_cs[i].ascii_dump(s);
382 }
383
384 s << "\nfirst_pending_constraint: " << first_pending_constraint << "\n";
385
386 s << "\nstatus: ";
387 switch (status) {
388 case UNSATISFIABLE:
389 s << "UNSATISFIABLE";
390 break;
391 case OPTIMIZED:
392 s << "OPTIMIZED";
393 break;
394 case PARTIALLY_SATISFIABLE:
395 s << "PARTIALLY_SATISFIABLE";
396 break;
397 }
398 s << "\n";
399
400 s << "\nparameters";
401 parameters.ascii_dump(s);
402
403 s << "\ninitial_context\n";
404 initial_context.ascii_dump(s);
405
406 s << "\ncontrol_parameters\n";
407 for (dimension_type i = 0; i < CONTROL_PARAMETER_NAME_SIZE; ++i) {
408 const Control_Parameter_Value value = control_parameters[i];
409 switch (value) {
410 case CUTTING_STRATEGY_FIRST:
411 s << "CUTTING_STRATEGY_FIRST";
412 break;
413 case CUTTING_STRATEGY_DEEPEST:
414 s << "CUTTING_STRATEGY_DEEPEST";
415 break;
416 case CUTTING_STRATEGY_ALL:
417 s << "CUTTING_STRATEGY_ALL";
418 break;
419 case PIVOT_ROW_STRATEGY_FIRST:
420 s << "PIVOT_ROW_STRATEGY_FIRST";
421 break;
422 case PIVOT_ROW_STRATEGY_MAX_COLUMN:
423 s << "PIVOT_ROW_STRATEGY_MAX_COLUMN";
424 break;
425 default:
426 s << "Invalid control parameter value";
427 }
428 s << "\n";
429 }
430
431 s << "\nbig_parameter_dimension: " << big_parameter_dimension << "\n";
432
433 s << "\ncurrent_solution: ";
434 if (current_solution == 0) {
435 s << "BOTTOM\n";
436 }
437 else if (const PIP_Decision_Node* const dec
438 = current_solution->as_decision()) {
439 s << "DECISION\n";
440 dec->ascii_dump(s);
441 }
442 else {
443 const PIP_Solution_Node* const sol = current_solution->as_solution();
444 PPL_ASSERT(sol != 0);
445 s << "SOLUTION\n";
446 sol->ascii_dump(s);
447 }
448 }
449
PPL_OUTPUT_DEFINITIONS(PIP_Problem)450 PPL_OUTPUT_DEFINITIONS(PIP_Problem)
451
452 bool
453 PPL::PIP_Problem::ascii_load(std::istream& s) {
454 std::string str;
455 if (!(s >> str) || str != "external_space_dim:") {
456 return false;
457 }
458
459 if (!(s >> external_space_dim)) {
460 return false;
461 }
462
463 if (!(s >> str) || str != "internal_space_dim:") {
464 return false;
465 }
466
467 if (!(s >> internal_space_dim)) {
468 return false;
469 }
470
471 if (!(s >> str) || str != "input_cs(") {
472 return false;
473 }
474
475 dimension_type input_cs_size;
476
477 if (!(s >> input_cs_size)) {
478 return false;
479 }
480
481 if (!(s >> str) || str != ")") {
482 return false;
483 }
484
485 Constraint c(Constraint::zero_dim_positivity());
486 for (dimension_type i = 0; i < input_cs_size; ++i) {
487 if (!c.ascii_load(s)) {
488 return false;
489 }
490 input_cs.push_back(c);
491 }
492
493 if (!(s >> str) || str != "first_pending_constraint:") {
494 return false;
495 }
496
497 if (!(s >> first_pending_constraint)) {
498 return false;
499 }
500
501 if (!(s >> str) || str != "status:") {
502 return false;
503 }
504
505 if (!(s >> str)) {
506 return false;
507 }
508
509 if (str == "UNSATISFIABLE") {
510 status = UNSATISFIABLE;
511 }
512 else if (str == "OPTIMIZED") {
513 status = OPTIMIZED;
514 }
515 else if (str == "PARTIALLY_SATISFIABLE") {
516 status = PARTIALLY_SATISFIABLE;
517 }
518 else {
519 return false;
520 }
521
522 if (!(s >> str) || str != "parameters") {
523 return false;
524 }
525
526 if (!parameters.ascii_load(s)) {
527 return false;
528 }
529
530 if (!(s >> str) || str != "initial_context") {
531 return false;
532 }
533
534 if (!initial_context.ascii_load(s)) {
535 return false;
536 }
537
538 if (!(s >> str) || str != "control_parameters") {
539 return false;
540 }
541
542 for (dimension_type i = 0; i < CONTROL_PARAMETER_NAME_SIZE; ++i) {
543 if (!(s >> str)) {
544 return false;
545 }
546 Control_Parameter_Value value;
547 if (str == "CUTTING_STRATEGY_FIRST") {
548 value = CUTTING_STRATEGY_FIRST;
549 }
550 else if (str == "CUTTING_STRATEGY_DEEPEST") {
551 value = CUTTING_STRATEGY_DEEPEST;
552 }
553 else if (str == "CUTTING_STRATEGY_ALL") {
554 value = CUTTING_STRATEGY_ALL;
555 }
556 else if (str == "PIVOT_ROW_STRATEGY_FIRST") {
557 value = PIVOT_ROW_STRATEGY_FIRST;
558 }
559 else if (str == "PIVOT_ROW_STRATEGY_MAX_COLUMN") {
560 value = PIVOT_ROW_STRATEGY_MAX_COLUMN;
561 }
562 else {
563 return false;
564 }
565 control_parameters[i] = value;
566 }
567
568 if (!(s >> str) || str != "big_parameter_dimension:") {
569 return false;
570 }
571 if (!(s >> big_parameter_dimension)) {
572 return false;
573 }
574
575 // Release current_solution tree (if any).
576 delete current_solution;
577 current_solution = 0;
578 // Load current_solution (if any).
579 if (!(s >> str) || str != "current_solution:") {
580 return false;
581 }
582 if (!(s >> str)) {
583 return false;
584 }
585 if (str == "BOTTOM") {
586 current_solution = 0;
587 }
588 else if (str == "DECISION") {
589 PIP_Decision_Node* const dec = new PIP_Decision_Node(0, 0, 0);
590 current_solution = dec;
591 if (!dec->ascii_load(s)) {
592 return false;
593 }
594 dec->set_owner(this);
595 }
596 else if (str == "SOLUTION") {
597 PIP_Solution_Node* const sol = new PIP_Solution_Node(0);
598 current_solution = sol;
599 if (!sol->ascii_load(s)) {
600 return false;
601 }
602 sol->set_owner(this);
603 }
604 else {
605 // Unknown node kind.
606 return false;
607 }
608
609 PPL_ASSERT(OK());
610 return true;
611 }
612
613 void
clear()614 PPL::PIP_Problem::clear() {
615 external_space_dim = 0;
616 internal_space_dim = 0;
617 status = PARTIALLY_SATISFIABLE;
618 if (current_solution != 0) {
619 delete current_solution;
620 current_solution = 0;
621 }
622 input_cs.clear();
623 first_pending_constraint = 0;
624 parameters.clear();
625 initial_context.clear();
626 control_parameters_init();
627 big_parameter_dimension = not_a_dimension();
628 }
629
630 void
631 PPL::PIP_Problem
add_space_dimensions_and_embed(const dimension_type m_vars,const dimension_type m_params)632 ::add_space_dimensions_and_embed(const dimension_type m_vars,
633 const dimension_type m_params) {
634 // Adding no space dims at all is a no-op:
635 // this avoids invalidating problem status (if it was optimized).
636 if (m_vars == 0 && m_params == 0) {
637 return;
638 }
639
640 // The space dimension of the resulting PIP problem should not
641 // overflow the maximum allowed space dimension.
642 dimension_type available = max_space_dimension() - space_dimension();
643 bool should_throw = (m_vars > available);
644 if (!should_throw) {
645 available -= m_vars;
646 should_throw = (m_params > available);
647 }
648 if (should_throw) {
649 throw std::length_error("PPL::PIP_Problem::"
650 "add_space_dimensions_and_embed(m_v, m_p):\n"
651 "adding m_v+m_p new space dimensions exceeds "
652 "the maximum allowed space dimension.");
653 }
654 // First add PIP variables ...
655 external_space_dim += m_vars;
656 // ... then add PIP parameters.
657 for (dimension_type i = m_params; i-- > 0; ) {
658 parameters.insert(Variable(external_space_dim));
659 ++external_space_dim;
660 }
661 // Update problem status.
662 if (status != UNSATISFIABLE) {
663 status = PARTIALLY_SATISFIABLE;
664 }
665 PPL_ASSERT(OK());
666 }
667
668 void
669 PPL::PIP_Problem
add_to_parameter_space_dimensions(const Variables_Set & p_vars)670 ::add_to_parameter_space_dimensions(const Variables_Set& p_vars) {
671 if (p_vars.space_dimension() > external_space_dim) {
672 throw std::invalid_argument("PPL::PIP_Problem::"
673 "add_to_parameter_space_dimension(p_vars):\n"
674 "*this and p_vars are dimension "
675 "incompatible.");
676 }
677 const dimension_type original_size = parameters.size();
678 parameters.insert(p_vars.begin(), p_vars.end());
679 // Do not allow to turn variables into parameters.
680 for (Variables_Set::const_iterator p = p_vars.begin(),
681 end = p_vars.end(); p != end; ++p) {
682 if (*p < internal_space_dim) {
683 throw std::invalid_argument("PPL::PIP_Problem::"
684 "add_to_parameter_space_dimension(p_vars):"
685 "p_vars contain variable indices.");
686 }
687 }
688
689 // If a new parameter was inserted, set the internal status to
690 // PARTIALLY_SATISFIABLE.
691 if (parameters.size() != original_size && status != UNSATISFIABLE) {
692 status = PARTIALLY_SATISFIABLE;
693 }
694 }
695
696 void
add_constraint(const Constraint & c)697 PPL::PIP_Problem::add_constraint(const Constraint& c) {
698 if (c.space_dimension() > external_space_dim) {
699 std::ostringstream s;
700 s << "PPL::PIP_Problem::add_constraint(c):\n"
701 << "dim == "<< external_space_dim << " and c.space_dimension() == "
702 << c.space_dimension() << " are dimension incompatible.";
703 throw std::invalid_argument(s.str());
704 }
705 input_cs.push_back(c);
706 // Update problem status.
707 if (status != UNSATISFIABLE) {
708 status = PARTIALLY_SATISFIABLE;
709 }
710 }
711
712 void
add_constraints(const Constraint_System & cs)713 PPL::PIP_Problem::add_constraints(const Constraint_System& cs) {
714 for (Constraint_System::const_iterator ci = cs.begin(),
715 ci_end = cs.end(); ci != ci_end; ++ci) {
716 add_constraint(*ci);
717 }
718 }
719
720 bool
is_satisfiable() const721 PPL::PIP_Problem::is_satisfiable() const {
722 if (status == PARTIALLY_SATISFIABLE) {
723 solve();
724 }
725 return status == OPTIMIZED;
726 }
727
728 void
set_control_parameter(Control_Parameter_Value value)729 PPL::PIP_Problem::set_control_parameter(Control_Parameter_Value value) {
730 switch (value) {
731 case CUTTING_STRATEGY_FIRST:
732 // Intentionally fall through.
733 case CUTTING_STRATEGY_DEEPEST:
734 // Intentionally fall through.
735 case CUTTING_STRATEGY_ALL:
736 control_parameters[CUTTING_STRATEGY] = value;
737 break;
738 case PIVOT_ROW_STRATEGY_FIRST:
739 // Intentionally fall through.
740 case PIVOT_ROW_STRATEGY_MAX_COLUMN:
741 control_parameters[PIVOT_ROW_STRATEGY] = value;
742 break;
743 default:
744 throw std::invalid_argument("PPL::PIP_Problem::set_control_parameter(v)"
745 ":\ninvalid value.");
746 }
747 }
748
749 void
set_big_parameter_dimension(dimension_type big_dim)750 PPL::PIP_Problem::set_big_parameter_dimension(dimension_type big_dim) {
751 if (parameters.count(big_dim) == 0) {
752 throw std::invalid_argument("PPL::PIP_Problem::"
753 "set_big_parameter_dimension(big_dim):\n"
754 "dimension 'big_dim' is not a parameter.");
755 }
756 if (big_dim < internal_space_dim) {
757 throw std::invalid_argument("PPL::PIP_Problem::"
758 "set_big_parameter_dimension(big_dim):\n"
759 "only newly-added parameters can be"
760 "converted into the big parameter.");
761 }
762 big_parameter_dimension = big_dim;
763 }
764
765 PPL::memory_size_type
external_memory_in_bytes() const766 PPL::PIP_Problem::external_memory_in_bytes() const {
767 memory_size_type n = initial_context.external_memory_in_bytes();
768 // Adding the external memory for `current_solution'.
769 if (current_solution != 0) {
770 n += current_solution->total_memory_in_bytes();
771 }
772 // Adding the external memory for `input_cs'.
773 n += input_cs.capacity() * sizeof(Constraint);
774 for (const_iterator i = input_cs.begin(),
775 i_end = input_cs.end(); i != i_end; ++i) {
776 n += (i->external_memory_in_bytes());
777 }
778 // FIXME: Adding the external memory for `parameters'.
779 n += parameters.size() * sizeof(dimension_type);
780
781 return n;
782 }
783
784 PPL::memory_size_type
total_memory_in_bytes() const785 PPL::PIP_Problem::total_memory_in_bytes() const {
786 return sizeof(*this) + external_memory_in_bytes();
787 }
788
789 void
print_solution(std::ostream & s,int indent) const790 PPL::PIP_Problem::print_solution(std::ostream& s, int indent) const {
791 switch (status) {
792
793 case UNSATISFIABLE:
794 PPL_ASSERT(current_solution == 0);
795 PIP_Tree_Node::indent_and_print(s, indent, "_|_\n");
796 break;
797
798 case OPTIMIZED:
799 PPL_ASSERT(current_solution != 0);
800 current_solution->print(s, indent);
801 break;
802
803 case PARTIALLY_SATISFIABLE:
804 throw std::logic_error("PIP_Problem::print_solution():\n"
805 "the PIP problem has not been solved.");
806 }
807 }
808