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 of S 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).

In the first lecture we review known results for the well-studied and well understood one-dimensional case, for which we present some simple new proofs. In contrast, we also describe hardness results for dimensions three and higher.

In the second lecture we 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.