Hi all,

here I attach an polyhedron of smaller dimensionality: I also ask for 'contains_integer_point'. It does not give me any result in reasonable time (actually I did not wait until it gives any result, since it took more than few minutes). I try it on 32-bit machine.

Thanks, Konrad

2009/7/9 Konrad Trifunovic konrad.trifunovic@gmail.com:

Hi,

that's a good point. We DO NOT need NNC polyhedra. Closed Polyhedra are fine (at least for dependence analysis). Do You think that using C_Polyhedron would help us avoid the much of the complexity problems?

from my analysis (by looking at the PPL code) I have seen that the "contains_integer_point" methods call the MIP (Mixed Integer Programming) routines, to solve the system of constraints. I have seen that it behaves differently in the case of Convex and NNC polyhedra.

regards, Konrad

2009/7/9 Roberto Bagnara bagnara@cs.unipr.it:

...

Konrad Trifunovic wrote:

...

I attach a patch that uses 'integer existence test'. I have forced the use of dependence check.

Hi there.

I am sorry if the answer is obvious, but I am wondering why you are using NNC polyhedra (NNC_Polyhedron) instead of ordinary polyhedra (C_Polyhedron).  Do you need to characterize rational solutions and use strict constraints? All the best,

Roberto

-- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "GCC GRAPHITE" group. To post to this group, send email to gcc-graphite@googlegroups.com To unsubscribe from this group, send email to gcc-graphite+unsubscribe@googlegroups.com For more options, visit this group at http://groups.google.de/group/gcc-graphite?hl=en -~----------~----~----~----~------~----~------~--~---

Konrad Trifunovic wrote:

Hi all,

the other tip that I give: if I try to resolve the same polyhedron, but if I make it Closed Polyhedron, then the solver 'contains_integer_point' runs out of memory.

Konrad

Hello.

We made a quick test using your data (the higher dimension data).

The test seems to confirm what was said by Roberto: you should use C_Polyhedron instead of NNC_Polyhedron. If you *need* to use NNC_Polyhedron we will have to do something to improve efficiency, but there seem to be no efficiency problem on your example if you stick to C_Polyhedron.

We made the following test (using the C++ interface): - load your ascii dump into a Pointset_Powerset<NNC_Polyhedron> - re-dumping it out (just to be sure we are making no silly mistakes) - extract the singleton NNC_Polyhedron (ph) from the powerset - convert it into a C_Polyhedron (c_ph) - asking if it contains an integer point (just to be sure that it does not depend on the representation given) - build another copy of c_ph, but using generators - asking again if it contains an integer point

On my notebook (a 64 bit machine), the whole thing takes time:

real 0m0.039s user 0m0.011s sys 0m0.014s

Regarding the memory consumption, I tried the example above after setting

# ulimit -S -v 20000

and it runs to completion (it fails with 19000).

I am attaching the source of the test program (containsintegerpoint2.cc), the input ascii-dump (aaa.dat), and the output we obtain (test.out). Note that the test sources assume the PPL test infrastructure ... let us know if you need a self contained test program.

Cheers, Enea Zaffanella.

size 1 space_dim 18 space_dim 18 -ZE -EM +CM +GM +CS +GS -CP -GP +SC -SG con_sys (up-to-date) topology NOT_NECESSARILY_CLOSED 22 x 20 (not_sorted) index_first_pending 22 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 = 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 0 0 0 -8192 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 -8192 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 > 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 >= 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 > 67100672 0 -1 0 -8192 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 >= 8191 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >= gen_sys (up-to-date) topology NOT_NECESSARILY_CLOSED 12 x 20 (not_sorted) index_first_pending 12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 C 1 0 8191 0 0 0 8191 0 0 8191 0 0 0 8191 0 1 8191 1 8191 0 C 8192 0 67100672 0 67100671 0 67100672 67100671 0 67092480 0 67100672 0 67092480 67100672 8192 549755797504 8192 549755797504 8192 P 8192 0 67100672 0 67092481 0 67100672 67092481 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 8192 P 8192 0 8192 0 67100671 0 8192 67100671 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 8192 P 8192 0 67100672 0 67092481 0 67100672 67092481 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 0 C 1 0 8191 0 8191 0 8191 8191 0 8191 0 8191 0 8191 8191 1 67108863 1 67108863 0 C 8192 0 67100672 0 0 0 67100672 0 0 0 0 8191 0 0 8191 8192 67100672 8192 67100672 0 C 1 0 0 0 8191 0 0 8191 0 0 0 8191 0 0 8191 1 67100672 1 67100672 0 C 8192 0 67100672 0 0 0 67100672 0 0 67092480 0 1 0 67092480 1 8192 67100672 8192 67100672 8192 P 8192 0 67100672 0 0 0 67100672 0 0 0 0 8191 0 0 8191 8192 67100672 8192 67100672 8192 P 8192 0 8192 0 0 0 8192 0 0 0 0 1 0 0 1 8192 8192 8192 8192 8192 P sat_c 12 x 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 sat_g 3 x 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

