Representability of functions (Q1825755): Difference between revisions

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.