## Nonlinear Optimization for Matroid Intersection and Extensions

##### View/Open

##### Date

2008-03-17##### MFO Scientific Program

Research in Pairs 2007##### Series

Oberwolfach Preprints;2008,14##### Author

Berstein, Yael

Lee, Jon

Onn, Shmuel

Weismantel, Robert

##### Metadata

Show full item record##### OWP-2008-14

##### Abstract

We address optimization of nonlinear functions of the form $f(W_x)$ , where $f : \mathbb{R}^d \to \mathbb{R}$ is a
nonlinear function, $W$ is a $d \times n$ matrix, and feasible $x$ are in some large finite set $\mathcal{F}$ of integer points in $\mathbb{R}^n$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking
at broad natural classes of $f$, $W$ and $ \mathcal{F}$.
One of our main motivations is multi-objective discrete optimization, where $f$ trades off the linear functions given by the rows of $W$ . Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures.
We assume that the convex hull of $\mathcal{F}$ is well-described by linear inequalities (i.e., we have an efficient separation oracle). For example, the set of characteristic vectors of common bases of a pair of matroids on a common ground set satisfies this property for $\mathcal{F}$. In this setting, the problem is already known to
be intractable (even for a single matroid), for general $f$ (given by a comparison oracle), for (i) $d = 1$ and binary-encoded $W$, and for (ii) $d = n$ and $W = I$.