=== test01 ===

Loading the ascii dump into NNC pointset powerset pps:

Re-dumping pps (for double checking): size 1 space_dim 18 space_dim 18 -ZE -EM +CM +GM +CS +GS -CP -GP +SC -SG con_sys (up-to-date) topology NOT_NECESSARILY_CLOSED 22 x 20 (not_sorted) index_first_pending 22 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 = 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 0 0 0 -8192 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 -8192 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 > 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 >= 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 > 67100672 0 -1 0 -8192 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 >= 8191 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >=

gen_sys (up-to-date) topology NOT_NECESSARILY_CLOSED 12 x 20 (not_sorted) index_first_pending 12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 C 1 0 8191 0 0 0 8191 0 0 8191 0 0 0 8191 0 1 8191 1 8191 0 C 8192 0 67100672 0 67100671 0 67100672 67100671 0 67092480 0 67100672 0 67092480 67100672 8192 549755797504 8192 549755797504 8192 P 8192 0 67100672 0 67092481 0 67100672 67092481 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 8192 P 8192 0 8192 0 67100671 0 8192 67100671 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 8192 P 8192 0 67100672 0 67092481 0 67100672 67092481 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 0 C 1 0 8191 0 8191 0 8191 8191 0 8191 0 8191 0 8191 8191 1 67108863 1 67108863 0 C 8192 0 67100672 0 0 0 67100672 0 0 0 0 8191 0 0 8191 8192 67100672 8192 67100672 0 C 1 0 0 0 8191 0 0 8191 0 0 0 8191 0 0 8191 1 67100672 1 67100672 0 C 8192 0 67100672 0 0 0 67100672 0 0 67092480 0 1 0 67092480 1 8192 67100672 8192 67100672 8192 P 8192 0 67100672 0 0 0 67100672 0 0 0 0 8191 0 0 8191 8192 67100672 8192 67100672 8192 P 8192 0 8192 0 0 0 8192 0 0 0 0 1 0 0 1 8192 8192 8192 8192 8192 P

sat_c 12 x 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0

sat_g 0 x 0

Extracting NNC polyhedron ph from powerset: Pretty printing its constraints: *** ph *** B + 8192*D - R = 0, Q = 1, B + 8192*D - P = 0, O = 1, B + 8192*D - I - 8192*N = 0, I - M = 0, L = 0, B + 8192*D - I - 8192*K = 0, J = 0, H = 0, D - G = 0, B - F = 0, E = 0, C = 0, A = 0, B - I > 0, -B - 8192*D + I >= -67100672, -B >= -8191, I >= 0, D >= 0. Pretty printing its generators: *** ph *** c(O + Q), c(8191*D + 8191*G + 8191*K + 8191*N + O + 67100672*P + Q + 67100672*R), c(8191*B + 8191*F + 8191*I + 8191*M + O + 8191*P + Q + 8191*R), c(8191*B + 8191*D + 8191*F + 8191*G + 8191*I + 8191*K + 8191*M + 8191*N + O + 67108863*P + Q + 67108863*R), p((8192*B + 8192*F + K + N + 8192*O + 8192*P + 8192*Q + 8192*R)/8192), p((8192*B + 67100671*D + 8192*F + 67100671*G + 67100672*K + 67100672*N + 8192*O + 549688705024*P + 8192*Q + 549688705024*R)/8192), p((67100672*B + 67100672*F + 8191*K + 8191*N + 8192*O + 67100672*P + 8192*Q + 67100672*R)/8192), p((67100672*B + 67100672*F + 67092480*I + K + 67092480*M + N + 8192*O + 67100672*P + 8192*Q + 67100672*R)/8192), p((67100672*B + 67092481*D + 67100672*F + 67092481*G + 67100672*K + 67100672*N + 8192*O + 549688705024*P + 8192*Q + 549688705024*R)/8192), p((67100672*B + 67100671*D + 67100672*F + 67100671*G + 67092480*I + 67100672*K + 67092480*M + 67100672*N + 8192*O + 549755797504*P + 8192*Q + 549755797504*R)/8192).

