search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
366 stars 63 forks source link

RFE: dynamic line length #80

Open msheby opened 6 months ago

msheby commented 6 months ago

Recently, https://github.com/scipopt/soplex/commit/12ef6c800ed0730f498bfcbdb262f32042b42e70 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 commented 6 months ago

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

msheby commented 6 months ago

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

leoneifler commented 6 months ago

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 commented 6 months ago

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 commented 6 months ago

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 commented 6 months ago

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!