# Difficulty in modeling constraint for generating a path

Hello.

I am trying to solve a path planning problem similar to TSP. However, in my case it is not necessary to visit all nodes and not all nodes can be connected. Also, the objective function is to maximize collection of items between start and end node.

Difficulties I am facing are:

1) How do I define the start and end node in the optimization formulation?

2) How do I put a constraint that takes care of connectivity since if a node is selected the ones connecting it should also be selected to complete the path?

The approach I use was to store the node to node available items in a form of dictionary.

items = {(1,0): 10, (2,0) :5, (2,1):8, ....}

Then created decision variable for each possible combination:

x = m.addVars(items.keys(), obj=items, vtype= GRB.BINARY)

Then I put the objective function as:

m. setObjective (sum(x[i]* items[i] for i in items) , GRB.MAXIMIZE )

Based on the connectivity I created a adjacency list :

adj = {

(0):[1,3],

(1):[0,2,4],

(2):[1,5],

(3):[0,4,6],

(4):[1,3,5,7],

(5):[2,4,8],

(6):[3,7],

(7):[4,6,8],

(8):[0,5,7]

}

Then item carrying capacity constraint:

m.addConstr((gp.quicksum(x[i]*items[i] for i in items) <= capacity ) ,'c1')

However, I am not able to figure out a proper constraint that takes into account the connectivity between nodes. Example, I want to go from 0 to 8, and if 1 is selected either 2 or 4 also should be selected. I tried to use or but the solution turned out to be infeasible because at the end the constraint was forcing each node to get selected and that violated the capacity constraint.

Any help in this regard is really appreciated. Thank you in advance!

Please sign in to leave a comment.

## Comments

0 comments