Enumerating all integer feasible points, CPLEX vs Polymake

[opfer]

Thomas,

Thanks. But it is not working for me

I downloaded ppl from their website, then did configure with the enabling on, make and install.

Did you use the parameter "--enable-ppl_lcdd" for configure?

polymake does not use ppl in the floating-point mode yet, rather for rational numbers only. There was simply no demand for that, until you came across

I don't even know whether PPL has support for floating-point arithmetic. But in this case, it seems fast enough with rational numbers.

Best regards,
Thomas

[UserCplex]

Gawrilow and Thomas:

Below is the log from ./configure --enable-ppl_lcdd

Does anything obvious stand out for you in terms of missing dependencies? I am rather new to ubuntu/linux. I can understand if you don't want to get into this. I will go to ppl website and look through their support files as well.

Thanks.

checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking for a BSD-compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking for a thread-safe mkdir -p... /bin/mkdir -p
checking for gawk... no
checking for mawk... mawk
checking whether make sets $(MAKE)... yes
checking whether make supports nested variables... yes
checking whether UID '1000' is supported by ustar format... yes
checking whether GID '1000' is supported by ustar format... yes
checking how to create a ustar tar archive... gnutar
checking for gcc... gcc
checking whether the C compiler works... yes
checking for C compiler default output file name... a.out
checking for suffix of executables...
checking whether we are cross compiling... no
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes
checking whether gcc accepts -g... yes
checking for gcc option to accept ISO C89... none needed
checking whether gcc understands -c and -o together... yes
checking for style of include used by make... GNU
checking dependency style of gcc... gcc3
checking whether we are actually using the Intel C compiler... no
checking whether we are actually using clang... no
checking whether we are actually using llvm-gcc... no
checking for g++... g++
checking whether we are using the GNU C++ compiler... yes
checking whether g++ accepts -g... yes
checking dependency style of g++... gcc3
checking whether we are actually using the Intel C++ compiler... no
checking whether we are actually using clang++... no
checking whether we are actually using llvm-g++... no
checking for grep that handles long lines and -e... /bin/grep
checking for fgrep... /bin/grep -F
checking for egrep... /bin/grep -E
checking for a sed that does not truncate output... /bin/sed
checking how to run the C++ preprocessor... g++ -E
checking whether make sets $(MAKE)... (cached) yes
checking whether to compile with debug info... yes
checking whether to compile for profiling... no
checking whether to compile for test coverage... no
checking whether to enable checking of run-time assertions... no
checking whether to enable even more run-time assertions... no
checking whether to enable optimizations... standard
checking for which architecture to optimize... default
checking whether to use (a specific) floating point arithmetic... default
checking whether to use precompiled headers... no
checking the type of integral values to use as coefficients... GMP mpz
checking for an ANSI C-conforming const... yes
checking for inline... inline
checking how to run the C preprocessor... gcc -E
checking for ANSI C header files... yes
checking for sys/types.h... yes
checking for sys/stat.h... yes
checking for stdlib.h... yes
checking for string.h... yes
checking for memory.h... yes
checking for strings.h... yes
checking for inttypes.h... yes
checking for stdint.h... yes
checking for unistd.h... yes
checking whether byte ordering is bigendian... no
checking for typeof syntax and keyword spelling... typeof
checking size of char... 1
checking size of short... 2
checking size of int... 4
checking size of long... 8
checking size of long long... 8
checking size of size_t... 8
checking size of float... 4
checking size of double... 8
checking size of long double... 16
checking size of int*... 8
checking size of fp... 8
checking for perl... /usr/bin/perl
checking for library containing sqrt... none required
checking fenv.h usability... yes
checking fenv.h presence... yes
checking for fenv.h... yes
checking ieeefp.h usability... no
checking ieeefp.h presence... no
checking for ieeefp.h... no
checking if it is possible to control the FPU... yes
checking whether the plain char type is signed... yes
checking whether the C++ compiler provides proper long doubles... yes
checking the binary format of C++ floats... IEEE754 Single Precision
checking the binary format of C++ doubles... IEEE754 Double Precision
checking the binary format of C++ long doubles... Intel Double-Extended
checking whether std::floor(long double) is buggy... no
checking whether the C++ compiler supports zero-length arrays... yes
checking whether the IEEE inexact flag is supported in C++... yes
checking whether the C++ compiler supports __attribute__ ((weak))... yes
checking for fenv.h... (cached) yes
checking for ieeefp.h... (cached) no
checking getopt.h usability... yes
checking getopt.h presence... yes
checking for getopt.h... yes
checking signal.h usability... yes
checking signal.h presence... yes
checking for signal.h... yes
checking for string.h... (cached) yes
checking for strings.h... (cached) yes
checking sys/resource.h usability... yes
checking sys/resource.h presence... yes
checking for sys/resource.h... yes
checking sys/time.h usability... yes
checking sys/time.h presence... yes
checking for sys/time.h... yes
checking for sys/types.h... (cached) yes
checking for unistd.h... (cached) yes
checking whether ffs is declared... yes
checking whether getenv is declared... yes
checking whether strtof is declared... yes
checking whether strtod is declared... yes
checking whether strtold is declared... yes
checking whether strtoll is declared... yes
checking whether strtoull is declared... yes
checking whether fma is declared... yes
checking whether fmaf is declared... yes
checking whether fmal is declared... yes
checking whether rintf is declared... yes
checking whether rintl is declared... yes
checking for int_fast16_t... yes
checking for int_fast32_t... yes
checking for int_fast64_t... yes
checking for uint_fast16_t... yes
checking for uint_fast32_t... yes
checking for uint_fast64_t... yes
checking for uintptr_t... yes
checking how to print strings... printf
checking for a sed that does not truncate output... (cached) /bin/sed
checking for ld used by gcc... /usr/bin/ld
checking if the linker (/usr/bin/ld) is GNU ld... yes
checking for BSD- or MS-compatible name lister (nm)... /usr/bin/nm -B
checking the name lister (/usr/bin/nm -B) interface... BSD nm
checking whether ln -s works... yes
checking the maximum length of command line arguments... 1572864
checking whether the shell understands some XSI constructs... yes
checking whether the shell understands "+="... yes
checking how to convert x86_64-pc-linux-gnu file names to x86_64-pc-linux-gnu format... func_convert_file_noop
checking how to convert x86_64-pc-linux-gnu file names to toolchain format... func_convert_file_noop
checking for /usr/bin/ld option to reload object files... -r
checking for objdump... objdump
checking how to recognize dependent libraries... pass_all
checking for dlltool... no
checking how to associate runtime and link libraries... printf %s\n
checking for ar... ar
checking for archiver @FILE support... @
checking for strip... strip
checking for ranlib... ranlib
checking command to parse /usr/bin/nm -B output from gcc object... ok
checking for sysroot... no
checking for mt... mt
checking if mt is a manifest tool... no
checking for dlfcn.h... yes
checking for objdir... .libs
checking if gcc supports -fno-rtti -fno-exceptions... no
checking for gcc option to produce PIC... -fPIC -DPIC
checking if gcc PIC flag -fPIC -DPIC works... yes
checking if gcc static flag -static works... yes
checking if gcc supports -c -o file.o... yes
checking if gcc supports -c -o file.o... (cached) yes
checking whether the gcc linker (/usr/bin/ld -m elf_x86_64) supports shared libraries... yes
checking whether -lc should be explicitly linked in... no
checking dynamic linker characteristics... GNU/Linux ld.so
checking how to hardcode library paths into programs... immediate
checking for shl_load... no
checking for shl_load in -ldld... no
checking for dlopen... no
checking for dlopen in -ldl... yes
checking whether a program can dlopen itself... yes
checking whether a statically linked program can dlopen itself... no
checking whether stripping libraries is possible... yes
checking if libtool supports shared libraries... yes
checking whether to build shared libraries... yes
checking whether to build static libraries... yes
checking how to run the C++ preprocessor... g++ -E
checking for ld used by g++... /usr/bin/ld -m elf_x86_64
checking if the linker (/usr/bin/ld -m elf_x86_64) is GNU ld... yes
checking whether the g++ linker (/usr/bin/ld -m elf_x86_64) supports shared libraries... yes
checking for g++ option to produce PIC... -fPIC -DPIC
checking if g++ PIC flag -fPIC -DPIC works... yes
checking if g++ static flag -static works... yes
checking if g++ supports -c -o file.o... yes
checking if g++ supports -c -o file.o... (cached) yes
checking whether the g++ linker (/usr/bin/ld -m elf_x86_64) supports shared libraries... yes
checking dynamic linker characteristics... (cached) GNU/Linux ld.so
checking how to hardcode library paths into programs... immediate
configure: creating ./config.lt
config.lt: creating libtool
checking for the GMP library version 4.1.3 or above... yes
checking size of mp_limb_t... 8
checking whether GMP has been compiled with support for exceptions... yes
checking for __mpz_struct._mp_alloc... yes
checking for __mpz_struct._mp_size... yes
checking for __mpz_struct._mp_d... yes
checking whether to build the ppl_lcdd program... yes
checking whether to build the ppl_lpsol program... yes
checking whether to build the ppl_pips program... yes
checking whether to build the PPL documentation... yes
checking which interfaces are enabled... cxx c ocaml java
checking for javac... no
checking for java... no
checking for jar... no
checking for javah... no
configure: WARNING: unable to include <jni.h>
checking whether jlong can contain data pointers... no
checking for ocamlc... no
checking for ocamldep... no
checking for ocamlmktop... no
checking for ocamlmklib... no
checking for ocamldoc... no
checking for ocamlbuild... no
checking for GNU M4 that supports accurate traces... configure: error: no acceptable m4 could be found in $PATH.
GNU M4 1.4.5 or later is required; 1.4.11 or later is recommended

