Properties of the value function generated by an integer progamming problem

67 Views Asked by At

Consider the following linear programming problem

max $w^\top x$ s.t.

$Ax\leq b, \,\,0\leq x\leq 1$,

where $x\in R^E, w \in\{0,1\}^E$, $A$ is a $\{0,\pm 1\}$ matrix and $b$ is a vector. Further assume that $A$ is totally unimodular, i.e., every nonsingular square submatrix has determinant -1 or 1.

Define a set function $f: 2^E\to R$ as follows: for every $U\subseteq E$,

$f(U):=max \{\chi^U x | Ax\leq b, 0\leq x\leq 1\}$.

where $\chi^U$ is the incidence vector of $U$.

My question is what combinatorial properties (i.e., submodularity) would function $f$ have? Is there any literature that discusses this problem? Thanks.