0
$\begingroup$

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$".

$\endgroup$
  • 1
    $\begingroup$ Hi, just wanted to point out that for an integer solution to exist, a totally unimodular (TUM) constraint matrix is not always necessary. A TUM is required iff you need integer solution for all integer RHS of constraint matrices on any linear objective. $\endgroup$ – csTheoryBeginner Nov 30 '17 at 16:28
  • $\begingroup$ I was not aware of that, thank you. Nonetheless I would still like to prove it’s totally unimodular. $\endgroup$ – Jules Nov 30 '17 at 16:30
  • $\begingroup$ Also, I am unable to understand what the constraint in your problem is. Could you please edit your question describing more clearly what the constraint is? $\endgroup$ – csTheoryBeginner Nov 30 '17 at 17:21
  • $\begingroup$ I tried to clarify that, I hope it makes more sense now. Nonetheless, I am still unable to use the special form of $S_i$’s to use in LP formulation. $\endgroup$ – Jules Dec 1 '17 at 5:09
  • 1
    $\begingroup$ @Jules-: I agree, my previous argument is not accurate. It was just meant to show you a direction to argue for a proof in case TUM is not the way to go forward. However, is it correct what you want to show is the LP solution is integral? Okay something that might help you to show TUM is, suppose you have a constraint matrix $Ax \leq b , x\geq 0 , x\leq 1$, then further suppose you have atmost two non zeros in each column of $A$, then $Ax \leq b , x\geq 0 , x\leq 1$ is TUM iff $A$ admits an equitable row bi-coloring. You should be able to find the definition equitable bi-coloring online. $\endgroup$ – csTheoryBeginner Dec 2 '17 at 2:48
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought of that too but couldn't prove that this resulting matrix is a TUM as well. Good to know that's a well-known case! $\endgroup$ – Jules Dec 5 '17 at 3:05
  • $\begingroup$ Though what about this matrix: $\begin{bmatrix} 1 & 1 & 0 & \\ 1 & 0 & 1 & \\ 0 & 1 & 1 \end{bmatrix}$. It has two ones in each row, we can get it by having three agents with, say, the same preferred sets but it won't be TUM. $\endgroup$ – Jules Dec 5 '17 at 3:22
  • $\begingroup$ You are right, it is not TUM. I made a mistake by stating that it is a bipartite graph, which is not. So your formulation is not TUM. $\endgroup$ – klaus Dec 5 '17 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.