1
$\begingroup$

I am solving a problem where I have a complete undirected graph with weights on the nodes and on the edges. The weight on the node represents a profit that you obtain if you select that node. The weight on the edge $(i,j)$ represent the distance to go from the node $i$ to node $j$.

The problem is to select a subset of nodes that maximize the profit, such that the distance traveled is less than a threshold $\lambda$.

The mathematical formulation of my idea is: $$ maximize \; \sum_{i=1}^{n} p_{i}x_{i} \\ subject \;to \; \sum_{i = 1}^{n} \; \sum_{\{j = 1, \; j > i\}}^{n} d_{ij}x_{i}x_{j} \leq \lambda\\ x_{i} \in \{0,1\}, \; \forall i \in \{1,..., n\} $$

Where $n$ is the number of nodes, $p_{i}$ is the profit of node $i$, and $d_{ij}$ is the distance to go from the node $i$ to node $j$.

The problem is similar to the knapsack 0-1, but having the weights on both nodes and edges, I can not solve it. Do you have any ideas?

$\endgroup$
1
$\begingroup$

You could solve your quadratic problem as a MIP (Mixed Integer Programming) problem using something like: $$ \begin{array}{ll} \max&\sum_i p_i x_i \\ &y_{i,j} \ge x_i+x_j-1 \\ &\sum_{i,j} d_{i,j} y_{i,j} \le \lambda \\ & x_i \in \{0,1\} \\ & y_{i,j} \in [0,1] \end{array} $$ where we restrict all $(i,j)\in A$.

$\endgroup$
1
  • $\begingroup$ I think about it and eventually I'll let you know if it is my solution. Thank you very much! $\endgroup$
    – Luca Russo
    Jan 25 '16 at 22:12

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.