Polyhedral Basis, Probability Spaces, and Links to Disjunctive Programming

Mohit Tawarmalani

Purdue University Economics Working Papers from Purdue University, Department of Economics

Abstract: Motivated by our earlier study of convex extensions [25], we define a polyhedral basis over a convex set. We explore properties of polyhedral functions that lead us into studying their relations to convexification and disjunctive programming. In particular, we show that a polyhedral basis is easy to identify for Cartesian products of simplices. A special case, that of an n-dimensional hypercube, is of particular interest in this study. In this case, we show that convex and concave envelopes of multilinear sets are derived as a consequence of disjunctive programming and Reformulation Linearization Techniques. We answer in negative an open question whether there exist polynomial functions that will provide convexification processes for general integer programs just as multilinear functions are used to convexify 0-1 programs in the reformulation linearization technique and the lift and project algorithm. The polyhedral functions also correspond to nonlinear rounding ideas and we will explore these in the article. This interpretation allows us to study probabilistic mathematical programs and explore their relation to multilinear programs. More concretely, we demonstrate that a probabilistic mathematical program is equivalent to the lagrangian relaxation of a multilinear program. Consequently, we study approximation schemes and demonstrate that rounding schemes often hint at polyhedral basis functions. Some negative results about Lagrangian relaxation are presented. This is a preliminary set of proofs and provides many directions for further work in convexification techniques. Some of the results that follow easily are stated without proofs.

Pages: 29 pages
Date: 2002
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pur:prukra:1157

Access Statistics for this paper

More papers in Purdue University Economics Working Papers from Purdue University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Business PHD ().