1 /* Test the MIP_Problem class with instances that require a watchdog timer.
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_test.hh"
25 #include <limits>
26
27 namespace {
28
29 class Timeout : virtual public std::exception,
30 public Parma_Polyhedra_Library::Throwable {
31 public:
what() const32 const char* what() const throw() {
33 return "Timeout in refine1.cc";
34 }
35
throw_me() const36 void throw_me() const {
37 throw *this;
38 }
39
priority() const40 int priority() const {
41 return 0;
42 }
43
Timeout()44 Timeout() {
45 }
46
~Timeout()47 ~Timeout() throw() {
48 }
49 };
50
51 Timeout t;
52
test01()53 bool test01() {
54 Variable A(0);
55 Variable B(1);
56 Variable C(2);
57 Variable D(3);
58
59 Linear_Expression cost(10*A + 3*B);
60 Constraint_System cs;
61 cs.insert(A + B >= 0);
62 cs.insert(B >= 0);
63 cs.insert(B == 3);
64 cs.insert(2*C + 2*D == 9);
65
66 MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MINIMIZATION);
67 Coefficient num_kr = -21;
68 Coefficient den_kr = 1;
69 Coefficient num;
70 Coefficient den;
71 Generator pg = mip.optimizing_point();
72 mip.evaluate_objective_function(pg, num, den);
73 nout << "Optimum value = " << num << "/" << den << endl;
74 if (num != num_kr || den != den_kr)
75 return false;
76 nout << "Optimizing point = ";
77 print_generator(pg);
78 Generator pg_kr = point(-6*A + 6*B + 9*D, 2);
79 if (pg != pg_kr)
80 return false;
81
82 // Set Variable A to be constrained to have an integer value.
83 mip.add_to_integer_space_dimensions(Variables_Set(A));
84 pg = mip.optimizing_point();
85 mip.evaluate_objective_function(pg, num, den);
86
87 nout << "Optimum value = " << num << "/" << den << endl;
88 if (num != num_kr || den != den_kr)
89 return false;
90 nout << "Optimizing point = ";
91 print_generator(pg);
92 if (pg != pg_kr)
93 return false;
94
95 // Set Variable B to be constrained to have an integer value.
96 mip.add_to_integer_space_dimensions(Variables_Set(B));
97 pg = mip.optimizing_point();
98 mip.evaluate_objective_function(pg, num, den);
99
100 nout << "Optimum value = " << num << "/" << den << endl;
101 if (num != num_kr || den != den_kr)
102 return false;
103 nout << "Optimizing point = ";
104 print_generator(pg);
105 if (pg != pg_kr)
106 return false;
107
108 // Set Variable C to be constrained to have an integer value.
109 mip.add_to_integer_space_dimensions(Variables_Set(C));
110 pg = mip.optimizing_point();
111 mip.evaluate_objective_function(pg, num, den);
112
113 nout << "Optimum value = " << num << "/" << den << endl;
114 if (num != num_kr || den != den_kr)
115 return false;
116 nout << "Optimizing point = ";
117 print_generator(pg);
118 if (pg != pg_kr)
119 return false;
120
121 // Set Variable D to be constrained to have an integer value.
122 // This will cause branch-and-bound not to terminate any longer.
123 mip.add_to_integer_space_dimensions(Variables_Set(D));
124
125 try {
126 // Set a 2 seconds timeout.
127 Parma_Polyhedra_Library::Watchdog
128 w(200, abandon_expensive_computations, t);
129
130 pg = mip.optimizing_point();
131
132 // We should never get here.
133 abandon_expensive_computations = 0;
134 nout << "unexpected termination" << endl;
135 return false;
136 }
137 catch (const Timeout&) {
138 abandon_expensive_computations = 0;
139 nout << "timeout, as expected" << endl;
140 return true;
141 }
142 #if !PPL_WATCHDOG_OBJECTS_ARE_SUPPORTED
143 // If Watchdog objects are not supported, an std::logic_error exception
144 // will be thrown: this is normal.
145 catch (const std::logic_error& e) {
146 nout << "std::logic_error exception caught: \n" << e.what() << std::endl;
147 exit(0);
148 }
149 #endif // !PPL_WATCHDOG_OBJECTS_ARE_SUPPORTED
150 catch (const std::overflow_error& e) {
151 abandon_expensive_computations = 0;
152 if (std::numeric_limits<Coefficient>::is_integer
153 && std::numeric_limits<Coefficient>::is_bounded
154 && std::numeric_limits<Coefficient>::radix == 2
155 && std::numeric_limits<Coefficient>::digits == 7) {
156 // Overflow is OK with 8-bit coefficients.
157 nout << "arithmetic overflow (" << e.what() << "),"
158 " possible with 8-bit coefficients" << endl;
159 return true;
160 }
161 else
162 // Overflow errors should be propagated in all other cases.
163 throw;
164 }
165 catch (...) {
166 abandon_expensive_computations = 0;
167 nout << "unexpected exception" << endl;
168 return false;
169 }
170 }
171
172 } // namespace
173
174 BEGIN_MAIN
175 DO_TEST(test01);
176 END_MAIN
177