[opfer]

First, please install M4:

Code: Select all

apt install m4

Then see if configure has further errors.

Also, on Ubuntu, I would not install to the default path. I'd rather do something like

Code: Select all

./configure --prefix=/opt/ppl --enable-ppl_lcdd

Then after "make" and "make install", you should be able to call /opt/ppl/bin/ppl_lcdd .

For this test, this should be sufficient. Then you can easily remove /opt/ppl if something does not work as intended.

Best regards,
Thomas

[gawrilow]

Code: Select all

./configure --prefix=/opt/ppl --enable-ppl_lcdd

This would usually require sudo for make install, because /opt is owned by root.

[gawrilow]

I don't even know whether PPL has support for floating-point arithmetic. But in this case, it seems fast enough with rational numbers.

Yes, it does support floats, but as said before, there is no polymake interface for that.

[UserCplex]

Thomas

Thank you very much. Following your instructions, I have indeed been able to run ppl_lcdd from the bin folder and link it to test2.txt file you shared.

Yes, gawrilow was also right. I had to do sudo make install.

I obtain an output that lists:

414 40 integer
<<and equations?>>

Is there a way to correlate these coefficients with the variables of the cplex lp file of the OP? In other words, is there an easy way to interpret the ppl output ?

That is, could you let me know in what order did you populate the variables in your test2.txt file and meaning of other entries in that file? Then, if I understand the correlation between test2.txt file and ppl output, I can write some wrapper code around this that spits out the equations/inequalities in human understandable form.

