Integer Programming Via Modular Representations

Modular representations of the integers are used to identify the successive integer grid points encountered as one varies the objective value of an all-integer programming problem. One can, therefore, proceed from a noninteger solution to an integer solution by monotonic variation of the objective value. Ordinarily, it is necessary to perturb the objective function of a problem to fit the prescribed format for the algorithm: although this is easily done for small problems, the limited number of digits carried by most computing machines prevents it for problems with many variables. The features of the algorithm are virtually independent of the number and the linearity (or nonlinearity) of the constraints, provided the variables are constrained to be nonnegative and bounded above.

• 저널Management Science · 16(5) · 289–294
• 토픽Constraint Satisfaction and Optimization · Computer Networks and Communications
• DOI10.1287/mnsc.16.5.289
• 저자Robert Wilson