Surrogate Level-Based Lagrangian Relaxation for mixed-integer linear programming

doi:10.1038/s41598-022-26264-1

Return

Surrogate Level-Based Lagrangian Relaxation for mixed-integer linear programming

2022-12-27

Mikhail A. Bragin *

Emily L. Tucker

DOI：10.1038/s41598-022-26264-1

Original

Save

View PDF

Abstract

En 中文

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 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. The new method has a major impact on the efficient resolution of complex Mixed-Integer Programming problems arising within a variety of scientific fields.

Keywords:

SCHEDULING PROBLEMS

SHOP

OPTIMIZATION

CONVERGENCE

STRATEGIES

ALGORITHM

MODEL

AGE

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.