Reformulating nonlinear combinatorial optimization problems for higher computational efficiency

Reformulating nonlinear combinatorial optimization problems for higher computational efficiency

0.00 Avg rating0 Votes
Article ID: iaor1996575
Country: Netherlands
Volume: 58
Issue: 2
Start Page Number: 236
End Page Number: 249
Publication Date: Apr 1992
Journal: European Journal of Operational Research
Authors: ,
Abstract:

It is important to develop computationally efficient algorithms to solve combinatorial optimization problems. Equally important, if not more so, is to find a way to reformulate the original combinatorial optimization problem, provided this is possible, so that the resulting equivalent problem can be solved easily and efficiently using commercially available codes. This paper proposes an equivalent formulation to deal basically with the linearization of nonlinear expressions in 0-1 variables. The equivalent formulation technique proposed in this paper linearizes a binary quadratic integer problem of n variables by introducing only n new linear constraints, whereas the most economical method in the literature requires the addition of 2n of such constraints. The same technique is extended to linearize the binary cubic expression of n variables, this time requiring the addition of at most 3n auxiliary linear constraints and 3n continuous variables. Also discussed in the paper is the computational superiority of the proposed method over the existing ones in the literature through a series of randomly generaged test problems.

Reviews

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