Linear Reformulation of Polynomial Discrete Programming for Fast Computation
Authors:
- 1 January 2017
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 29 (1) , 108-122
Abstract
Polynomial discrete programming problems are commonly faced but hard to solve. Treating the nonconvex cross-product terms is the key. State-of-the-art methods usually convert such a problem into a 0-1 mixed-integer linear programming problem and then adopt the branch-and-bound scheme to find an optimal solution. Much effort has been spent on reducing the required numbers of variables and linear constraints as well as on avoiding unbalanced branch-and-bound trees. This study presents a set of equations that linearize the discrete cross-product terms in an extremely effective manner. It is shown that embedding the proposed “equations for linearizing discrete products” into those state-of-the-art methods in the literature not only significantly reduces the required number of linear constraints from O(h3n3) to O(hn) for a cubic polynomial discrete program with n variables in h possible values but also tighten these methods with much more balanced branch-and-bound trees. Numerical experiments confirm a two-order (102-times) reduction in computational time for some randomly generated cubic polynomial discrete programming problems. There is a Video Overview associated with this article, available as supplemental material.Keywords
This publication has 21 references indexed in Scilit:
- A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment ProblemsINFORMS Journal on Computing, 2013
- Base-2 Expansions for Linearizing Products of Functions of Discrete VariablesOperations Research, 2012
- A Broader View of Designing the Liver Allocation SystemOperations Research, 2012
- Maximizing the Efficiency of the U.S. Liver Allocation System Through Region DesignManagement Science, 2010
- Global Optimization for Generalized Geometric Programs with Mixed Free-Sign VariablesOperations Research, 2009
- Exact Solutions to Task Allocation ProblemsManagement Science, 2006
- Location, Location, Location: How Network Embeddedness Affects Project Success in Open Source SystemsManagement Science, 2006
- Equivalent Formulations of Nonlinear Integer Problems for Efficient OptimizationManagement Science, 1990
- A set of geometric programming test problems and their solutionsMathematical Programming, 1976
- Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear ProgramOperations Research, 1974