2

I'm looking for advice on solving ILP problems with a relatively small number of constraints and variables, but very large coefficients. I have less than 500 variables and constraints, but my coefficients are all greater than 1000 bits. I'm concerned about numerical stability issues for the solver when dealing with such large coefficients.

My problem has purely linear constraints and I am trying to minimize a linear objective. The problem domain is cryptanalysis. The constraint matrix is extremely dense.

Are there any solvers in particular that excel in this domain? Are there particular settings or algorithms I should use to prevent numerical stability issues?

I would also be interested in LP solvers that can handle huge coefficients if the support is better there, as I can likely use rounding to obtain a pretty good solution for the ILP from a solution to the LP.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Elliot Gorokhovsky
  • 123
  • 4

2 Answers2

1

Classical MILP solvers work with floating-point numbers. Therefore, if you need more accuracy than what a double might store, they won't fit. Otherwise, what is important first for numerical stability is the range of the coefficients. So if you can scale your coefficients to fit in $[10^{-4}, 10^4]$, numerical stability might not be an issue.

For problems with numerical issues, some solvers provide dedicated options to mitigate them. For example:

If this is not enough, then you will need a truly exact MILP solver such as the ones mentioned in this question

fontanf
  • 2,623
  • 6
  • 11
1

If you can make it work with $10^{-6}$ or $10^{-8}$ relative precision, just use an off-the-shelf solver with more precision-oriented options. You will need to rescale your problem so that the coefficients are "reasonable" for the solver ($10^{10}$ should be safe-ish).

You mention cryptanalysis, so I'm assuming from now that you actually need an exact solution. If you need a solution with 1000 bits of accuracy, the accuracy of a typical solver is not going to be sufficienthis doesn't even fit in a floating-point number.

Depending on your use case, you need one of the following:

  • For continuous or mixed integer problem, an exact linear solver as mentioned by the other answer, such as GLPK in exact mode or QSOPT_ex.
  • For pure binary or integer problems, a pseudoboolean solver such as Minisat+ or RoundingSat may be a better choice. They are more similar to SAT solvers, and would probably give better results than a MIP solver for anything related to cryptanalysis.
Ggouvine
  • 1,877
  • 7
  • 13