1 /* Test the MIP_Problem class.
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 
26 namespace {
27 
28 bool
test01()29 test01() {
30   Variable X01(0);
31   Variable X02(1);
32   Variable X03(2);
33   Variable X04(3);
34   Variable X05(4);
35   Variable X06(5);
36   Variable X07(6);
37   Variable X08(7);
38   Variable X09(8);
39   Variable X10(9);
40   Variable X11(10);
41   Variable X12(11);
42   Variable X13(12);
43   Variable X14(13);
44   Variable X15(14);
45   Variable X16(15);
46   Variable X17(16);
47   Variable X18(17);
48   Variable X19(18);
49   Variable X20(19);
50   Variable X21(20);
51   Variable X22(21);
52   Variable X23(22);
53   Variable X24(23);
54   Variable X25(24);
55   Variable X26(25);
56   Variable X27(26);
57   Variable X28(27);
58   Variable X29(28);
59   Variable X30(29);
60   Variable X31(30);
61   Variable X32(31);
62   Variable X33(32);
63   Variable X34(33);
64   Variable X35(34);
65   Variable X36(35);
66   Variable X37(36);
67   Variable X38(37);
68   Variable X39(38);
69 
70   Constraint_System cs;
71   cs.insert(X01 - X02 - X03 + 0*X39 == 0);
72   cs.insert(Coefficient("2386907802506363")*X01 - X04 == 0);
73   cs.insert(-X01 >= -80);
74   cs.insert(X02 - Coefficient("3152519739159347")*X14 >= 0);
75   cs.insert(X06 + X07 + X08 + X09 - X14 - X15 == 0);
76   cs.insert(Coefficient("2386907802506363")*X06
77             + Coefficient("2386907802506363")*X07
78             + Coefficient("1080863910568919")*X08
79             + Coefficient("7746191359077253")*X09
80             - X16 == 0);
81   cs.insert(-X06 + X10 >= -80);
82   cs.insert(-X07 + X11 >= 0);
83   cs.insert(-X08 + X12 >= 0);
84   cs.insert(-X09 + X13 >= 0);
85   cs.insert(X22 - X23 - X24 - X25 == 0);
86   cs.insert(Coefficient("7746191359077253")*X22 - X26 == 0);
87   cs.insert(-X22 >= -500);
88   cs.insert(X23 - Coefficient("3152519739159347")*X36 >= 0);
89   cs.insert(Coefficient("7746191359077253")*X28
90             + Coefficient("7746191359077253")*X29
91             + Coefficient("3512807709348987")*X30
92             + Coefficient("3332663724254167")*X31
93             - X38 == 0);
94   cs.insert(X28 + X29 + X30 + X31 - X36 + X37 + X39 == 44);
95   cs.insert(-X28 + X32 >= -500);
96   cs.insert(-X29 + X33 >= 0);
97   cs.insert(-X30 + X34 >= 0);
98   cs.insert(-X31 + X35 >= 0);
99   cs.insert(Coefficient("-2661627379775963")*X10
100             - Coefficient("2686397177726501")*X11
101             - Coefficient("5422333951354077")*X12
102             - Coefficient("5469621747441467")*X13
103             + X25
104             - Coefficient("2466846695892189")*X32
105             - Coefficient("4996743786567565")*X33
106             - Coefficient("5064297780978123")*X34
107             - Coefficient("641481471923585")*X35 >= 0);
108   cs.insert(X03 - Coefficient("7854277750134145")*X22 >= 0);
109   cs.insert(X15
110             - Coefficient("7854277750134145")*X28
111             - Coefficient("7782220156096217")*X29
112             - Coefficient("7782220156096217")*X30
113             - Coefficient("7710162562058289")*X31 >= 0);
114   cs.insert(Coefficient("-5422333951354077")*X01 + X24 >= 0);
115   cs.insert(X21 >= 2);
116   cs.insert(-X16 - X38 >= -300);
117   for (dimension_type i = X01.id(); i <= X39.id(); ++i)
118     cs.insert(Variable(i) >= 0);
119 
120   // Cost function.
121   Linear_Expression cost(-10*X02 - 8*X14 - 15*X23 - 12*X36 + 250*X39);
122 
123   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
124 
125   if (mip.solve() != OPTIMIZED_MIP_PROBLEM)
126     return false;
127 
128   // Computed numerator and denominator.
129   Coefficient num;
130   Coefficient den;
131   mip.optimal_value(num, den);
132   nout << "Optimum value = " << num << "/" << den << endl;
133   Coefficient num_kr = 11000;
134   Coefficient den_kr = 1;
135   if (num != num_kr || den != den_kr)
136     return false;
137 
138   // The feasible / optimizing point.
139   Generator pg = mip.optimizing_point();
140   nout << "Optimizing point = ";
141   print_generator(pg);
142 
143   // Making mip unfeasible.
144   Constraint_System further_cs;
145   further_cs.insert(X05 >= 5);
146   further_cs.insert(X05 <= 3);
147   mip.add_constraints(further_cs);
148 
149   return !mip.is_satisfiable();
150 }
151 
152 bool
test02()153 test02() {
154   Variable A(0);
155   Variable B(1);
156   Variable C(2);
157   Variable D(3);
158   Variable E(4);
159   Variable F(5);
160   Variable G(6);
161   Variable H(7);
162 
163   // Cost function
164   Linear_Expression cost(-26*A + 343*B + 1233*D - C + F);
165 
166   // Feasible region.
167   Constraint_System cs;
168   cs.insert(A - B + C >= 24);
169   cs.insert(B <= 320);
170   cs.insert(A + B + 2*D == 23);
171   cs.insert(A + 2*B + E == 4112);
172   cs.insert(7*A + 5*B + F <= 200);
173   cs.insert(138*A + 2*G == 25);
174   cs.insert(23*A + 342*B - 34*H == 99);
175   for (dimension_type i = A.id(); i <= H.id(); ++i)
176     cs.insert(Variable(i) >= 0);
177 
178   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
179 
180   Generator pg = mip.optimizing_point();
181   nout << "Optimizing point = ";
182   print_generator(pg);
183   Generator pg_kr = point();
184   pg_kr = point(22*B + 1846*C + 863*D + 312468*E + 15090*F + 950*G + 0*H, 76);
185   if (pg != pg_kr)
186     return false;
187 
188   Coefficient num;
189   Coefficient den;
190   mip.evaluate_objective_function(pg, num, den);
191   nout << "Optimum value = " << num << "/" << den << endl;
192   Coefficient num_kr = 1084869;
193   Coefficient den_kr = 76;
194   if (num != num_kr || den != den_kr)
195     return false;
196 
197   // Reoptimize using another objective function.
198   Linear_Expression new_cost = -51*A + 632*B;
199   mip.set_objective_function(new_cost);
200   pg = mip.optimizing_point();
201   nout << "Optimizing point = ";
202   print_generator(pg);
203   pg_kr = point(782*B + 1598*C + 138244*E + 2890*F + 425*G + 7767*H, 34);
204   if (pg != pg_kr)
205     return false;
206 
207   mip.evaluate_objective_function(pg, num, den);
208   nout << "Optimum value = " << num << "/" << den << endl;
209   num_kr = 14536;
210   den_kr = 1;
211   if (num != num_kr || den != den_kr)
212     return false;
213 
214   // Reoptimize after changing optimization mode.
215   mip.set_optimization_mode(MINIMIZATION);
216   pg = mip.optimizing_point();
217   nout << "Optimizing point = ";
218   print_generator(pg);
219   pg_kr = point(17100*A + 26174*B + 2274482*C
220                 + 1063871*D + 388070456*E + 18627830*F + 0*H,
221                 94392);
222   if (pg != pg_kr)
223     return false;
224 
225   mip.evaluate_objective_function(pg, num, den);
226   nout << "Optimum value = " << num << "/" << den << endl;
227   num_kr = 3917467;
228   den_kr = 23598;
229 
230   return num == num_kr && den == den_kr;
231 }
232 
233 bool
test03()234 test03() {
235   Variable A(0);
236   Variable B(1);
237   Variable C(2);
238   Variable D(3);
239 
240   Constraint_System cs;
241   cs.insert(Coefficient("2251799813685248")*A
242             >= Coefficient("-5895288448651847"));
243   cs.insert(Coefficient("5895288437392848")*A
244             + Coefficient("3643488632714799")*B
245             - Coefficient("2251799813685248")*C
246             >= Coefficient("-19077554137963492"));
247   cs.insert(Coefficient("5895288437392848")*A +
248             Coefficient("3643488632714799")*B
249             + Coefficient("2251799813685248")*C >=
250             Coefficient("-19077554137963492"));
251   cs.insert(Coefficient("11790576874785696")*A
252             + Coefficient("4503599627370496")*B
253             + Coefficient("7286977274436797")*D
254             >= Coefficient("-38155108284934184"));
255   cs.insert(Coefficient("11790576874785696")*A
256             + Coefficient("4503599627370496")*B
257             - Coefficient("7286977274436797")*D
258             >= Coefficient("-38155108284934184"));
259   cs.insert(Coefficient("11790576879289294")*A
260             + Coefficient("7286977274436797")*C
261             + Coefficient("4503599627370496")*D
262             >= Coefficient("-38155108289437784"));
263   cs.insert(Coefficient("11790576879289294")*A
264             + Coefficient("7286977274436797")*C
265             - Coefficient("4503599627370496")*D
266             >= Coefficient("-38155108289437784"));
267   cs.insert(Coefficient("11790576879289294")*A
268             - Coefficient("7286977274436797")*C
269             + Coefficient("4503599627370496")*D
270             >= Coefficient("-38155108289437784"));
271   cs.insert(Coefficient("11790576879289294")*A
272             - Coefficient("7286977274436797")*C
273             - Coefficient("4503599627370496")*D
274             >= Coefficient("-38155108289437784"));
275   cs.insert(Coefficient("2947644225451823")*A
276             - Coefficient("1125899906842624")*B
277             + Coefficient("1821744319735099")*D
278             >= Coefficient("-9538777088122044"));
279   cs.insert(Coefficient("11790576892800094")*A
280             - Coefficient("4503599627370496")*B
281             - Coefficient("7286977274436797")*D
282             >= Coefficient("-38155108325466584"));
283   cs.insert(Coefficient("5895288437392848")*A
284             - Coefficient("3643488630462999")*B
285             + Coefficient("2251799813685248")*C
286             >= Coefficient("-19077554133459892"));
287   cs.insert(Coefficient("2947644218696424")*A
288             - Coefficient("1821744320860999")*B
289             - Coefficient("1125899906842624")*C
290             >= Coefficient("-9538777072359446"));
291   cs.insert(Coefficient("7286977269933197")*A
292             + Coefficient("11790576924325290")*B
293             + Coefficient("4503599627370496")*D
294             >= Coefficient("-38155108379509776"));
295   cs.insert(Coefficient("7286977269933197")*A
296             + Coefficient("11790576924325290")*B
297             - Coefficient("4503599627370496")*D
298             >= Coefficient("-38155108379509776"));
299   cs.insert(Coefficient("562949953421312")*A
300             + Coefficient("562949953421312")*B
301             + Coefficient("562949953421312")*C
302             + Coefficient("562949953421312")*D
303             >= Coefficient("-2947644226577723"));
304   cs.insert(Coefficient("562949953421312")*A
305             + Coefficient("562949953421312")*B
306             + Coefficient("562949953421312")*C
307             - Coefficient("562949953421312")*D
308             >= Coefficient("-2947644226577723"));
309   cs.insert(Coefficient("562949953421312")*A
310             + Coefficient("562949953421312")*B
311             - Coefficient("562949953421312")*C
312             + Coefficient("562949953421312")*D
313             >= Coefficient("-2947644225451823"));
314   cs.insert(Coefficient("562949953421312")*A
315             + Coefficient("562949953421312")*B
316             - Coefficient("562949953421312")*C
317             - Coefficient("562949953421312")*D
318             >= Coefficient("-2947644225451823"));
319   cs.insert(Coefficient("7286977269933197")*A
320             + Coefficient("4503599627370496")*B
321             + Coefficient("11790576865778496")*C
322             >= Coefficient("-38155108266919784"));
323   cs.insert(Coefficient("7286977251918799")*A
324             + Coefficient("4503599627370496")*B
325             - Coefficient("11790576870282096")*C
326             >= Coefficient("-38155108244401792"));
327   cs.insert(Coefficient("1821744320860999")*A
328             + Coefficient("1125899906842624")*C
329             + Coefficient("2947644226577723")*D
330             >= Coefficient("-9538777093751544"));
331   cs.insert(Coefficient("1821744320860999")*A
332             + Coefficient("1125899906842624")*C
333             - Coefficient("2947644226577723")*
334             D >= Coefficient("-9538777093751544"));
335   cs.insert(Coefficient("1821744320860999")*A
336             - Coefficient("1125899906842624")*C
337             + Coefficient("2947644228829523")*D
338             >= Coefficient("-9538777096003344"));
339   cs.insert(Coefficient("1821744320860999")*A
340             - Coefficient("1125899906842624")*C
341             - Coefficient("2947644228829523")*D
342             >= Coefficient("-9538777096003344"));
343   cs.insert(Coefficient("3643488664239996")*A
344             - Coefficient("2251799813685248")*B
345             + Coefficient("5895288468918045")*C
346             >= Coefficient("-19077554257308884"));
347   cs.insert(Coefficient("3643488652980997")*A
348             - Coefficient("2251799813685248")*B
349             - Coefficient("5895288468918045")*C
350             >= Coefficient("-19077554232539084"));
351   cs.insert(Coefficient("562949953421312")*A
352             - Coefficient("562949953421312")*B
353             + Coefficient("562949953421312")*C
354             + Coefficient("562949953421312")*D
355             >= Coefficient("-2947644226577723"));
356   cs.insert(Coefficient("562949953421312")*A
357             - Coefficient("562949953421312")*B
358             + Coefficient("562949953421312")*C
359             - Coefficient("562949953421312")*D
360             >= Coefficient("-2947644229392473"));
361   cs.insert(Coefficient("562949953421312")*A
362             - Coefficient("562949953421312")*B
363             - Coefficient("562949953421312")*C
364             + Coefficient("562949953421312")*D
365             >= Coefficient("-2947644227140673"));
366   cs.insert(Coefficient("562949953421312")*A
367             - Coefficient("562949953421312")*B
368             - Coefficient("562949953421312")*C
369             - Coefficient("562949953421312")*D
370             >= Coefficient("-2947644227703623"));
371   cs.insert(Coefficient("7286977314969193")*A
372             - Coefficient("11790576906310892")*B
373             + Coefficient("4503599627370496")*D
374             >= Coefficient("-38155108447063768"));
375   cs.insert(Coefficient("3643488655232797")*A
376             - Coefficient("5895288446400047")*B
377             - Coefficient("2251799813685248")*D
378             >= Coefficient("-19077554203265688"));
379   cs.insert(Coefficient("4503599627370496")*A
380             + Coefficient("11790576753188506")*B
381             + Coefficient("7286977179861205")*C
382             >= Coefficient("-38155107920142616"));
383   cs.insert(Coefficient("4503599627370496")*A
384             + Coefficient("11790576766699304")*B
385             - Coefficient("7286977179861205")*C
386             >= Coefficient("-38155107965178608"));
387   cs.insert(Coefficient("4503599627370496")*A
388             + Coefficient("7286977157343207")*B
389             + Coefficient("11790576712656108")*D
390             >= Coefficient("-38155107816559824"));
391   cs.insert(Coefficient("2251799813685248")*A
392             + Coefficient("3643488592182402")*B
393             - Coefficient("5895288374342453")*D
394             >= Coefficient("-19077553960071308"));
395   cs.insert(Coefficient("4503599627370496")*A
396             + Coefficient("11790576753188506")*C
397             + Coefficient("7286977175357605")*D
398             >= Coefficient("-38155107924646216"));
399   cs.insert(Coefficient("2251799813685248")*A
400             + Coefficient("5895288390105051")*C
401             - Coefficient("3643488594434202")*D
402             >= Coefficient("-19077553996100104"));
403   cs.insert(Coefficient("2251799813685248")*A
404             - Coefficient("5895288421630249")*C
405             + Coefficient("3643488619204000")*D
406             >= Coefficient("-19077554088423896"));
407   cs.insert(Coefficient("4503599627370496")*A
408             - Coefficient("11790576865778496")*C
409             - Coefficient("7286977247415199")*D
410             >= Coefficient("-38155108244401792"));
411   cs.insert(Coefficient("4503599627370496")*A
412             - Coefficient("7286977247415199")*B
413             + Coefficient("11790576888296494")*D
414             >= Coefficient("-38155108307452184"));
415   cs.insert(Coefficient("2251799813685248")*A
416             - Coefficient("3643488639470198")*B
417             - Coefficient("5895288464414445")*D
418             >= Coefficient("-19077554210021088"));
419   cs.insert(Coefficient("2251799813685248")*A
420             - Coefficient("5895288428385648")*B
421             + Coefficient("3643488630462999")*C
422             >= Coefficient("-19077554131208092"));
423   cs.insert(Coefficient("4503599627370496")*A
424             - Coefficient("11790576843260498")*B
425             - Coefficient("7286977224897201")*C
426             >= Coefficient("-38155108163336992"));
427   cs.insert(Coefficient("1125899906842624")*B
428             >= Coefficient("-2947644227703623"));
429   cs.insert(Coefficient("5895288459910846")*B
430             + Coefficient("2251799813685248")*C
431             + Coefficient("3643488630462999")*D
432             >= Coefficient("-19077554198762088"));
433   cs.insert(Coefficient("5895288457659046")*B
434             + Coefficient("2251799813685248")*C
435             - Coefficient("3643488628211199")*D
436             >= Coefficient("-19077554189754888"));
437   cs.insert(Coefficient("11790576915318092")*B
438             - Coefficient("4503599627370496")*C
439             + Coefficient("7286977269933197")*D
440             >= Coefficient("-38155108393020576"));
441   cs.insert(Coefficient("5895288457659046")*B
442             - Coefficient("2251799813685248")*C
443             - Coefficient("3643488632714799")*D
444             >= Coefficient("-19077554187503088"));
445   cs.insert(Coefficient("7286977292451195")*B
446             + Coefficient("11790576919821692")*C
447             + Coefficient("4503599627370496")*D
448             >= Coefficient("-38155108433552976"));
449   cs.insert(Coefficient("3643488664239996")*B
450             + Coefficient("5895288486932443")*C
451             - Coefficient("2251799813685248")*D
452             >= Coefficient("-19077554304596680"));
453   cs.insert(Coefficient("3643488643973798")*B
454             - Coefficient("5895288446400047")*C
455             + Coefficient("2251799813685248")*D
456             >= Coefficient("-19077554180747688"));
457   cs.insert(Coefficient("7286977314969193")*B
458             - Coefficient("11790576937836090")*C
459             - Coefficient("4503599627370496")*D
460             >= Coefficient("-38155108510114168"));
461   cs.insert(Coefficient("4503599627370496")*B
462             + Coefficient("7286977247415199")*C
463             + Coefficient("11790576883792894")*D
464             >= Coefficient("-38155108289437784"));
465   cs.insert(Coefficient("4503599627370496")*B
466             + Coefficient("7286977251918799")*C
467             - Coefficient("11790576883792894")*D
468             >= Coefficient("-38155108280430584"));
469   cs.insert(Coefficient("4503599627370496")*B
470             - Coefficient("7286977229400801")*C
471             + Coefficient("11790576852267696")*D
472             >= Coefficient("-38155108181351392"));
473   cs.insert(Coefficient("1125899906842624")*D
474             >= Coefficient("-2947644225451823"));
475   cs.insert(Coefficient("4503599627370496")*B
476             - Coefficient("7286977229400801")*C
477             - Coefficient("11790576852267696")*D
478             >= Coefficient("-38155108167840592"));
479   cs.insert(Coefficient("-2251799813685248")*D
480             >= Coefficient("-5895288448651847"));
481   cs.insert(Coefficient("2251799813685248")*C
482             >= Coefficient("-5895288446400047"));
483   cs.insert(Coefficient("-2251799813685248")*C
484             >= Coefficient("-5895288444148247"));
485   cs.insert(Coefficient("-1125899906842624")*B
486             + Coefficient("1821744321986899")*C
487             + Coefficient("2947644226577723")*D
488             >= Coefficient("-9538777088122044"));
489   cs.insert(Coefficient("-3643488607945001")*B
490             + Coefficient("5895288414874849")*C
491             + Coefficient("2251799813685248")*D
492             >= Coefficient("-19077554059150500"));
493   cs.insert(Coefficient("-4503599627370496")*B
494             + Coefficient("7286977292451195")*C
495             - Coefficient("11790576906310892")*D
496             >= Coefficient("-38155108343480984"));
497   cs.insert(Coefficient("-7286977220393601")*B
498             + Coefficient("11790576829749698")*C
499             - Coefficient("4503599627370496")*D
500             >= Coefficient("-38155108086775800"));
501   cs.insert(Coefficient("-4503599627370496")*B
502             - Coefficient("7286977274436797")*C
503             + Coefficient("11790576901807292")*D
504             >= Coefficient("-38155108325466584"));
505   cs.insert(Coefficient("-3643488605693201")*B
506             - Coefficient("5895288414874849")*C
507             + Coefficient("2251799813685248")*D
508             >= Coefficient("-19077554059150500"));
509   cs.insert(Coefficient("-1125899906842624")*B
510             - Coefficient("1821744319735099")*C
511             - Coefficient("2947644225451823")*D
512             >= Coefficient("-9538777079114846"));
513   cs.insert(Coefficient("-7286977220393601")*B
514             - Coefficient("11790576834253298")*C
515             - Coefficient("4503599627370496")*D
516             >= Coefficient("-38155108113797400"));
517   cs.insert(Coefficient("-5895288462162645")*B
518             + Coefficient("2251799813685248")*C
519             + Coefficient("3643488639470198")*D
520             >= Coefficient("-19077554144718892"));
521   cs.insert(Coefficient("-11790576924325290")*B
522             - Coefficient("4503599627370496")*C
523             + Coefficient("7286977292451195")*D
524             >= Coefficient("-38155108320962984"));
525   cs.insert(Coefficient("-5895288468918045")*B
526             + Coefficient("2251799813685248")*C
527             - Coefficient("3643488641721998")*D
528             >= Coefficient("-19077554160481492"));
529   cs.insert(Coefficient("-11790576928828890")*B
530             - Coefficient("4503599627370496")*C
531             - Coefficient("7286977292451195")*D
532             >= Coefficient("-38155108329970184"));
533   cs.insert(Coefficient("-281474976710656")*B
534             >= Coefficient("-736911053829681"));
535   cs.insert(Coefficient("-4503599627370496")*A
536             + Coefficient("11790576658612912")*B
537             + Coefficient("7286977125818009")*C
538             >= Coefficient("-38155107627408640"));
539   cs.insert(Coefficient("-2251799813685248")*A
540             + Coefficient("5895288336061856")*B
541             - Coefficient("3643488560657205")*C
542             >= Coefficient("-19077553829466920"));
543   cs.insert(Coefficient("-2251799813685248")*A
544             + Coefficient("3643488535887407")*B
545             + Coefficient("5895288288774060")*D
546             >= Coefficient("-19077553683099932"));
547   cs.insert(Coefficient("-7286977274436797")*A
548             + Coefficient("11790576766699304")*B
549             + Coefficient("4503599627370496")*D
550             >= Coefficient("-38155108032732608"));
551   cs.insert(Coefficient("-4503599627370496")*A
552             + Coefficient("7286977098796411")*B
553             - Coefficient("11790576609073318")*D
554             >= Coefficient("-38155107483293448"));
555   cs.insert(Coefficient("-7286977301458395")*A
556             + Coefficient("11790576735174106")*B
557             - Coefficient("4503599627370496")*D
558             >= Coefficient("-38155107983193008"));
559   cs.insert(Coefficient("-4503599627370496")*A
560             + Coefficient("11790576708152508")*C
561             + Coefficient("7286977148336007")*D
562             >= Coefficient("-38155107771523824"));
563   cs.insert(Coefficient("-281474976710656")*A
564             + Coefficient("281474976710656")*B
565             + Coefficient("281474976710656")*C
566             + Coefficient("281474976710656")*D
567             >= Coefficient("-1473822119481311"));
568   cs.insert(Coefficient("-1125899906842624")*A
569             + Coefficient("2947644178164027")*C
570             - Coefficient("1821744285958102")*D
571             >= Coefficient("-9538776941755056"));
572   cs.insert(Coefficient("-1125899906842624")*A
573             + Coefficient("1125899906842624")*B
574             + Coefficient("1125899906842624")*C
575             - Coefficient("1125899906842624")*D
576             >= Coefficient("-5895288471169845"));
577   cs.insert(Coefficient("-4503599627370496")*A
578             - Coefficient("11790576856771296")*C
579             + Coefficient("7286977247415199")*D
580             >= Coefficient("-38155108221883792"));
581   cs.insert(Coefficient("-1125899906842624")*A
582             + Coefficient("1125899906842624")*B
583             - Coefficient("1125899906842624")*C
584             + Coefficient("1125899906842624")*D
585             >= Coefficient("-5895288471169845"));
586   cs.insert(Coefficient("-140737488355328")*A
587             - Coefficient("368455526774103")*C
588             - Coefficient("227718038700250")*D
589             >= Coefficient("-1192347131793131"));
590   cs.insert(Coefficient("-1125899906842624")*A
591             + Coefficient("1125899906842624")*B
592             - Coefficient("1125899906842624")*C
593             - Coefficient("1125899906842624")*D
594             >= Coefficient("-5895288464414445"));
595   cs.insert(Coefficient("-3643488643973798")*A
596             + Coefficient("2251799813685248")*B
597             + Coefficient("5895288441896447")*C
598             >= Coefficient("-19077554158229692"));
599   cs.insert(Coefficient("-7286977296954795")*A
600             + Coefficient("4503599627370496")*B
601             - Coefficient("11790576892800094")*C
602             >= Coefficient("-38155108352488176"));
603   cs.insert(Coefficient("-4503599627370496")*A
604             - Coefficient("7286977269933197")*B
605             + Coefficient("11790576924325290")*D
606             >= Coefficient("-38155108411034976"));
607   cs.insert(Coefficient("-3643488639470198")*A
608             + Coefficient("2251799813685248")*C
609             + Coefficient("5895288466666245")*D
610             >= Coefficient("-19077554219028288"));
611   cs.insert(Coefficient("-4503599627370496")*A
612             - Coefficient("7286977296954795")*B
613             - Coefficient("11790576955850488")*D
614             >= Coefficient("-38155108514617768"));
615   cs.insert(Coefficient("-7286977251918799")*A
616             + Coefficient("4503599627370496")*C
617             - Coefficient("11790576892800094")*D
618             >= Coefficient("-38155108311955784"));
619   cs.insert(Coefficient("-3643488655232797")*A
620             - Coefficient("2251799813685248")*C
621             + Coefficient("5895288480177044")*D
622             >= Coefficient("-19077554264064284"));
623   cs.insert(Coefficient("-1821744320860999")*A
624             - Coefficient("1125899906842624")*C
625             - Coefficient("2947644229955423")*D
626             >= Coefficient("-9538777099381044"));
627   cs.insert(Coefficient("-4503599627370496")*A
628             - Coefficient("11790576874785696")*B
629             + Coefficient("7286977269933197")*C
630             >= Coefficient("-38155108302948584"));
631   cs.insert(Coefficient("-7286977274436797")*A
632             - Coefficient("4503599627370496")*B
633             + Coefficient("11790576937836090")*C
634             >= Coefficient("-38155108424545776"));
635   cs.insert(Coefficient("-4503599627370496")*A
636             - Coefficient("11790576802728102")*B
637             - Coefficient("7286977197875603")*C
638             >= Coefficient("-38155108019221808"));
639   cs.insert(Coefficient("-3643488664239996")*A
640             - Coefficient("2251799813685248")*B
641             - Coefficient("5895288493687843")*C
642             >= Coefficient("-19077554284330480"));
643   cs.insert(Coefficient("-562949953421312")*A
644             - Coefficient("562949953421312")*B
645             + Coefficient("562949953421312")*C
646             + Coefficient("562949953421312")*D
647             >= Coefficient("-2947644250784571"));
648   cs.insert(Coefficient("-281474976710656")*A
649             - Coefficient("281474976710656")*B
650             + Coefficient("281474976710656")*C
651             - Coefficient("281474976710656")*D
652             >= Coefficient("-1473822131021785"));
653   cs.insert(Coefficient("-1125899906842624")*A
654             - Coefficient("1125899906842624")*B
655             - Coefficient("1125899906842624")*C
656             + Coefficient("1125899906842624")*D
657             >= Coefficient("-5895288464414445"));
658   cs.insert(Coefficient("-1125899906842624")*A
659             - Coefficient("1125899906842624")*B
660             - Coefficient("1125899906842624")*C
661             - Coefficient("1125899906842624")*D
662             >= Coefficient("-5895288468918045"));
663   cs.insert(Coefficient("-3643488412038417")*A
664             - Coefficient("5895288318047457")*B
665             + Coefficient("2251799813685248")*D
666             >= Coefficient("-19077553665085532"));
667   cs.insert(Coefficient("-1821744199263809")*A
668             - Coefficient("2947644153394229")*B
669             - Coefficient("1125899906842624")*D
670             >= Coefficient("-9538776813402468"));
671   cs.insert(Coefficient("-5895288378846052")*A
672             + Coefficient("3643488632714799")*B
673             + Coefficient("2251799813685248")*C
674             >= Coefficient("-19077554023121704"));
675   cs.insert(Coefficient("-11790576834253298")*A
676             + Coefficient("7286977314969193")*B
677             - Coefficient("4503599627370496")*C
678             >= Coefficient("-38155108302948584"));
679   cs.insert(Coefficient("-736911041726257")*A
680             + Coefficient("281474976710656")*B
681             + Coefficient("455436077400500")*D
682             >= Coefficient("-2384694241068264"));
683   cs.insert(Coefficient("-5895288347320855")*A
684             + Coefficient("2251799813685248")*B
685             - Coefficient("3643488616952200")*D
686             >= Coefficient("-19077553951064108"));
687   cs.insert(Coefficient("-2947644201807925")*A
688             + Coefficient("1821744319735099")*C
689             + Coefficient("1125899906842624")*D
690             >= Coefficient("-9538777048715548"));
691   cs.insert(Coefficient("-11790576820742500")*A
692             + Coefficient("7286977296954795")*C
693             - Coefficient("4503599627370496")*D
694             >= Coefficient("-38155108248905384"));
695   cs.insert(Coefficient("-11790576996382886")*A
696             - Coefficient("7286977251918799")*C
697             + Coefficient("4503599627370496")*D
698             >= Coefficient("-38155108523624968"));
699   cs.insert(Coefficient("-5895288507198642")*A
700             - Coefficient("3643488632714799")*C
701             - Coefficient("2251799813685248")*D
702             >= Coefficient("-19077554291085880"));
703   cs.insert(Coefficient("-11790577113476476")*A
704             - Coefficient("4503599627370496")*B
705             + Coefficient("7286977319472793")*D
706             >= Coefficient("-38155108861394936"));
707   cs.insert(Coefficient("-5895288572500836")*A
708             - Coefficient("2251799813685248")*B
709             - Coefficient("3643488652980997")*D
710             >= Coefficient("-19077554450963668"));
711   cs.insert(Coefficient("-5895288484680644")*A
712             - Coefficient("3643488607945001")*B
713             + Coefficient("2251799813685248")*C
714             >= Coefficient("-19077554212272888"));
715   cs.insert(Coefficient("-2947644274991419")*A
716             - Coefficient("1821744320860999")*B
717             - Coefficient("1125899906842624")*C
718             >= Coefficient("-9538777190578936"));
719   cs.insert(Coefficient("-2251799813685248")*A
720             >= Coefficient("-5895288448651847"));
721 
722   // Cost function
723   Linear_Expression cost(10*A + 21*B + 31*C + 45*D);
724 
725   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
726 
727   Generator pg = mip.optimizing_point();
728   nout << "Optimizing point obtained by simplex:\n";
729   print_generator(pg);
730 
731   Coefficient num;
732   Coefficient den;
733   mip.evaluate_objective_function(pg, num, den);
734   nout << "\nOptimum value = " << num << "/" << den << endl;
735 
736   C_Polyhedron ph(cs);
737   Coefficient num1;
738   Coefficient den1;
739   bool maximum;
740   Generator pg1 = point();
741   ph.maximize(cost, num1, den1, maximum, pg1);
742 
743   nout << "\nOptimizing point obtained by enumeration:\n";
744   print_generator(pg1);
745   nout << "\nOptimum value = " << num1 << "/" << den1 << endl;
746 
747   return maximum && num == num1 && den == den1 && pg == pg1;
748 }
749 
750 bool
test04()751 test04() {
752   Variable A(0);
753   Variable B(1);
754   Variable C(2);
755   Variable D(3);
756   Variable E(4);
757   Variable F(5);
758   Variable G(6);
759   Variable H(7);
760 
761   // Cost function
762   Linear_Expression cost(-26*A + 343*B + 1233*D - C + F);
763 
764   // Feasible region.
765   Constraint_System cs;
766   cs.insert(A - B + C >= 24);
767   cs.insert(B <= 320);
768   cs.insert(A + B + 2*D == 23);
769   cs.insert(A + 2*B + E == 4112);
770   cs.insert(7*A + 5*B + F <= 200);
771   cs.insert(138*A + 2*G == 25);
772   cs.insert(23*A + 342*B - 34*H == 99);
773   for (dimension_type i = A.id(); i <= H.id(); ++i)
774     cs.insert(Variable(i) >= 0);
775 
776   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
777 
778   Generator pg = mip.optimizing_point();
779   nout << "Optimizing point = ";
780   print_generator(pg);
781   Generator pg_kr = point();
782   pg_kr = point(22*B + 1846*C + 863*D + 312468*E + 15090*F + 950*G + 0*H, 76);
783   if (pg != pg_kr)
784     return false;
785 
786   Coefficient num;
787   Coefficient den;
788   mip.evaluate_objective_function(pg, num, den);
789   nout << "Optimum value = " << num << "/" << den << endl;
790   Coefficient num_kr = 1084869;
791   Coefficient den_kr = 76;
792   if (num != num_kr || den != den_kr)
793     return false;
794 
795   // Reoptimize using another objective function.
796   Linear_Expression new_cost = -51*A + 632*B;
797   mip.set_objective_function(new_cost);
798   pg = mip.optimizing_point();
799   nout << "Optimizing point = ";
800   print_generator(pg);
801   pg_kr = point(782*B + 1598*C + 138244*E + 2890*F + 425*G + 7767*H, 34);
802   if (pg != pg_kr)
803     return false;
804 
805   mip.evaluate_objective_function(pg, num, den);
806   nout << "Optimum value = " << num << "/" << den << endl;
807   num_kr = 14536;
808   den_kr = 1;
809   if (num != num_kr || den != den_kr)
810     return false;
811 
812   // Reoptimize after changing optimization mode.
813   mip.set_optimization_mode(MINIMIZATION);
814   pg = mip.optimizing_point();
815   nout << "Optimizing point = ";
816   print_generator(pg);
817   pg_kr = point(17100*A + 26174*B + 2274482*C
818                 + 1063871*D + 388070456*E + 18627830*F + 0*H,
819                 94392);
820   if (pg != pg_kr)
821     return false;
822 
823   mip.evaluate_objective_function(pg, num, den);
824   nout << "Optimum value = " << num << "/" << den << endl;
825   num_kr = 3917467;
826   den_kr = 23598;
827   if (num != num_kr || den != den_kr)
828     return false;
829 
830   return true;
831 }
832 
833 bool
test05()834 test05() {
835   Variable A(0);
836   Variable B(1);
837   Variable C(2);
838   Variable D(3);
839   Constraint_System cs;
840   cs.insert(Coefficient("2251799813685248")*A
841             >= Coefficient("-5895288448651847"));
842   cs.insert(Coefficient("5895288437392848")*A
843             + Coefficient("3643488632714799")*B
844             - Coefficient("2251799813685248")*C
845             >= Coefficient("-19077554137963492"));
846   cs.insert(Coefficient("5895288437392848")*A +
847             Coefficient("3643488632714799")*B
848             + Coefficient("2251799813685248")*C >=
849             Coefficient("-19077554137963492"));
850   cs.insert(Coefficient("11790576874785696")*A
851             + Coefficient("4503599627370496")*B
852             + Coefficient("7286977274436797")*D
853             >= Coefficient("-38155108284934184"));
854   cs.insert(Coefficient("11790576874785696")*A
855             + Coefficient("4503599627370496")*B
856             - Coefficient("7286977274436797")*D
857             >= Coefficient("-38155108284934184"));
858   cs.insert(Coefficient("11790576879289294")*A
859             + Coefficient("7286977274436797")*C
860             + Coefficient("4503599627370496")*D
861             >= Coefficient("-38155108289437784"));
862   cs.insert(Coefficient("11790576879289294")*A
863             + Coefficient("7286977274436797")*C
864             - Coefficient("4503599627370496")*D
865             >= Coefficient("-38155108289437784"));
866   cs.insert(Coefficient("11790576879289294")*A
867             - Coefficient("7286977274436797")*C
868             + Coefficient("4503599627370496")*D
869             >= Coefficient("-38155108289437784"));
870   cs.insert(Coefficient("11790576879289294")*A
871             - Coefficient("7286977274436797")*C
872             - Coefficient("4503599627370496")*D
873             >= Coefficient("-38155108289437784"));
874   cs.insert(Coefficient("2947644225451823")*A
875             - Coefficient("1125899906842624")*B
876             + Coefficient("1821744319735099")*D
877             >= Coefficient("-9538777088122044"));
878   cs.insert(Coefficient("11790576892800094")*A
879             - Coefficient("4503599627370496")*B
880             - Coefficient("7286977274436797")*D
881             >= Coefficient("-38155108325466584"));
882   cs.insert(Coefficient("5895288437392848")*A
883             - Coefficient("3643488630462999")*B
884             + Coefficient("2251799813685248")*C
885             >= Coefficient("-19077554133459892"));
886   cs.insert(Coefficient("2947644218696424")*A
887             - Coefficient("1821744320860999")*B
888             - Coefficient("1125899906842624")*C
889             >= Coefficient("-9538777072359446"));
890   cs.insert(Coefficient("7286977269933197")*A
891             + Coefficient("11790576924325290")*B
892             + Coefficient("4503599627370496")*D
893             >= Coefficient("-38155108379509776"));
894   cs.insert(Coefficient("7286977269933197")*A
895             + Coefficient("11790576924325290")*B
896             - Coefficient("4503599627370496")*D
897             >= Coefficient("-38155108379509776"));
898   cs.insert(Coefficient("562949953421312")*A
899             + Coefficient("562949953421312")*B
900             + Coefficient("562949953421312")*C
901             + Coefficient("562949953421312")*D
902             >= Coefficient("-2947644226577723"));
903   cs.insert(Coefficient("562949953421312")*A
904             + Coefficient("562949953421312")*B
905             + Coefficient("562949953421312")*C
906             - Coefficient("562949953421312")*D
907             >= Coefficient("-2947644226577723"));
908   cs.insert(Coefficient("562949953421312")*A
909             + Coefficient("562949953421312")*B
910             - Coefficient("562949953421312")*C
911             + Coefficient("562949953421312")*D
912             >= Coefficient("-2947644225451823"));
913   cs.insert(Coefficient("562949953421312")*A
914             + Coefficient("562949953421312")*B
915             - Coefficient("562949953421312")*C
916             - Coefficient("562949953421312")*D
917             >= Coefficient("-2947644225451823"));
918   cs.insert(Coefficient("7286977269933197")*A
919             + Coefficient("4503599627370496")*B
920             + Coefficient("11790576865778496")*C
921             >= Coefficient("-38155108266919784"));
922   cs.insert(Coefficient("7286977251918799")*A
923             + Coefficient("4503599627370496")*B
924             - Coefficient("11790576870282096")*C
925             >= Coefficient("-38155108244401792"));
926   cs.insert(Coefficient("1821744320860999")*A
927             + Coefficient("1125899906842624")*C
928             + Coefficient("2947644226577723")*D
929             >= Coefficient("-9538777093751544"));
930   cs.insert(Coefficient("1821744320860999")*A
931             + Coefficient("1125899906842624")*C
932             - Coefficient("2947644226577723")*
933             D >= Coefficient("-9538777093751544"));
934   cs.insert(Coefficient("1821744320860999")*A
935             - Coefficient("1125899906842624")*C
936             + Coefficient("2947644228829523")*D
937             >= Coefficient("-9538777096003344"));
938   cs.insert(Coefficient("1821744320860999")*A
939             - Coefficient("1125899906842624")*C
940             - Coefficient("2947644228829523")*D
941             >= Coefficient("-9538777096003344"));
942   cs.insert(Coefficient("3643488664239996")*A
943             - Coefficient("2251799813685248")*B
944             + Coefficient("5895288468918045")*C
945             >= Coefficient("-19077554257308884"));
946   cs.insert(Coefficient("3643488652980997")*A
947             - Coefficient("2251799813685248")*B
948             - Coefficient("5895288468918045")*C
949             >= Coefficient("-19077554232539084"));
950   cs.insert(Coefficient("562949953421312")*A
951             - Coefficient("562949953421312")*B
952             + Coefficient("562949953421312")*C
953             + Coefficient("562949953421312")*D
954             >= Coefficient("-2947644226577723"));
955   cs.insert(Coefficient("562949953421312")*A
956             - Coefficient("562949953421312")*B
957             + Coefficient("562949953421312")*C
958             - Coefficient("562949953421312")*D
959             >= Coefficient("-2947644229392473"));
960   cs.insert(Coefficient("562949953421312")*A
961             - Coefficient("562949953421312")*B
962             - Coefficient("562949953421312")*C
963             + Coefficient("562949953421312")*D
964             >= Coefficient("-2947644227140673"));
965   cs.insert(Coefficient("562949953421312")*A
966             - Coefficient("562949953421312")*B
967             - Coefficient("562949953421312")*C
968             - Coefficient("562949953421312")*D
969             >= Coefficient("-2947644227703623"));
970   cs.insert(Coefficient("7286977314969193")*A
971             - Coefficient("11790576906310892")*B
972             + Coefficient("4503599627370496")*D
973             >= Coefficient("-38155108447063768"));
974   cs.insert(Coefficient("3643488655232797")*A
975             - Coefficient("5895288446400047")*B
976             - Coefficient("2251799813685248")*D
977             >= Coefficient("-19077554203265688"));
978   cs.insert(Coefficient("4503599627370496")*A
979             + Coefficient("11790576753188506")*B
980             + Coefficient("7286977179861205")*C
981             >= Coefficient("-38155107920142616"));
982   cs.insert(Coefficient("4503599627370496")*A
983             + Coefficient("11790576766699304")*B
984             - Coefficient("7286977179861205")*C
985             >= Coefficient("-38155107965178608"));
986   cs.insert(Coefficient("4503599627370496")*A
987             + Coefficient("7286977157343207")*B
988             + Coefficient("11790576712656108")*D
989             >= Coefficient("-38155107816559824"));
990   cs.insert(Coefficient("2251799813685248")*A
991             + Coefficient("3643488592182402")*B
992             - Coefficient("5895288374342453")*D
993             >= Coefficient("-19077553960071308"));
994   cs.insert(Coefficient("4503599627370496")*A
995             + Coefficient("11790576753188506")*C
996             + Coefficient("7286977175357605")*D
997             >= Coefficient("-38155107924646216"));
998   cs.insert(Coefficient("2251799813685248")*A
999             + Coefficient("5895288390105051")*C
1000             - Coefficient("3643488594434202")*D
1001             >= Coefficient("-19077553996100104"));
1002   cs.insert(Coefficient("2251799813685248")*A
1003             - Coefficient("5895288421630249")*C
1004             + Coefficient("3643488619204000")*D
1005             >= Coefficient("-19077554088423896"));
1006   cs.insert(Coefficient("4503599627370496")*A
1007             - Coefficient("11790576865778496")*C
1008             - Coefficient("7286977247415199")*D
1009             >= Coefficient("-38155108244401792"));
1010   cs.insert(Coefficient("4503599627370496")*A
1011             - Coefficient("7286977247415199")*B
1012             + Coefficient("11790576888296494")*D
1013             >= Coefficient("-38155108307452184"));
1014   cs.insert(Coefficient("2251799813685248")*A
1015             - Coefficient("3643488639470198")*B
1016             - Coefficient("5895288464414445")*D
1017             >= Coefficient("-19077554210021088"));
1018   cs.insert(Coefficient("2251799813685248")*A
1019             - Coefficient("5895288428385648")*B
1020             + Coefficient("3643488630462999")*C
1021             >= Coefficient("-19077554131208092"));
1022   cs.insert(Coefficient("4503599627370496")*A
1023             - Coefficient("11790576843260498")*B
1024             - Coefficient("7286977224897201")*C
1025             >= Coefficient("-38155108163336992"));
1026   cs.insert(Coefficient("1125899906842624")*B
1027             >= Coefficient("-2947644227703623"));
1028   cs.insert(Coefficient("5895288459910846")*B
1029             + Coefficient("2251799813685248")*C
1030             + Coefficient("3643488630462999")*D
1031             >= Coefficient("-19077554198762088"));
1032   cs.insert(Coefficient("5895288457659046")*B
1033             + Coefficient("2251799813685248")*C
1034             - Coefficient("3643488628211199")*D
1035             >= Coefficient("-19077554189754888"));
1036   cs.insert(Coefficient("11790576915318092")*B
1037             - Coefficient("4503599627370496")*C
1038             + Coefficient("7286977269933197")*D
1039             >= Coefficient("-38155108393020576"));
1040   cs.insert(Coefficient("5895288457659046")*B
1041             - Coefficient("2251799813685248")*C
1042             - Coefficient("3643488632714799")*D
1043             >= Coefficient("-19077554187503088"));
1044   cs.insert(Coefficient("7286977292451195")*B
1045             + Coefficient("11790576919821692")*C
1046             + Coefficient("4503599627370496")*D
1047             >= Coefficient("-38155108433552976"));
1048   cs.insert(Coefficient("3643488664239996")*B
1049             + Coefficient("5895288486932443")*C
1050             - Coefficient("2251799813685248")*D
1051             >= Coefficient("-19077554304596680"));
1052   cs.insert(Coefficient("3643488643973798")*B
1053             - Coefficient("5895288446400047")*C
1054             + Coefficient("2251799813685248")*D
1055             >= Coefficient("-19077554180747688"));
1056   cs.insert(Coefficient("7286977314969193")*B
1057             - Coefficient("11790576937836090")*C
1058             - Coefficient("4503599627370496")*D
1059             >= Coefficient("-38155108510114168"));
1060   cs.insert(Coefficient("4503599627370496")*B
1061             + Coefficient("7286977247415199")*C
1062             + Coefficient("11790576883792894")*D
1063             >= Coefficient("-38155108289437784"));
1064   cs.insert(Coefficient("4503599627370496")*B
1065             + Coefficient("7286977251918799")*C
1066             - Coefficient("11790576883792894")*D
1067             >= Coefficient("-38155108280430584"));
1068   cs.insert(Coefficient("4503599627370496")*B
1069             - Coefficient("7286977229400801")*C
1070             + Coefficient("11790576852267696")*D
1071             >= Coefficient("-38155108181351392"));
1072   cs.insert(Coefficient("1125899906842624")*D
1073             >= Coefficient("-2947644225451823"));
1074   cs.insert(Coefficient("4503599627370496")*B
1075             - Coefficient("7286977229400801")*C
1076             - Coefficient("11790576852267696")*D
1077             >= Coefficient("-38155108167840592"));
1078   cs.insert(Coefficient("-2251799813685248")*D
1079             >= Coefficient("-5895288448651847"));
1080   cs.insert(Coefficient("2251799813685248")*C
1081             >= Coefficient("-5895288446400047"));
1082   cs.insert(Coefficient("-2251799813685248")*C
1083             >= Coefficient("-5895288444148247"));
1084   cs.insert(Coefficient("-1125899906842624")*B
1085             + Coefficient("1821744321986899")*C
1086             + Coefficient("2947644226577723")*D
1087             >= Coefficient("-9538777088122044"));
1088   cs.insert(Coefficient("-3643488607945001")*B
1089             + Coefficient("5895288414874849")*C
1090             + Coefficient("2251799813685248")*D
1091             >= Coefficient("-19077554059150500"));
1092   cs.insert(Coefficient("-4503599627370496")*B
1093             + Coefficient("7286977292451195")*C
1094             - Coefficient("11790576906310892")*D
1095             >= Coefficient("-38155108343480984"));
1096   cs.insert(Coefficient("-7286977220393601")*B
1097             + Coefficient("11790576829749698")*C
1098             - Coefficient("4503599627370496")*D
1099             >= Coefficient("-38155108086775800"));
1100   cs.insert(Coefficient("-4503599627370496")*B
1101             - Coefficient("7286977274436797")*C
1102             + Coefficient("11790576901807292")*D
1103             >= Coefficient("-38155108325466584"));
1104   cs.insert(Coefficient("-3643488605693201")*B
1105             - Coefficient("5895288414874849")*C
1106             + Coefficient("2251799813685248")*D
1107             >= Coefficient("-19077554059150500"));
1108   cs.insert(Coefficient("-1125899906842624")*B
1109             - Coefficient("1821744319735099")*C
1110             - Coefficient("2947644225451823")*D
1111             >= Coefficient("-9538777079114846"));
1112   cs.insert(Coefficient("-7286977220393601")*B
1113             - Coefficient("11790576834253298")*C
1114             - Coefficient("4503599627370496")*D
1115             >= Coefficient("-38155108113797400"));
1116   cs.insert(Coefficient("-5895288462162645")*B
1117             + Coefficient("2251799813685248")*C
1118             + Coefficient("3643488639470198")*D
1119             >= Coefficient("-19077554144718892"));
1120   cs.insert(Coefficient("-11790576924325290")*B
1121             - Coefficient("4503599627370496")*C
1122             + Coefficient("7286977292451195")*D
1123             >= Coefficient("-38155108320962984"));
1124   cs.insert(Coefficient("-5895288468918045")*B
1125             + Coefficient("2251799813685248")*C
1126             - Coefficient("3643488641721998")*D
1127             >= Coefficient("-19077554160481492"));
1128   cs.insert(Coefficient("-11790576928828890")*B
1129             - Coefficient("4503599627370496")*C
1130             - Coefficient("7286977292451195")*D
1131             >= Coefficient("-38155108329970184"));
1132   cs.insert(Coefficient("-281474976710656")*B
1133             >= Coefficient("-736911053829681"));
1134   cs.insert(Coefficient("-4503599627370496")*A
1135             + Coefficient("11790576658612912")*B
1136             + Coefficient("7286977125818009")*C
1137             >= Coefficient("-38155107627408640"));
1138   cs.insert(Coefficient("-2251799813685248")*A
1139             + Coefficient("5895288336061856")*B
1140             - Coefficient("3643488560657205")*C
1141             >= Coefficient("-19077553829466920"));
1142   cs.insert(Coefficient("-2251799813685248")*A
1143             + Coefficient("3643488535887407")*B
1144             + Coefficient("5895288288774060")*D
1145             >= Coefficient("-19077553683099932"));
1146   cs.insert(Coefficient("-7286977274436797")*A
1147             + Coefficient("11790576766699304")*B
1148             + Coefficient("4503599627370496")*D
1149             >= Coefficient("-38155108032732608"));
1150   cs.insert(Coefficient("-4503599627370496")*A
1151             + Coefficient("7286977098796411")*B
1152             - Coefficient("11790576609073318")*D
1153             >= Coefficient("-38155107483293448"));
1154   cs.insert(Coefficient("-7286977301458395")*A
1155             + Coefficient("11790576735174106")*B
1156             - Coefficient("4503599627370496")*D
1157             >= Coefficient("-38155107983193008"));
1158   cs.insert(Coefficient("-4503599627370496")*A
1159             + Coefficient("11790576708152508")*C
1160             + Coefficient("7286977148336007")*D
1161             >= Coefficient("-38155107771523824"));
1162   cs.insert(Coefficient("-281474976710656")*A
1163             + Coefficient("281474976710656")*B
1164             + Coefficient("281474976710656")*C
1165             + Coefficient("281474976710656")*D
1166             >= Coefficient("-1473822119481311"));
1167   cs.insert(Coefficient("-1125899906842624")*A
1168             + Coefficient("2947644178164027")*C
1169             - Coefficient("1821744285958102")*D
1170             >= Coefficient("-9538776941755056"));
1171   cs.insert(Coefficient("-1125899906842624")*A
1172             + Coefficient("1125899906842624")*B
1173             + Coefficient("1125899906842624")*C
1174             - Coefficient("1125899906842624")*D
1175             >= Coefficient("-5895288471169845"));
1176   cs.insert(Coefficient("-4503599627370496")*A
1177             - Coefficient("11790576856771296")*C
1178             + Coefficient("7286977247415199")*D
1179             >= Coefficient("-38155108221883792"));
1180   cs.insert(Coefficient("-1125899906842624")*A
1181             + Coefficient("1125899906842624")*B
1182             - Coefficient("1125899906842624")*C
1183             + Coefficient("1125899906842624")*D
1184             >= Coefficient("-5895288471169845"));
1185   cs.insert(Coefficient("-140737488355328")*A
1186             - Coefficient("368455526774103")*C
1187             - Coefficient("227718038700250")*D
1188             >= Coefficient("-1192347131793131"));
1189   cs.insert(Coefficient("-1125899906842624")*A
1190             + Coefficient("1125899906842624")*B
1191             - Coefficient("1125899906842624")*C
1192             - Coefficient("1125899906842624")*D
1193             >= Coefficient("-5895288464414445"));
1194   cs.insert(Coefficient("-3643488643973798")*A
1195             + Coefficient("2251799813685248")*B
1196             + Coefficient("5895288441896447")*C
1197             >= Coefficient("-19077554158229692"));
1198   cs.insert(Coefficient("-7286977296954795")*A
1199             + Coefficient("4503599627370496")*B
1200             - Coefficient("11790576892800094")*C
1201             >= Coefficient("-38155108352488176"));
1202   cs.insert(Coefficient("-4503599627370496")*A
1203             - Coefficient("7286977269933197")*B
1204             + Coefficient("11790576924325290")*D
1205             >= Coefficient("-38155108411034976"));
1206   cs.insert(Coefficient("-3643488639470198")*A
1207             + Coefficient("2251799813685248")*C
1208             + Coefficient("5895288466666245")*D
1209             >= Coefficient("-19077554219028288"));
1210   cs.insert(Coefficient("-4503599627370496")*A
1211             - Coefficient("7286977296954795")*B
1212             - Coefficient("11790576955850488")*D
1213             >= Coefficient("-38155108514617768"));
1214   cs.insert(Coefficient("-7286977251918799")*A
1215             + Coefficient("4503599627370496")*C
1216             - Coefficient("11790576892800094")*D
1217             >= Coefficient("-38155108311955784"));
1218   cs.insert(Coefficient("-3643488655232797")*A
1219             - Coefficient("2251799813685248")*C
1220             + Coefficient("5895288480177044")*D
1221             >= Coefficient("-19077554264064284"));
1222   cs.insert(Coefficient("-1821744320860999")*A
1223             - Coefficient("1125899906842624")*C
1224             - Coefficient("2947644229955423")*D
1225             >= Coefficient("-9538777099381044"));
1226   cs.insert(Coefficient("-4503599627370496")*A
1227             - Coefficient("11790576874785696")*B
1228             + Coefficient("7286977269933197")*C
1229             >= Coefficient("-38155108302948584"));
1230   cs.insert(Coefficient("-7286977274436797")*A
1231             - Coefficient("4503599627370496")*B
1232             + Coefficient("11790576937836090")*C
1233             >= Coefficient("-38155108424545776"));
1234   cs.insert(Coefficient("-4503599627370496")*A
1235             - Coefficient("11790576802728102")*B
1236             - Coefficient("7286977197875603")*C
1237             >= Coefficient("-38155108019221808"));
1238   cs.insert(Coefficient("-3643488664239996")*A
1239             - Coefficient("2251799813685248")*B
1240             - Coefficient("5895288493687843")*C
1241             >= Coefficient("-19077554284330480"));
1242   cs.insert(Coefficient("-562949953421312")*A
1243             - Coefficient("562949953421312")*B
1244             + Coefficient("562949953421312")*C
1245             + Coefficient("562949953421312")*D
1246             >= Coefficient("-2947644250784571"));
1247   cs.insert(Coefficient("-281474976710656")*A
1248             - Coefficient("281474976710656")*B
1249             + Coefficient("281474976710656")*C
1250             - Coefficient("281474976710656")*D
1251             >= Coefficient("-1473822131021785"));
1252   cs.insert(Coefficient("-1125899906842624")*A
1253             - Coefficient("1125899906842624")*B
1254             - Coefficient("1125899906842624")*C
1255             + Coefficient("1125899906842624")*D
1256             >= Coefficient("-5895288464414445"));
1257   cs.insert(Coefficient("-1125899906842624")*A
1258             - Coefficient("1125899906842624")*B
1259             - Coefficient("1125899906842624")*C
1260             - Coefficient("1125899906842624")*D
1261             >= Coefficient("-5895288468918045"));
1262   cs.insert(Coefficient("-3643488412038417")*A
1263             - Coefficient("5895288318047457")*B
1264             + Coefficient("2251799813685248")*D
1265             >= Coefficient("-19077553665085532"));
1266   cs.insert(Coefficient("-1821744199263809")*A
1267             - Coefficient("2947644153394229")*B
1268             - Coefficient("1125899906842624")*D
1269             >= Coefficient("-9538776813402468"));
1270   cs.insert(Coefficient("-5895288378846052")*A
1271             + Coefficient("3643488632714799")*B
1272             + Coefficient("2251799813685248")*C
1273             >= Coefficient("-19077554023121704"));
1274   cs.insert(Coefficient("-11790576834253298")*A
1275             + Coefficient("7286977314969193")*B
1276             - Coefficient("4503599627370496")*C
1277             >= Coefficient("-38155108302948584"));
1278   cs.insert(Coefficient("-736911041726257")*A
1279             + Coefficient("281474976710656")*B
1280             + Coefficient("455436077400500")*D
1281             >= Coefficient("-2384694241068264"));
1282   cs.insert(Coefficient("-5895288347320855")*A
1283             + Coefficient("2251799813685248")*B
1284             - Coefficient("3643488616952200")*D
1285             >= Coefficient("-19077553951064108"));
1286   cs.insert(Coefficient("-2947644201807925")*A
1287             + Coefficient("1821744319735099")*C
1288             + Coefficient("1125899906842624")*D
1289             >= Coefficient("-9538777048715548"));
1290   cs.insert(Coefficient("-11790576820742500")*A
1291             + Coefficient("7286977296954795")*C
1292             - Coefficient("4503599627370496")*D
1293             >= Coefficient("-38155108248905384"));
1294   cs.insert(Coefficient("-11790576996382886")*A
1295             - Coefficient("7286977251918799")*C
1296             + Coefficient("4503599627370496")*D
1297             >= Coefficient("-38155108523624968"));
1298   cs.insert(Coefficient("-5895288507198642")*A
1299             - Coefficient("3643488632714799")*C
1300             - Coefficient("2251799813685248")*D
1301             >= Coefficient("-19077554291085880"));
1302   cs.insert(Coefficient("-11790577113476476")*A
1303             - Coefficient("4503599627370496")*B
1304             + Coefficient("7286977319472793")*D
1305             >= Coefficient("-38155108861394936"));
1306   cs.insert(Coefficient("-5895288572500836")*A
1307             - Coefficient("2251799813685248")*B
1308             - Coefficient("3643488652980997")*D
1309             >= Coefficient("-19077554450963668"));
1310   cs.insert(Coefficient("-5895288484680644")*A
1311             - Coefficient("3643488607945001")*B
1312             + Coefficient("2251799813685248")*C
1313             >= Coefficient("-19077554212272888"));
1314   cs.insert(Coefficient("-2947644274991419")*A
1315             - Coefficient("1821744320860999")*B
1316             - Coefficient("1125899906842624")*C
1317             >= Coefficient("-9538777190578936"));
1318   cs.insert(Coefficient("-2251799813685248")*A
1319             >= Coefficient("-5895288448651847"));
1320 
1321   // Cost function
1322   Linear_Expression cost(10*A + 21*B + 31*C + 45*D);
1323 
1324   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
1325 
1326   Generator pg = mip.optimizing_point();
1327   nout << "Optimizing point = ";
1328   print_generator(pg);
1329 
1330   Coefficient num;
1331   Coefficient den;
1332   mip.evaluate_objective_function(pg, num, den);
1333   nout << "Optimum value = " << num << "/" << den << endl;
1334 
1335   return true;
1336 }
1337 
1338 bool
test06()1339 test06() {
1340   Variable A(0);
1341   Variable B(1);
1342   Linear_Expression cost(A + B);
1343   Constraint_System cs;
1344   cs.insert(-A - B >= -8);
1345   cs.insert(-A - 3*B >= -18);
1346   cs.insert(-A + B >= -4);
1347   cs.insert(A >= 0);
1348   cs.insert(A <= 3);
1349   cs.insert(B >= 0);
1350 
1351   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
1352 
1353   const Coefficient num_kr = 8;
1354   const Coefficient den_kr = 1;
1355   Coefficient num;
1356   Coefficient den;
1357 
1358   Generator pg = mip.optimizing_point();
1359   mip.evaluate_objective_function(pg, num, den);
1360   nout << "Optimum value = " << num << "/" << den << endl;
1361   if (num != num_kr || den != den_kr)
1362     return false;
1363 
1364   nout << "Optimizing point = ";
1365   print_generator(pg);
1366   Generator pg_kr = point(3*A + 5*B);
1367   if (pg != pg_kr)
1368     return false;
1369 
1370   // Set variable A to be constrained to have an integer value.
1371   mip.add_to_integer_space_dimensions(Variables_Set(A));
1372   pg = mip.optimizing_point();
1373   mip.evaluate_objective_function(pg, num, den);
1374   nout << "Optimum value = " << num << "/" << den << endl;
1375   if (num != num_kr || den != den_kr)
1376     return false;
1377   nout << "Optimizing point = ";
1378   print_generator(pg);
1379   if (pg != pg_kr)
1380     return false;
1381 
1382   // Set variable B to be constrained to have an integer value.
1383   mip.add_to_integer_space_dimensions(Variables_Set(B));
1384   pg = mip.optimizing_point();
1385   mip.evaluate_objective_function(pg, num, den);
1386   nout << "Optimum value = " << num << "/" << den << endl;
1387   if (num != num_kr || den != den_kr)
1388     return false;
1389 
1390   nout << "Optimizing point = ";
1391   print_generator(pg);
1392   if (pg != pg_kr)
1393     return false;
1394 
1395   return true;
1396 }
1397 
1398 bool
test07()1399 test07() {
1400   Variable A(0);
1401   Variable B(1);
1402   Linear_Expression cost(A + B);
1403   Constraint_System cs;
1404   cs.insert(-A - 3*B >= -4);
1405   cs.insert(-5*A - B >= -5);
1406   cs.insert(-3*A - 2*B >= -2);
1407   cs.insert(A + 3*B >= -1);
1408   cs.insert(2*A - B >= -2);
1409 
1410   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
1411 
1412   Coefficient num_kr = 8;
1413   Coefficient den_kr = 7;
1414   Coefficient num;
1415   Coefficient den;
1416 
1417   Generator pg = mip.optimizing_point();
1418   mip.evaluate_objective_function(pg, num, den);
1419   nout << "Optimum value = " << num << "/" << den << endl;
1420   if (num != num_kr || den != den_kr)
1421     return false;
1422 
1423   nout << "Optimizing point = ";
1424   print_generator(pg);
1425   Generator pg_kr = point(-2*A + 10*B, 7);
1426   if (pg != pg_kr)
1427     return false;
1428 
1429   // Set variable A to be constrained to have an integer value.
1430   mip.add_to_integer_space_dimensions(Variables_Set(A));
1431   pg = mip.optimizing_point();
1432   mip.evaluate_objective_function(pg, num, den);
1433 
1434   num_kr = 1;
1435   den_kr = 1;
1436   nout << "Optimum value = " << num << "/" << den << endl;
1437   if (num != num_kr || den != den_kr)
1438     return false;
1439   pg_kr = point(B);
1440   nout << "Optimizing point = ";
1441   print_generator(pg);
1442   if (pg != pg_kr)
1443     return false;
1444 
1445   // Set variable B to be constrained to have an integer value.
1446   mip.add_to_integer_space_dimensions(Variables_Set(B));
1447   pg = mip.optimizing_point();
1448   mip.evaluate_objective_function(pg, num, den);
1449   nout << "Optimum value = " << num << "/" << den << endl;
1450   if (num != num_kr || den != den_kr)
1451     return false;
1452 
1453   nout << "Optimizing point = ";
1454   print_generator(pg);
1455   if (pg != pg_kr)
1456     return false;
1457 
1458   return true;
1459 }
1460 
1461 bool
test08()1462 test08() {
1463   Variable A(0);
1464   Variable B(1);
1465   Variable C(2);
1466   Variable D(3);
1467   Linear_Expression cost(12*A + 6*B + 4*C + 3*D);
1468 
1469   Constraint_System cs;
1470   cs.insert(A >= 0);
1471   cs.insert(B >= 0);
1472   cs.insert(C >= 0);
1473   cs.insert(D >= 0);
1474   cs.insert(3008*A + 20980*B - 97775*C - 101225*D >= 0);
1475   cs.insert(3985*A + 25643*B - 135871*C - 130580*D >= 0);
1476   cs.insert(4324*A + 26978*B - 133655*C - 168473*D >= 0);
1477   cs.insert(3534*A + 25361*B - 46243*C - 100407*D >= 0);
1478   cs.insert(8836*A + 40796*B - 176661*C - 215616*D >= 0);
1479   cs.insert(5376*A + 37562*B - 182576*C - 217615*D >= 0);
1480   cs.insert(2491*A + 16544*B - 49440*C - 83639*D >= 0);
1481   cs.insert(4775*A + 39122*B - 136701*C - 193393*D >= 0);
1482   cs.insert(8046*A + 42958*B - 225138*C - 256575*D >= 0);
1483   cs.insert(8554*A + 48955*B - 257370*C - 312877*D >= 0);
1484   cs.insert(6147*A + 45514*B - 165274*C - 227099*D >= 0);
1485   cs.insert(8366*A + 55140*B - 203989*C - 321623*D >= 0);
1486   cs.insert(13479*A + 68037*B - 174270*C - 341743*D >= 0);
1487   cs.insert(21808*A + 78302*B - 322990*C - 487539*D >= 0);
1488   cs.insert(-8554*A - 48955*B >= -10000);
1489   cs.insert(-257370*C - 312877*D >= -10000);
1490 
1491   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
1492 
1493   Coefficient num_kr = Coefficient("8231960000");
1494   Coefficient den_kr = 581120267;
1495   Coefficient num;
1496   Coefficient den;
1497 
1498   Generator pg = mip.optimizing_point();
1499   mip.evaluate_objective_function(pg, num, den);
1500   nout << "Optimum value = " << num << "/" << den << endl;
1501   if (num != num_kr || den != den_kr)
1502     return false;
1503   nout << "Optimizing point = ";
1504   print_generator(pg);
1505   Generator pg_kr = point(679355000*A + 19925000*C + 0*D, 581120267);
1506   if (pg != pg_kr)
1507     return false;
1508 
1509   // Set variable A to be constrained to have an integer value.
1510   mip.add_to_integer_space_dimensions(Variables_Set(A));
1511   pg = mip.optimizing_point();
1512   mip.evaluate_objective_function(pg, num, den);
1513 
1514   num_kr = Coefficient("81926256268");
1515   den_kr = Coefficient("6651564805");
1516   nout << "Optimum value = " << num << "/" << den << endl;
1517   if (num != num_kr || den != den_kr)
1518     return false;
1519   pg_kr = point(Coefficient("6651564805")*A + 196469466*B + 232165453*C + 0*D,
1520                 Coefficient("6651564805"));
1521   nout << "Optimizing point = ";
1522   print_generator(pg);
1523   if (pg != pg_kr)
1524     return false;
1525 
1526   // Set variable B to be constrained to have an integer value.
1527   mip.add_to_integer_space_dimensions(Variables_Set(B));
1528   pg = mip.optimizing_point();
1529   mip.evaluate_objective_function(pg, num, den);
1530 
1531   num_kr = 1646392;
1532   den_kr = 135871;
1533   nout << "Optimum value = " << num << "/" << den << endl;
1534   if (num != num_kr || den != den_kr)
1535     return false;
1536   pg_kr = point(135871*A + 3985*C + 0*D, 135871);
1537   nout << "Optimizing point = ";
1538   print_generator(pg);
1539   if (pg != pg_kr)
1540     return false;
1541 
1542   // Set variable C to be constrained to have an integer value.
1543   mip.add_to_integer_space_dimensions(Variables_Set(C));
1544   pg = mip.optimizing_point();
1545   mip.evaluate_objective_function(pg, num, den);
1546 
1547   num_kr = 2335041;
1548   den_kr = 193393;
1549   nout << "Optimum value = " << num << "/" << den << endl;
1550   if (num != num_kr || den != den_kr)
1551     return false;
1552   pg_kr = point(193393*A + 4775*D, 193393);
1553   nout << "Optimizing point = ";
1554   print_generator(pg);
1555   if (pg != pg_kr)
1556     return false;
1557 
1558   // Set variable D to be constrained to have an integer value.
1559   mip.add_to_integer_space_dimensions(Variables_Set(D));
1560   pg = mip.optimizing_point();
1561   mip.evaluate_objective_function(pg, num, den);
1562 
1563   num_kr = 12;
1564   den_kr = 1;
1565   nout << "Optimum value = " << num << "/" << den << endl;
1566   if (num != num_kr || den != den_kr)
1567     return false;
1568   pg_kr = point(A + 0*D);
1569   nout << "Optimizing point = ";
1570   print_generator(pg);
1571   if (pg != pg_kr)
1572     return false;
1573 
1574   return true;
1575 }
1576 
1577 bool
test09()1578 test09() {
1579   Variable A(0);
1580   Variable B(1);
1581   Variable C(2);
1582   Linear_Expression cost(A + B + C);
1583   Constraint_System cs;
1584   cs.insert(A >= -1);
1585   cs.insert(B >= -1);
1586   cs.insert(C >= -1);
1587   cs.insert(-A >= -1);
1588   cs.insert(-B >= -1);
1589   cs.insert(-C >= -1);
1590 
1591   MIP_Problem mip = MIP_Problem(cs.space_dimension(), cs, cost, MAXIMIZATION);
1592 
1593   Coefficient num_kr = 3;
1594   Coefficient den_kr = 1;
1595   Coefficient num;
1596   Coefficient den;
1597 
1598   Generator pg = mip.optimizing_point();
1599   mip.evaluate_objective_function(pg, num, den);
1600   nout << "Optimum value = " << num << "/" << den << endl;
1601   if (num != num_kr || den != den_kr)
1602     return false;
1603   nout << "Optimizing point = ";
1604   print_generator(pg);
1605   Generator pg_kr = point(A + B + C);
1606   if (pg != pg_kr)
1607     return false;
1608 
1609   // Set variable A to be constrained to have an integer value.
1610   mip.add_to_integer_space_dimensions(Variables_Set(A));
1611   pg = mip.optimizing_point();
1612   mip.evaluate_objective_function(pg, num, den);
1613 
1614   nout << "Optimum value = " << num << "/" << den << endl;
1615   if (num != num_kr || den != den_kr)
1616     return false;
1617   nout << "Optimizing point = ";
1618   print_generator(pg);
1619   if (pg != pg_kr)
1620     return false;
1621 
1622   // Set variable B to be constrained to have an integer value.
1623   mip.add_to_integer_space_dimensions(Variables_Set(B));
1624   pg = mip.optimizing_point();
1625   mip.evaluate_objective_function(pg, num, den);
1626 
1627   nout << "Optimum value = " << num << "/" << den << endl;
1628   if (num != num_kr || den != den_kr)
1629     return false;
1630   nout << "Optimizing point = ";
1631   print_generator(pg);
1632   if (pg != pg_kr)
1633     return false;
1634 
1635   // Set variable C to be constrained to have an integer value.
1636   mip.add_to_integer_space_dimensions(Variables_Set(C));
1637   pg = mip.optimizing_point();
1638   mip.evaluate_objective_function(pg, num, den);
1639 
1640   nout << "Optimum value = " << num << "/" << den << endl;
1641   if (num != num_kr || den != den_kr)
1642     return false;
1643   nout << "Optimizing point = ";
1644   print_generator(pg);
1645   if (pg != pg_kr)
1646     return false;
1647 
1648   return true;
1649 }
1650 
1651 bool
test10()1652 test10() {
1653   Variable A(0);
1654   Variable B(1);
1655   Variable C(2);
1656 
1657   // Feasible region.
1658   Constraint_System cs;
1659   cs.insert(A + B <= 1);
1660   cs.insert(A + C <= 1);
1661   cs.insert(B + C <= 1);
1662 
1663   // All integer variables.
1664   Variables_Set ivs(A, C);
1665 
1666   // Cost function.
1667   Linear_Expression cost(-2*A - 3*B - 4*C);
1668 
1669   MIP_Problem mip(cs.space_dimension(), cs.begin(), cs.end(), ivs, cost,
1670                   MINIMIZATION);
1671 
1672   if (mip.solve() != OPTIMIZED_MIP_PROBLEM)
1673     return false;
1674 
1675   Generator pg = mip.optimizing_point();
1676   nout << "Optimizing point = ";
1677   using namespace Parma_Polyhedra_Library::IO_Operators;
1678   nout << pg << endl;
1679 
1680   return true;
1681 }
1682 
1683 } // namespace
1684 
1685 BEGIN_MAIN
1686   DO_TEST_F64(test01);
1687   DO_TEST_F32(test02);
1688   DO_TEST_F64(test03);
1689   DO_TEST_F32(test04);
1690   DO_TEST_F64(test05);
1691   DO_TEST(test06);
1692   DO_TEST(test07);
1693   DO_TEST_F64(test08);
1694   DO_TEST(test09);
1695   DO_TEST(test10);
1696 END_MAIN
1697