On integer programs with irrational data

Abstract An integer program (IP) with a finite number of feasible solutions may have an unbounded continuous relaxation if it contains irrational parameters, due to implicit constraints induced by those irrational numbers. For IPs with polynomial constraints, we show that these implicit constraints can be derived explicitly when the irrational parameters belong to an extension field of the rational numbers by roots of integers, leading to a rational reformulation. We also present a weaker result for IPs involving the broader class of algebraic irrational numbers, which extends to IPs containing a particular form of transcendental numbers.