Binary quadratic and higher-order polynomial programs are widely studied in the optimization literature by both theoreticians and practitioners alike. Despite boasting many diverse applications in a variety of settings, these NP-hard problems remain challenging to solve even for state-of-the-art algorithms on the highest performing computers. One of the most commonly used exact solution methods for solving such problems employs an initial linearization step to transform the nonlinear program into an equivalent linear form through the introduction of auxiliary variables and constraints. The resulting linearized model, often called a 'Linearization," can then be solved using a standard mixed-integer linear programming (MILP) solver. Alternatively, if the linearization possesses a special mathematical structure, it could be optimized by a custom-designed solution algorithm.

Forrester, Richard J. Linearization Strategies for Binary Quadratic and Higher-Order Polynomial Programs. In Encyclopedia of Optimization, 3rd ed., edited by Panos M. Pardalos and Oleg A. Prokopyev, 7 pp. Cham: Springer, 2023. https://link.springer.com/referenceworkentry/10.1007/978-3-030-54621-2_833-1

Richard Forrester is a professor of Mathematics and Data Analytics at Dickinson College.

For more information on the published version, visit Springer's Website. https://link.springer.com/referencework/10.1007/978-3-030-54621-2

Citation