An optimization problem is defined a graph of V nodes and E edges. First, I defined variables on each nodes (two independent variables for each node), and each edge imposes one constraint (on the 2 variables of the two end nodes). So the system has solutions when $$ 2V\geq E $$ Second, for the same problem the variables are defined on each edge from the outset. Each node imposes one constraint (on the 3 variables on the 3 connected edges). Thus,the system has solutions if $$ E\geq V $$ holds.

The problem is that the two approaches above model the same problem, but how come it leads to two different conditions of solvablity?

Does it related to the dependency between constraints? (similar to the row rank of a matrix) And how to examine the dependency between constraints in a systematic way?


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.