writing down a constraint in IBM CPLEX

Question

My question is about writing down a constraint in IBM CPLEX or in any solver.

Imagine you have a graph with N nodes and E edges. Imagine for connecting one node (source node) to another specific node (destination node), you have a set of paths. Each path is a list of nodes that start from the source node and end with the destination node. The paths in the set can share nodes. For each path, I have a binary decision variable x_p that indicates if you have decided to use that path (x_p=1) or not (x_p=0). The objective function for my optimization problem is a function of the paths. I want to have a constraint that checks if the paths that have been decided to be used (their binary decision variable is 1) are using at most K nodes which means the summation of the unique nodes on those paths is less than equal to K. Is it possible to write a constraint for this?

Answer 1

Let's name our nodes

[n_0, n_1, ... n_n-1].

A-priori you know all there is to know about path-incidences -> which path is using which nodes, e.g.:

path_0: {n_3, n_5}
path_1: {n_0}
path_2: {n_3, n_4}
path_3: {n_0, n_1}
...

Introduce |nodes| boolean-variables:

node_0_used
node_1_used
...

Introduce |nodes| big-M style constraints:

node_0:

    sum(x_p_i) <= node_0_used * |x_p_i| where p_i are path-usage variables of paths incident to node 0

e.g.
    sum(x_p_1 + x_p_3) <= node_0_used * 2

as: node_0 appears in paths 1 and 3 only
    cardinality of paths where node_0 appears is 2

Then add your final constraint: at most use a unique nodes:

sum(node_i_used) <= a  where i in [0, n-1]