Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?


The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.

Lovasz and Scarf proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was reported in 1993 by Cook, Rutherford, Scarf, and Shallcross (this paper is available in ResearchGate).

One of the key steps in Lenstra's algorithm uses basis reduction (BR) to locate "thin directions" for the polytope. Branching on such a direction produces only a small (i.e., polynomial number) of subproblems. In a series of papers, Aardal and coauthors essentially applied this BR step to help solve (using standard MIP solvers) otherwise hard-to-solve IP instances (see, e.g., this paper and this paper). We (also see arXiv) have studied a similar, but arguably simpler and more general, approach (full disclosure: self-citation here!) to solve IP feasibility problems: apply BR to the constraint matrix $A$ of the IP feasibility problem (of the form $\{\mathbf{l} \leq A \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}$), and use standard techniques to solve the resulting reformulated IP feasibility problem. The BR could be performed using standard software tools such as NTL.

| cite | improve this answer | |
  • $\begingroup$ would you also know mathoverflow.net/questions/282456/…? $\endgroup$ – 1.. Oct 2 '17 at 3:08
  • $\begingroup$ I must mention that while Lenstra-type algos might not be implemented in their original form, Barvinok's lattice-point counting algo (improvements of the same) has indeed been implemented - see math.ucdavis.edu/~latte $\endgroup$ – kbala Oct 13 '17 at 18:14
  • $\begingroup$ this also looks like sufficient correct? if we know how to count can't we use binary search and is there such a binary search algorithm? $\endgroup$ – 1.. Feb 12 '18 at 8:45
  • $\begingroup$ what is the complexity of Lovasz/Scarf. Is there any open source software available for any implementation of fixed fimension poly time integer programming algorithm? $\endgroup$ – 1.. Mar 17 '18 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.