Integer linear programming heuristics that exploit a relationship between computational complexity and bandwidth
Loren K. Platzman, Jane C. Ammons, John J. Bartholdi · 1985
We consider problems of choosing an n-vector x, whose entries must be integers, to optimize a linear objective subject to m linear constraints. For example, the "selection problem" is to choose some subset from among n discrete alternatives so that requirements are satisfied at least cost. Such problems are known to be NP-hard. In this paper, we exploit the concept of bandwidth to explain in a novel way why integer linear programming is difficult. The main contribution is a heuristic based on these ideas. It requires computational effort exponential in m but nearly linear in n, and may be run to any desired prespecified accuracy.