An efficient linearization technique for mixed 0–1 polynomial problem

✍ Scribed by V.R. Ghezavati; M. Saidi-Mehrabad

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 252 KB
• Volume: 235
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2010.08.009

✦ Synopsis

This paper addresses a new and efficient linearization technique to solve mixed 0-1 polynomial problems to achieve a global optimal solution. Given a mixed 0-1 polynomial term z = c t x 1 x 2 . . . x n y, where x 1 , x 2 , . . . , x n are binary (0-1) variables and y is a continuous variable. Also, c t can be either a positive or a negative parameter. We transform z into a set of auxiliary constraints which are linear and can be solved by exact methods such as branch and bound algorithms. For this purpose, we will introduce a method in which the number of additional constraints is decreased significantly rather than the previous methods proposed in the literature. As is known in any operations research problem decreasing the number of constraints leads to decreasing the mathematical computations, extensively. Thus, research on the reducing number of constraints in mathematical problems in complicated situations have high priority for decision makers. In this method, each n-auxiliary constraints proposed in the last method in the literature for the linearization problem will be replaced by only 3 novel constraints. In other words, previous methods were dependent on the number of 0-1 variables and therefore, one auxiliary constraint was considered per 0-1 variable, but this method is completely independent of the number of 0-1 variables and this illustrates the high performance of this method in computation considerations. The analysis of this method illustrates the efficiency of the proposed algorithm.