Representability of functions
type: Item
instance of: scholarly article
title: Representability of functions
zbMATH Open document ID: 0684.90066
DOI: 10.1016/0166-218X(89)90023-1
author: Robert G. Jeroslow
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: This paper is a continuation of an earlier paper of the author [ibid. 17, 223-243 (1987; Zbl 0618.90069)]. A set \(S\leq R^ K\) is called bounded MIP representable (B-MIP.R) if there is a linear transformation F(x,y) together with a subset \(K\subseteq \{1,...,n\}\) of the set of indices of the auxiliary variables \(y=(y_ 1,...,y_ n)\) and a vector \(b\in R^ m\) for which the following holds: \[ (1)\quad x\in S\quad \Leftrightarrow \quad there\quad exists\quad y\quad with\quad y_ k\in \{0,1\}\quad for\quad k\in K,\quad and\quad F(x,y)\leq b. \] When (1) holds, the triple (F,K,b) is called a representation of S. When \(K=\emptyset\) in (1), the representation is called ``simple''. Three kinds of representability: min-, max-, and constraint-representability are defined: 1. A function F is min-B-MIP.R if its epigraph \(EPI(F)=\{(r,x)|\) \(r\geq F(x)\}\) is B-MIP.R. 2. F is max-B-MIP.R if its hypograph \(HYPO(F)=\{(r,x)|\) \(r\leq F(x)\}\) is B.MIP.R. 3. F is constraint-B-MIP.R if its graph \(GPH(F)=\{(r,x)|\) \(r=F(x)\}\) is B-MIP.R. The main characterization results for constraint-B-MIP.R functions are: Theorem 3.1. A min- or max-B-MIP representable function F, with a bounded domain, is constraint-B-MIP-representable iff F is continuous on its domain.
Mathematics Subject Classification ID: 90C11
zbMATH DE Number: 4121757
zbMATH Keywords: representability
reviewed by: Oleg A. Shcherbina
MaRDI profile type: Publication
cites work: Q4120330
cites work: Disjunctive programming: Properties of the convex hull of feasible points
cites work: Disjunctive Programming
cites work: Branch and Bound Methods for Mathematical Programming Systems
cites work: Q4187595
cites work: Q3294638
cites work: Q3844775
cites work: Discrete-Variable Extremum Problems
cites work: New results on equivalent integer programming formulations
cites work: Polyhedral annexation in mixed integer and combinatorial programming
cites work: ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
cites work: Integer programming formulation of combinatorial optimization problems
cites work: Q4132247
cites work: Representations of unbounded optimization problems as integer programs
cites work: Representability in mixed integer programming. I: Characterization results
cites work: Modelling with integer variables
cites work: Experimental Results on the New Techniques for Integer Programming Formulations
cites work: On the existence of optimal solutions to integer and mixed-integer programming problems
cites work: Integer and mixed-integer programming models: General properties
cites work: Mixed integer minimization models for piecewise-linear functions of a single variable
cites work: A theoretical and computational comparison of “equivalent” mixed-integer formulations
cites work: Rational Mixed-Integer and Polyhedral Union Minimization Models
cites work: Q5638112
cites work: Q5603731
cites work: Q4124606
cites work: Q3347628
cites work: Hypercylindrically Deduced Cuts in Zero-One Integer Programs
Wikidata QID: Q126382764
full work available at URL: 0166-218x(89)90023-1
OpenAlex ID: W2078053321
Recommended article: Modelling with integer variables
Recommended article: Representability in mixed integer programming. I: Characterization results
Recommended article: Characterizations of mixed binary convex quadratic representable sets
Recommended article: Mixed-Integer Convex Representability
Recommended article: Minimal representation of convex regions defined by analytic functions
Recommended article: Convex separable minimization subject to bounded variables
Recommended article: Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions?
Recommended article: A new approach to optimization under monotonic constraint
Recommended article: Optimization problems for convex functions
Recommended article: Obtaining an approximate solution of a maximin with connected variables and of a multiple maximin
description: scientific article; zbMATH DE number 4121757