[opfer]

Code: Select all

./configure --prefix=/opt/ppl --enable-ppl_lcdd

This would usually require sudo for make install, because /opt is owned by root.

Thanks for pointing this out. I typiclaly chown the folders before, e.g.:

Code: Select all

sudo mkdir /opt/ppl sudo chown opfer. /opt/ppl

Then you don't need sudo for the installation process.

Is there a way to correlate these coefficients with the variables of the cplex lp file of the OP? In other words, is there an easy way to interpret the ppl output ?

That is, could you let me know in what order did you populate the variables in your test2.txt file and meaning of other entries in that file? Then, if I understand the correlation between test2.txt file and ppl output, I can write some wrapper code around this that spits out the equations/inequalities in human understandable form.

I did this in the order that my own reader uses. If I remember correctly, it uses the order from the "BOUNDS" section, if provided. In your case, I recommend writing the file on your own. Then you know the order. But for production, I would not write such I file at all. I would use the API. As I said, I just did a test whether it works at all.

Concerning the other entries of the file, I just copied one example. It seems important to add a "1" as first element of each row. Didn't investigate this any further.

Best regards,
Thomas

[UserCplex]

Hi Opfer/Gawrilow,

I created a lp2polyfloat.sh file to automate the task of reading in an LP file and computing the facets "quickly" by using Floats instead of Rationals as suggested earlier in this thread. The script file content is:

However, on running this script thus:

terminalprompt> polymake --script lp2polyfloat.sh

I get the error:

Code: Select all

line 5: Can't locate object method "LATTICE_POINTS" via package "Polymake::polytope::Polytope__Float"

Could you let me know what I am doing wrong? On line 4, having Rational in place of Float does not give any error.

Also, is every occurrence of $p->LATTICE_POINTS "costly" in that is the computation of the lattice points done all over again at each place in the code where this occurs? For e.g., in the script above, I have that occurring at 3 places. Are the lattice points computed 3 times from scratch each time?

Thanks.

[gawrilow]

line 5: Can't locate object method "LATTICE_POINTS" via package "Polymake::polytope::Polytope__Float"

Could you let me know what I am doing wrong? On line 4, having Rational in place of Float does not give any error.

Help system turns out to be useful:

Code: Select all

help 'LATTICE_POINTS'; polytope/objects/Polytope/methods/Lattice points in polytopes/LATTICE_POINTS: LATTICE_POINTS() -> Matrix<Integer> Only defined for Polytope<Rational>. Returns the lattice points in bounded Polytopes.

The restriction is deliberate and justified: having imprecise coordinates, one would risk to deliver a lattice point lying outside the polyhedron, which would constitute an invalid result.

Also, is every occurrence of $p->LATTICE_POINTS "costly" in that is the computation of the lattice points done all over again at each place in the code where this occurs? For e.g., in the script above, I have that occurring at 3 places. Are the lattice points computed 3 times from scratch each time?

In general, polymake stores any computed property with the object, so that every subsequent access operation is as cheap as a lookup in a small hash table with few dozens entries. LATTICE_POINTS is a very thin wrapper function retrieving the first data member of the LATTICE_POINTS_GENERATOR property. It can safely be assumed as cheap.

[polymake_rulez44]

polymake does not use ppl in the floating-point mode yet, rather for rational numbers only. There was simply no demand for that, until you came across

So if you want to use ppl with floats, you should indeed run it standalone,as Thomas proposes. I have no idea why ppl_lcdd was not built on your machine - maybe there was a warning message about some missing dependency you've overlooked when building ppl?
Have you configured a non-standard installation location not in your PATH? Do you have permissions to write to that location? By default it's /usr/local.

That would be a great feature!

so if i run

Code: Select all

ppl_lcdd text2.txt

How can i tell ppl on this command line to use floating arithmetric?
Can i write this file format directly from polymake and read back in the output of ppl?