0
$\begingroup$

I am wondering if this Integer Linear Programming model I came up with as an exercise for my algorithms class is correct.

The Problem

Given a graph $G=(V, E)$, with a set of weights $W = \{w_{ij} \ge 0 | \forall (i,j) \in E\}$ find a set of vertices $U$ and a set of edges $\delta(U)$ such that $\forall (i,j) \in \delta(U), i \in U, j \notin U$ and $\sum_{(i,j) \in U}w_{ij}$ is maximum.

My model $$\max \sum_{(i,j) \in E} d_{ij} w_{ij}$$

Subject to

$$d_{ij} - u_i + u_j \ge 0, \forall(i,j) \in E$$ $$u_i+u_j \le 1, \forall (i,j) \in E$$ $$u_i, u_j, d_{ij} = \{0,1\}$$

Variables

$d_{ij} = 1 \text{ if } (i,j) \in \delta(U), 0 \text{ otherwise.}$

$u_i = 1 \text{ if } i \in U, 0 \text{ otherwise.}$

Line of thought

The second restriction say that I may choose a single extremity of each edge to go into $U$ because if $(i,j) \in \delta(U), i \in U, j \notin U$, but I can also choose none of them in case $(i,j) \notin \delta(U)$

The first restriction implies that if I choose $d_{ij} = 1$ either $u_i = 1$ or $u_j = 1$ (but not both because of the second restriction), but I could set $d_{ij}=1$ and let the other two variables be 0 and I still satisfy the restriction, so I guess I am missing a restriction to force at least one of the extremities to be chosen, I just can't find a way to write using the variables I defined.

Question

Would be changing the second restriction to $u_i + u_j = 1$ solve this? What are other ways to writes this problem as ILP?

$\endgroup$
  • $\begingroup$ The way to know whether your proposed solution is correct is to prove it correct. It can also be useful to work through some small examples (pick a small problem instance, find the optimal solution, write down your LP for that graph, and check whether the LP gives the right answer). We discourage "is my answer correct?" questions as they're usually not interesting to others. As far as other ways to write this as an ILP, any problem in NP can be expressed as an ILP (see e.g., cs.stackexchange.com/q/12102/755 for how to do that in a mostly mechanical way). $\endgroup$ – D.W. Apr 16 at 19:59

Your Answer

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

Browse other questions tagged or ask your own question.