Aggregating diophantine equations

Mathews [1897] has given a theorem for aggregating two diophantine equations with positive integer coefficients into a single equation that has the same solution set as its parents over the nonnegative integers. Building on this result,Elmaghraby andWig [1970] show how to shrink the inequality constraints of a bounded variable integer program to a single constraint equation. However, such applications are limited, as we show, by a greater than exponential growth in coefficient size as successive constraints are aggregated into one. To mitigate this situation, we give new theorems and implementation procedures that provide exponential order reductions in the coefficient growth attending the aggregation process.

Mathews [1897] hat ein Theorem zur Zusammenfassung zweier diophantischer Gleichungen mit positiven ganzzahligen Koeffizienten zu einer einzigen Gleichung mit derselben Lösungsmenge wie die beiden ursprünglichen Gleichungen entwickelt. Aufbauend auf dieses Ergebnis zeigtenElmaghraby undWig [1970] eine Möglichkeit, die Ungleichungen eines ganzzahligen Optimierungsproblems mit begrenzten Variablen sukzessive auf eine einzige Gleichung zu reduzieren. Die praktische Anwendbarkeit ist jedoch begrenzt. Bei der sukzessiven Zusammenfassung der Nebenbedingungen zu einer einzigen wachsen die Koeffizienten stärker als exponentiell an. Um diesen Nachteil zu mindern, werden hier neue Theoreme und Anwendungsprozeduren entwickelt. Diese gewährleisten, daß das Anwachsen der Koeffizienten im Verlaufe des Aggregationsprozesses um einen Faktor exponentieller Ordnung geringer ist.

Authors and Affiliations

1. University of Colorado, Boulder, Colorado

   Fred Glover

2. Institute for Operations Research, Colorado School of Mines, 80401, Golden, Colorado

   Robert E. D. Woolsey

Reprints and permissions