Nonlinear 0-1 programming. I: Linearization techniques
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.
- Nonlinear 0-1 programming. II: Dominance relations and algorithms
- scientific article; zbMATH DE number 4081288
- Multilinear programming: Duality theories
- Generalized bilinear programming. I: Models, applications and linear programming relaxation
- A representation of the set of feasible objectives in multiple objective linear programs
- Cardinality constrained multilinear sets
- On optimization over the efficient set of a multiple objective linear programming problem
- A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints
- scientific article; zbMATH DE number 3858869
- Heuristic methods for linear multiplicative programming
- A Balasian-Based Algorithm for Zero-One Polynomial Programming
- A duality theorem and an algorithm for (mixed-) integer nonlinear programming
- Covering Relaxation for Positive 0-1 Polynomial Programs
- Duality in Discrete Programming: II. The Quadratic Case
- Facets of the knapsack polytope
- scientific article; zbMATH DE number 3152649 (Why is no real title available?)
- scientific article; zbMATH DE number 3540635 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- scientific article; zbMATH DE number 3310598 (Why is no real title available?)
- L’algebre de Boole et ses applications en recherche operationnelle
- Methods of Nonlinear 0-1 Programming
- Nonlinear 0-1 programming. II: Dominance relations and algorithms
- Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
- Technical Note—Generalized Covering Relaxation for 0-1 Programs
- The Generalized Lattice-Point Problem
- Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Experiments in quadratic 0-1 programming
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Lagrangean decomposition for integer nonlinear programming with linear constraints
- A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
- Unconstrained 0-1 nonlinear programming: A nondifferentiable approach
- A survey of algorithms for the generalized assignment problem
- Combinatorial optimization models for production scheduling in automated manufacturing systems
- An enumerative algorithm framework for a class of nonlinear integer programming problems
- A constrained nonlinear 0-1 program for data allocation
- Strong valid inequalities for Boolean logical pattern generation
- Compact linearization for binary quadratic problems subject to assignment constraints
- Two new reformulation convexification based hierarchies for 0-1 MIPs
- Robust metaheuristic algorithm for redundancy optimization in large-scale complex systems
- A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
- Explicit convex and concave envelopes through polyhedral subdivisions
- Berge-acyclic multilinear 0-1 optimization problems
- Matroid optimization problems with monotone monomials in the objective
- Graph, clique and facet of Boolean logical polytope
- A multi-term, polyhedral relaxation of a 0-1 multilinear function for Boolean logical pattern generation
- The basic algorithm for pseudo-Boolean programming revisited
- Linear forms of nonlinear expressions: new insights on old ideas
- Continuous dynamical systems that realize discrete optimization on the hypercube
- An algorithm for indefinite integer quadratic programming
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- A polytope for a product of real linear functions in 0/1 variables
- Maximizing the Product of Two Linear Functions In 0-1 Variables
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Nonlinear 0-1 programming. II: Dominance relations and algorithms
- Nonlinear one-parametric bottleneck linear programming
- scientific article; zbMATH DE number 4008098 (Why is no real title available?)
- Roof duality for polynomial 0–1 optimization
- State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- A revised Taha's algorithm for polynomial 0-1 programming
- A branch and bound algorithm for designing reliable systems at a minimum cost
- Concave extensions for nonlinear 0-1 maximization problems
- \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation
- Projection, lifting and extended formulation integer and combinatorial optimization
- ``Miniaturized linearizations for quadratic 0/1 problems
- Polyhedral analysis for concentrator location problems
- Upper-bounds for quadratic 0-1 maximization
- Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method
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)