  Mixed-Integer Linear Programming (MILP) plays an important role across a
range of scientific disciplines and within areas of strategic importance to
society. The MILP problems, however, suffer from combinatorial complexity.
Because of integer decision variables, as the problem size increases, the
number of possible solutions increases super-linearly thereby leading to a
drastic increase in the computational effort. To efficiently solve MILP
problems, a "price-based" decomposition and coordination approach is developed
to exploit 1. the super-linear reduction of complexity upon the decomposition
and 2. the geometric convergence potential inherent to Polyak's stepsizing
formula for the fastest coordination possible to obtain near-optimal solutions
in a computationally efficient manner. Unlike all previous methods to set
stepsizes heuristically by adjusting hyperparameters, the key novel way to
obtain stepsizes is purely decision-based: a novel "auxiliary" constraint
satisfaction problem is solved, from which the appropriate stepsizes are
inferred. Testing results for large-scale Generalized Assignment Problems (GAP)
demonstrate that for the majority of instances, certifiably optimal solutions
are obtained. For stochastic job-shop scheduling as well as for pharmaceutical
scheduling, computational results demonstrate the two orders of magnitude
speedup as compared to Branch-and-Cut (B&C). The new method has a major impact
on the efficient resolution of complex Mixed-Integer Programming (MIP) problems
arising within a variety of scientific fields.
