Solving a linear diophantine equation with lower and upper bounds on the variables

Karen Aardal, Cor Hurkens, Arjen K Lenstra

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

15 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publicationProceedings 6th International IPCO Conference, Houston TX, USA, June 22-24, 1998
EditorsRobert E Bixby, E Andrew Boyd, Roger Z Rios-Mercado
Place of PublicationBerlin
PublisherSpringer
Pages229-242
Number of pages14
ISBN (Print)3-540-64590-X
DOIs
Publication statusPublished - 1998
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume1412

Keywords

  • Convex Body
  • Diophantine Equation
  • Feasibility Problem
  • Basis Reduction
  • Initial Basis

Fingerprint Dive into the research topics of 'Solving a linear diophantine equation with lower and upper bounds on the variables'. Together they form a unique fingerprint.

Cite this