Many planning and location problems in forestry, mining, political districting, farmland consolidation, as well as in data mining, entail the selection of a subset, or a partition into subsets, that should satisfy some, often ill-specified, shape constraints. A typical such shape constraint is that the subsets be convex, or “approximately convex”. In general terms, a subset S of a given (finite) set of points in a convexity structure is convex if every given point that is in the convex hull of S is itself in S. We are interested in modeling such convexity restrictions when the given set of points is finite, i.e., in polyhedral descriptions of the characteristic vectors of convex subsets, and extended formulations that are compact (i.e., polynomial-sized) and if possible ideal (i.e., with integer extreme solutions). This in turn leads us to considering the associated optimization problem, where each point has a given weight (of arbitrary sign) and we seek a convex subset with maximum (or minimum) total weight. In many applications, these restrictions and optimization problem arise in a low-dimensional space and are subject to additional constraints.
Modeling convex subset restrictions is well understood for the standard (vector space) convexity in the one-dimensional case. On the other hand, the optimization problem is NP-hard for the standard convexity in dimensions three and higher, and hard to approximate when the dimension is part of the input. For the two-dimensional (planar) case, convexity can be enforced by a polynomial (quartic) number of linear inequalities in the natural binary variables, but the resulting formulation is very weak. We present a compact ideal extended formulation, derived from the cubic-time dynamic programming optimization algorithm of Eppstein et al. (1992) and Bautista-Santiago et al. (2011). We point out open questions on finding more compact and/or tighter formulations, as well as exact or approximate combinatorial separation and optimization algorithms. We also consider related notions of convexity in partially ordered sets and in networks and metric spaces.
(This talk presents joint work with numerous co-authors in Chile and elsewhere.)
