Nonlinear 0–1 programming: II. Dominance relations and algorithms |
| |
Authors: | Egon Balas Joseph B Mazzola |
| |
Institution: | (1) Carnegie-Mellon University, Pittsburgh, PA, USA;(2) University of North Carolina at Chapel Hill, NC, USA |
| |
Abstract: | A nonlinear 0–1 program can be restated as a multilinear 0–1 program, which in turn is known to be equivalent to a linear
0–1 program with generalized covering (g.c.) inequalities. In a companion paper 6] we have defined a family of linear inequalities
that contains more compact (smaller cardinality) linearizations of a multilinear 0–1 program than the one based on the g.c.
inequalities. In this paper we analyze the dominance relations between inequalities of the above family. In particular, we
give a criterion that can be checked in linear time, for deciding whether a g.c. inequality can be strengthened by extending
the cover from which it was derived. We then describe a class of algorithms based on these results and discuss our computational
experience. We conclude that the g.c. inequalities can be strengthened most of the time to an extent that increases with problem
density. In particular, the algorithm using the strengthening procedure outperforms the one using only g.c. inequalities whenever
the number of nonlinear terms per constraint exceeds about 12–15, and the difference in their performance grows with the number
of such terms.
Research supported by the National Science Foundation under grant ECS 7902506 and by the Office of Naval Research under contract
N00014-75-C-0621 NR 047-048. |
| |
Keywords: | Nonlinear 0– 1 Programming Algorithm Covering Inequalities Dominance Compact Linear Equivalent Strengthening 0– 1 Inequalities |
本文献已被 SpringerLink 等数据库收录! |
|