Nonlinear 0-1 programming. I: Linearization techniques

From MaRDI portal





Any real function f(x) in 0-1 variables can be rewritten as a multilinear function in the same variables, i.e. \[ (*)\quad f(x)=\sum_{j\in N}a_ j(\prod_{i\in Q_ j}x_ i),\quad x_ i\in \{0,1\},\quad i\in \cup_{j\in N}Q_ j, \] where the \(a_ j\) are real numbers. Nonlinear 0-1 programs can therefore be formulated as general multilinear programs \[ (MLP)\quad \max \{f_ 0(x):\quad f_ k(x)\leq b_ k,\quad k\in K,\quad x\quad binary\}, \] where \(f_ 0\) and \(f_ k\), \(k\in K\), are multilinear functions of type (*). To solve (MLP) one frequently linearizes the problem to obtain a 0-1 linear program. The linearization proposed here uses only the original variables. Families of lower and upper bounding affine functions for the multilinear function (*) are introduced and several properties established. These results are then combined to define a family of lower bounding affine functions containing for every binary x a member, which is equal to f(x). In a second part the authors turn to inequalities of the form \[ (**)\quad f(x)\leq b,\quad where\quad f(x)\quad is\quad as\quad in\quad (*). \] A family of linear inequalities is introduced which is equivalent to (**) in the sense of having the same solution set. Moreover, it contains the well-known system of generalized covering inequalities as well as other linear equivalents of (**) of smaller cardinality.




Cited in
(44)








This page was built for publication: Nonlinear 0-1 programming. I: Linearization techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3216430)