@inproceedings{3e55969abfa04b2288279c9029ce5027,

title = "Solving a linear diophantine equation with lower and upper bounds on the variables",

abstract = "We develop an algorithm for solving a linear diophantine equation with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction, and first finds short vectors satisfying the diophantine equation. The next step is to branch on linear combi- nations of these 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 linear dio- phantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good result on real-life data.",

keywords = "Convex Body, Diophantine Equation, Feasibility Problem, Basis Reduction, Initial Basis",

author = "Karen Aardal and Cor Hurkens and Lenstra, {Arjen K}",

year = "1998",

doi = "10.1007/3-540-69346-7_18",

language = "English",

isbn = "3-540-64590-X",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "229--242",

editor = "Bixby, {Robert E} and Boyd, {E Andrew} and Rios-Mercado, {Roger Z}",

booktitle = "Integer Programming and Combinatorial Optimization",

}