RFE: dynamic line length

[msheby]

Recently, scipopt/soplex@12ef6c8 gave SoPlex the ability to read LP files with arbitrarily long lines; could the same functionality be ported to (the exact-rational branch of) SCIP?

[leoneifler]

As far as I can see, this should already be possible. Can you send me an LP file that exact SCIP cannot read?

[msheby]

Sure -- I'll have to upload it somewhere; it's massive.

[leoneifler]

So I looked at your instance, and the issue is not the line length but rather the length of the individual numbers. The LP file reader has a maximum length of 65536 for a single number (which to be fair is called MAX_LINELEN - no idea why). The first rational where this was not enough had an encoding length of 161587 (although it was between 0 and 1)

It is of course possible to change this, but I have to caution you that your instance will almost certainly not be able to be solved with these enormous fractions unless you have a lot of time and almost unlimited memory. May I ask where this instance comes from and if this incredible amount of precision is really necessary? Because if it is, then I would be happy to help try to make this work somehow, I just never thought something like this would come up in practice.

[msheby]

I built a system that represents the game tree of the Royal Game of Ur; minimal subgraphs are generated and passed to scip to solve. The game's win probabilities have already been approximated; I'm looking to see if the tooling exists to permit one to solve the game exactly.

[leoneifler]

I see, and I am guessing these insanely long numbers result from multiplying a bunch of different win probabilities that were computed earlier in the process? I can change the code of the LP file reader to allow numbers of any encoding length, but I have to admit that I am not especially hopeful that SCIP will be able to solve this. I will ping you when I have a patch that you can try.

If you can see any modelling tricks to avoid having these huge numbers everywhere, that would definitely be a plus 😅 .

[msheby]

I see, and I am guessing these insanely long numbers result from multiplying a bunch of different win probabilities that were computed earlier in the process?

Exactly!

[magneticflux-]

I just ran into this too, I have a massive array of ~180k variables generated in the MiniZinc flattening process and so they had names like X_INTRODUCED_10324_. Doing a quick sed 's/X_INTRODUCED_/qq_/g' model.fzn on the output let me work around the limitation.

The error I ran into looked like:

[reader_fzn.c:668] ERROR: Syntax error in line 643264: expected token <]> found <RODUCED_7349_>
[reader_fzn.c:669] ERROR:   input: RODUCED_7349_,X_INTRODUCED_7348_,X_INTRODUCED_7347_, [...]

[tons of variables]

[reader_fzn.c:668] ERROR: Syntax error in line 643264: expected variable name or constant found <X_INT>
[reader_fzn.c:669] ERROR:   input: RODUCED_7349_,X_INTRODUCED_7348_, [...]

[tons of variables]

Of note, the exact length of the replacement is important: replacing it with q_ instead of qq_ gave a similar error when parsing ran out of text mid-variable and got confused, just at a different spot. I'm using SCIP version 9.1.0, and it seems like the code to re-allocate the buffer does not handle all cases correctly: 13a5fda

[svigerske]

@magneticflux- I think that's a different issue. Can you provide the model.fzn that reproduces this? And which operating system are you using? (We currently look into some issue where fzn/opb files are not written correctly on windows only.)

[magneticflux-]

Sorry, I didn't realize previous discussion was about LP files rather than FZN files!

Here's the FlatZinc, unzipped is 57MB: model.zip
It's generated from a MiniZinc which was generated from external data so there are some redundant or odd-looking constraints, but they get eliminated by presolve. The main structure is a covering-like problem that ends up selecting ~50 out of 20,000 possibilities after all the dependencies between selections shake out, and I've found Google's CP-SAT handles it well (but I'm experimenting with alternatives).

I'm using Linux and building SCIP v9.1.0 from source using https://github.com/Lichthagel/scipopt-nix:

SCIP version 9.1.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 7.1.0] [GitHash: 8cab027-dirty]
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  Soplex 7.1.0         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 595bfac-]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.3.1           General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.3.0            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.6.1          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 690e9e7      AMPL .nl file reader library (github.com/ampl/mp)
  PaPILO 2.3.0         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB)
  Nauty 2.8.8          Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)
  sassy 1.1            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)
  Ipopt 3.14.16        Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

Compiler: gcc 13.3.0

Build options:
 ARCH=x86_64
 OSTYPE=Linux-6.9.11
 COMP=GNU 13.3.0
 BUILD=Release
 DEBUGSOL=OFF
 EXPRINT=cppad
 SYM=snauty
 GMP=ON
 IPOPT=ON
 WORHP=OFF
 LPS=spx
 LPSCHECK=OFF
 NOBLKBUFMEM=OFF
 NOBLKMEM=OFF
 NOBUFMEM=OFF
 THREADSAFE=ON
 READLINE=ON
 SANITIZE_ADDRESS=OFF
 SANITIZE_MEMORY=OFF
 SANITIZE_UNDEFINED=OFF
 SANITIZE_THREAD=OFF
 SHARED=ON
 VERSION=9.1.0.0
 API_VERSION=115
 ZIMPL=ON
 ZLIB=ON

Edit:
I adjusted some reified constraints to simplify the flattening and presolve and I got a slightly smaller result, but it still triggers the line-length issue: model_2.zip

[svigerske]

The problem seems to be the long int_lin_eq() line. Here is a small instance to reproduce this:
model_2a.fzn.gz

[svigerske]

Here is a patch for the FlatZinc reader that should help on model_2.zip. It was a matter of reallocating sufficiently often:

diff --git a/src/scip/reader_fzn.c b/src/scip/reader_fzn.c
index d7b6b5f453..75aac20c6f 100644
--- a/src/scip/reader_fzn.c
+++ b/src/scip/reader_fzn.c
@@ -448,7 +448,7 @@ SCIP_Bool getNextLine(
 
    fzninput->linenumber++;
 
-   if( fzninput->linebuf[fzninput->linebufsize - 2] != '\0' )
+   while( fzninput->linebuf[fzninput->linebufsize - 2] != '\0' )
    {
       int newsize;

[svigerske]

Regarding the original issue, I'm not sure that @leoneifler is still looking into this. Maybe he can give us an update whether the patch he mentioned in #80 (comment) is still planned to happen, or we should just close this issue as a won't-fix.