A linearization method for mixed 0–1 polynomial programs

A linearization method for mixed 0–1 polynomial programs

0.00 Avg rating0 Votes
Article ID: iaor20011546
Country: United Kingdom
Volume: 27
Issue: 10
Start Page Number: 1005
End Page Number: 1016
Publication Date: Sep 2000
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: integer
Abstract:

This paper proposes a concise method for solving mixed 0–1 polynomial programming problems to obtain a global optimal solution. Given a mixed 0–1 polynomial term z = ctx1x2 … xny, where x1 x2, …, xn are 0–1 integer variables, y is a continuous variable, and ct is either a positive or a negative coefficient; we can transform z into a set of auxiliary constraints. Based on this transformation, the original mixed 0–1 polynomial program can then be solved directly by the branch-and-bound method. In addition, the proposed model for solving a mixed 0–1 polynomial problem is expressed in a much more compact way, and also uses fewer additional 0–1 variables and auxiliary constraints than the previous methods, such as those proposed by Glover, Oral–Kettani, and Li. The analytical superiority of this concise method in terms of the number of iterations and execution times can be seen, through a computational experiment conducted on a set of generated mixed 0–1 polynomial problems.

Reviews

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