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?
1 Answer 1
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.
-
$\begingroup$ would you also know mathoverflow.net/questions/282456/…? $\endgroup$Turbo– Turbo2017年10月02日 03:08:22 +00:00Commented Oct 2, 2017 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– kbala2017年10月13日 18:14:12 +00:00Commented Oct 13, 2017 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$Turbo– Turbo2018年02月12日 08:45:26 +00:00Commented Feb 12, 2018 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$Turbo– Turbo2018年03月17日 23:17:37 +00:00Commented Mar 17, 2018 at 23:17
Explore related questions
See similar questions with these tags.