# Optimization problem on graph with weights on nodes and edges

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?

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