Creating a C_Polyhedron c_ph from ph:

Dumping the C_Polyhedron: space_dim 18 -ZE -EM -CM -GM +CS -GS -CP -GP -SC -SG con_sys (up-to-date) topology NECESSARILY_CLOSED 21 x 19 (not_sorted) index_first_pending 21 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >= 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 = 0 0 1 0 8192 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 = -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 0 0 0 -8192 0 0 0 0 = 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 = 0 0 1 0 8192 0 0 0 0 -1 0 -8192 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 = 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 >= 67100672 0 -1 0 -8192 0 0 0 0 1 0 0 0 0 0 0 0 0 0 >= 8191 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 >= 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >=

gen_sys (not_up-to-date) topology NECESSARILY_CLOSED 0 x 0 (sorted) index_first_pending 0

sat_c 0 x 0

sat_g 0 x 0

Pretty printing its constraints: *** c_ph *** B + 8192*D - R = 0, Q = 1, B + 8192*D - P = 0, O = 1, B + 8192*D - I - 8192*N = 0, I - M = 0, L = 0, B + 8192*D - I - 8192*K = 0, J = 0, H = 0, D - G = 0, B - F = 0, E = 0, C = 0, A = 0, B - I >= 0, -B - 8192*D + I >= -67100672, -B >= -8191, I >= 0, D >= 0. Checking for an integer point ... true

Dumping the C_Polyhedron copy: space_dim 18 -ZE -EM -CM -GM -CS +GS -CP -GP -SC -SG con_sys (not_up-to-date) topology NECESSARILY_CLOSED 0 x 0 (sorted) index_first_pending 0

gen_sys (up-to-date) topology NECESSARILY_CLOSED 6 x 19 (not_sorted) index_first_pending 6 8192 0 67100672 0 0 0 67100672 0 0 0 0 8191 0 0 8191 8192 67100672 8192 67100672 P 8192 0 67100672 0 67092481 0 67100672 67092481 0 0 0 67100672 0 0 67100672 8192 549688705024 8192 549688705024 P 1 0 8191 0 8191 0 8191 8191 0 8191 0 8191 0 8191 8191 1 67108863 1 67108863 P 1 0 0 0 8191 0 0 8191 0 0 0 8191 0 0 8191 1 67100672 1 67100672 P 1 0 8191 0 0 0 8191 0 0 8191 0 0 0 8191 0 1 8191 1 8191 P 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 P

sat_c 0 x 0

sat_g 0 x 0

Pretty printing its generators: *** c_ph2 *** p((67100672*B + 67100672*F + 8191*K + 8191*N + 8192*O + 67100672*P + 8192*Q + 67100672*R)/8192), p((67100672*B + 67092481*D + 67100672*F + 67092481*G + 67100672*K + 67100672*N + 8192*O + 549688705024*P + 8192*Q + 549688705024*R)/8192), p(8191*B + 8191*D + 8191*F + 8191*G + 8191*I + 8191*K + 8191*M + 8191*N + O + 67108863*P + Q + 67108863*R), p(8191*D + 8191*G + 8191*K + 8191*N + O + 67100672*P + Q + 67100672*R), p(8191*B + 8191*F + 8191*I + 8191*M + O + 8191*P + Q + 8191*R), p(O + Q). Checking for an integer point ... true

Thank You for Your work,

indeed, when changed to C_Polyhedron this example was solved quickly. It made me think that changing all the polyhedrons to C_Polyhedron would solve the problems, unfortunately I have found some other examples that take a long time, even when being expressed as C_Polyhedrons. Stay tuned, I will send an examples.

