Solving a system of linear diophantine equations with lower and upper bounds on the variables

• 成果类型: Article
• 署名作者: Aardal, K; Hurkens, CAJ; Lenstra, AK
• 署名单位: Utrecht University; Eindhoven University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.25.3.427.12219
• 发表日期: 2000
• 页码: 427-442
• 关键词: subset sum problems; basis reduction; lattice

摘要

We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first rinds a short vector satisfying the system of diophantine equations, and a set of Vectors belonging to the null-space of the constraint matrix. Due to basis reduction, all these vectors are relatively short. The next step is to branch on linear combinations of the null-space vectors, which either yields a vector that satisfies the bound constraints or provides a proof that no such Vector exists. The research was motivated by the need for solving constrained diophantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good results on real-life data, and on instances from the literature.