Linear Reformulation of Polynomial Discrete Programming for Fast Computation

Linear Reformulation of Polynomial Discrete Programming for Fast Computation

0.00 Avg rating0 Votes
Article ID: iaor2017286
Volume: 29
Issue: 1
Start Page Number: 108
End Page Number: 122
Publication Date: Feb 2017
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: heuristics
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(h 3 n 3) 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.

Reviews

Required fields are marked *. Your email address will not be published.