Date: May, 2nd, 11h30
Place: ULB Bruxelles
Abstract: 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”. Thus we consider associated optimization (sub)problems (finding a “best” convex subset) and modeling problems (representing such subsets using moderate numbers of variables and linear constraints) for convex subsets of given points. 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 ofS is itself in S. In the associated optimization problem, each point has a given weight (of arbitrary sign) and we seek a convex subset with maximum (or minimum) total weight. We also seek 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).
We first review known results for the well-studied and well-understood one-dimensional case. In contrast, we also describe hardness results for dimensions three and higher. We then consider 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 review existing optimization algorithms and derive compact ideal extended formulations.
We also consider related notions of convexity in partially ordered sets and in networks and metric spaces.