Thanks, Konrad

2009/7/10 Enea Zaffanella zaffanella@cs.unipr.it:

Enea Zaffanella wrote:

...

Konrad Trifunovic wrote:

...

Hi all,

the other tip that I give: if I try to resolve the same polyhedron, but if I make it Closed Polyhedron, then the solver 'contains_integer_point' runs out of memory.

Konrad

Hello.

We made a quick test using your data (the higher dimension data).

I just saw that I made a mistake in the test ...

I haven't noticed that the input test was actually containing a strict inequality constraint ... so I was "over-approximating" it using a non-strict inequality (when converting the NNC to the C polyhedron).

I will investigate further.

Enea.

Thank you Roberto for the long and detailed email.

Indeed, we should keep in mind to always ask on the ppl mailing list early on.

Regarding the need to solve integer programming problems, my view is twofold: 1. For the case of Array Dataflow Analysis, it is critical to have a parametric integer linear programming solver, in the form of the evolution of PIP you are working on. We can leave without it for early experiments, but it will be needed for any scalable (and precise) analysis. 2. For plain dependence analysis and testing (the problem that triggered the whole thread), it is certainly not critical. It would of course improve precision, but the problems raised by Konrad and Li were due to a wrong design that was re-analysing the polyhedral representation AFTER strip-mining of loops, itself responsible for the introduction of large constants. Konrad is updating the dependence analysis and the strip-minig API such that this won't be necessary anymore.

I hope the problems raised on this thread will disappear (for now) when this is fixed.

Thanks, Albert

Roberto Bagnara wrote:

Konrad Trifunovic wrote:

...

indeed, when changed to C_Polyhedron this example was solved quickly. It made me think that changing all the polyhedrons to C_Polyhedron would solve the problems, unfortunately I have found some other examples that take a long time, even when being expressed as C_Polyhedrons. Stay tuned, I will send an examples.

Hi All.

I propose we start from the very beginning.

The first thing I would like to do is to solve the communication problem. There must be a communication problem because it is only by chance that I discovered gcc-graphite@googlegroups.com and that, on it, people was discussing about problems they have with the PPL. The same happened already at least a couple of times on the gcc mailing lists: people had troubles using the PPL and they did not mail ppl-devel@cs.unipr.it. However, we made it very clear that we have a 100% determination to support all our users, GCC and Graphite in particular. So, please, do talk with us as soon as what appears to be a problem shows up. Even better: please let us know in advance what you plan to do with the PPL and how. Believe me: we can help.

Now, the complexity problems. I am not sure I understand what you are trying to accomplish, but it seems to me that you call for the solution of (pure or mixed) integer programming problems. As integer programming is NP-complete (and very tough also in practical terms), there is no way you can obtain efficiency _unless_ the problems you are trying to solve have a peculiar structure and you use algorithms that are able to exploit it. Concerning the PPL, MIP problems are solved using a textbook implementation of branch-and-bound, which, in turn, uses a textbook implementation of primal simplex. Branch-and-bound is not even guaranteed to terminate and can generate zillions of subproblems. So the only sensible way to use it is by either:

a) ensuring the problem is small enough and solvable by branch-and-bound; and/or

b) guarding the computation with a time threshold and a memory threshold (the PPL provides support for both).

A possibility to obtain a better performance would be to use the PPL/GLPK interface. This is already available in the `simplex' branch of the main PPL Git repository. The reason we do not merge this with `master' is that until now we failed to convince the GLPK people to move the bignum simplex interface to the installed glpk.h: that interface is currently only available by using an header file that is not installed. Note that this would not substantially transform your problem: you will have to set time/memory threshold anyway. All the best,

Roberto

P.S. Concerning point (b) above, we are installing in the main Git repository mechanisms to impose (deterministic) limits to the computation performed by expensive PPL computation (including those that take place in MIP_Problem).

P.S. I have checked that the issue I mentioned witth respect to GLPK is still present in the latest version (4.38). There was also another issue with it, but I have no time right now to check if this is still present: even in the bignum simplex solver, GLPK was making unsafe approximations in order to keep the coefficients small. Perhaps this is no longer the case.