A linearization method for mixed 0-1 polynomial programs

Ching‐Ter Chang

doi:10.1016/S0305-0548(99)00071-4

A linearization method for mixed 0-1 polynomial programs

2000-09-01

39

PRE

AI

DOI：10.1016/S0305-0548(99)00071-4

Original

Original request for help

Save

Abstract

En 中文

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 = c(1)x(1)x(2)....x(n)y, where x(1), x(2),..., x(n) are 0-1 integer variables, y is a continuous variable, and c(t) 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 conduced on a set of generated mixed 0-1 polynomial problems. Scope and purpose Decision-making problems, such as facility layout,job assignment, or Communication network designs are most often formulated as mixed integer problems. To solve this form of problem, Glover transformed a binary quadratic problem with n of 0-1 variables into linear inequalities by adding 4n auxiliary constraints and n continuous variables. Oral and Kettani later proposed another linearization procedure for binary quadratic and cubic problems, which substantially improved the technique of Glover by reducing the number of auxiliary constraints. Recently, Li presented a more general linearization approach for solving mixed 0-1 polynomial problems. Compared with previous model, Li's model is more promising for use in solving practical problems. This paper shows that it is possible to further modify Li's model by reducing the number of extra variables and auxiliary constraints in the linearization process. Some test examples with various sizes of variables demonstrate that this model uses less CPU time and has fewer iterations than Li's model, while reaching the same optimal solution. (C) 2000 Elsevier Science Ltd. AIL rights reserved.

Keywords:

linearization

polynomial

mixed 0-1

A linearization method for mixed 0-1 polynomial programs

Abstract

AI Summary

Journal

Organization

Cited Papers