LP formulation and integer solution existance

Question

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix.

We have $m$ pieces of contiguous land parcels $\{1,...,m\}$ and $n$ agents with a simple valuation function that assigns $0$ to all the subset of parcels but $S_i = \{l,l+1,l+2,...,k\}$ for which it assigns $v_i(S_i)$. We would like to find such an allocation of agents to the parcels that maximizes welfare (sum of obtained values).

Let’s define $S=\{S_1,S_2,...,S_n\}$. My try for a relaxed LP is as follows: $$\max \sum\limits_iv_i(S_i)*x_i\\ s.t.\\ x_i\leq 1 \ \forall i\\ \sum\limits_{x_i: S_i\in T} x_i\leq 1\ \forall T\subseteq S: \cap T \neq \emptyset, T \textrm{ is maximal}\\ x_i\geq 0$$

First off, is it the correct formualtion? I add the second constraint to mean „for each set of agents with contiguous set of parcels that share at least one parcel, and which is a maximal set with that property, only one agent at most can get its desired plot of land”. In other words, I sum $x_i$’s of those agents who chose their subset of lands sharing at least one plot. I do not want repetetiveness so I only take maximal amount of agents with that property each time. The other constraints are just relaxed constraint in $x_i$ which means that either agent $i$ gets his desired set or not.

Secondly, I do not really see why would constraint matrix be totally unimodular. It will have an identity matrix in is upper part and sth that cannot be specified in general in its bottim part. Perhaps there’s some simpler LP formulation that I haven’t thought of? I must add I did not leverage the form of the sets valued by the agents anywhere, so it can be that I am missing something.

I kindly ask for your help.

Example: We have $3$ plots of land $\{1,2,3\}$ and $3$ agents with valuations $v_1(\{1,2\})=2$, $v_2(\{2,3\})=3$, $v_3(\{3\})=2$, so $S_1=\{1,2\}$, $S_2=\{2,3\}$, $S_3=\{3\}$. Then the corresponding LP is $$\max v_1(S_1)*x_1 + v_2(S_2)*x_2 + v_3(S_3)*x_3\\ s.t.\\ x_i\leq 1 \ \forall i\\ x_1 + x_2 \leq 1\\ x_2 + x_3 \leq 1\\ x_i\geq 0$$ The contraints mean that "at most one from $S_1$ and $S_2$ can be chosen and at most one from $S_2$ and $S_3$".

Answer 1

I don't know why you added this in your second constraint:

..., and which is a maximal set with that property, ...

I would model it simply as: "For every two agents $x_i$ and $x_j$, if their sets $S_i$ and $S_j$ intersect, then $x_i + x_j \leq 1$" $$ x_i + x_j \leq 1 \quad \forall (i,j): i \lt j \text{ and } S_i \cap S_j \neq \emptyset$$

Notice that every row in the constraint matrix has exactly two ones, and we can think of it as a bipartite graph, which is TUM.

This matrix is not TUM, and there is no guarantee that it will provide Integer Solutions, as we can see in the counter-example: $$ S_1 \cap S_2 \neq \emptyset, S_1 \cap S_3 \neq \emptyset, S_2 \cap S_3 \neq \emptyset $$ \begin{bmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1\\ \end{bmatrix}

That doesn't mean that your problem does not have an integer optimal solution, simply that this Linear Formulation will not always yield an integer solution. For example, the solution of your LP might be $x_1 = 0.23848$, which satisfies all the constraints and is the optimal solution, but it is not integer.

If your goal is to solve this problem, and get the Integer Optimal Solution, you can use an Integer Linear Formulation and use any ILP solver to get to that solution.

The Integer Linear Formulation allows constraints like $ x_1 \in \{0, 1\}$, that will ensure that this variable will be either 0 or 1.

The purpose of proving that it is TUM, is to avoid using Integer Linear Formulations, since they are slower to solve than Linear Programs.