Premium
A cut approach to a class of quadratic integer programming problems
Author(s) -
Picard JeanClaude,
Ratliff H. Donald
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100407
Subject(s) - mathematics , integer programming , combinatorics , quadratic equation , quadratic programming , branch and cut , integer (computer science) , class (philosophy) , euclidean geometry , mathematical optimization , graph , sequence (biology) , discrete mathematics , maximum flow problem , computer science , geometry , artificial intelligence , biology , genetics , programming language
This paper presents an algorithm for solving a class of quadratic integer programming problems. These problems include discrete versions of the quadratic placement problem and the squared Euclidean distance problem. The algorithm solves a sequence of at most Σ i=1 n(u i ‐ l i ) minimum cut problems, or equivalently maximum flow problems, on a graph with n + 2 vertices where n is the number of variables in the problem, u i and l i are upper and lower bounds, respectively, on the i th variable.