How to see constraint violation for network flow problem

Question

I am testing to see if my network is balanced as part of a larger protection-interdiction-restoration problem. To do this, I'm solving the problem as a minimum cost network flow problem to see if the network is balanced initially. I'm returning that the network is infeasible when I run it, but I'm not sure if it's because I formulated the constraints wrong or because it's genuinely unfeasible. Here's my code:

import gurobipy as gp
from gurobipy import GRB
import csv
import csv
from math import *
import numpy as np
from gurobipy import quicksum

# input arcs names
arccap = open('C:/Users/Emma/Documents/2021-2022/Thesis/Data/poweronly/arcs-smallp.csv', 'r', encoding='utf-8-sig')
csv_arccap = csv.reader(arccap)
mydict_arccap = {}
for row in csv_arccap:
     mydict_arccap[(row[0],row[1])] = float(row[2])
        
arcs, capacity = gp.multidict(mydict_arccap)

#import nodes
# input arcs names
inflow = open('C:/Users/Emma/Documents/2021-2022/Thesis/Data/poweronly/inflow.csv', 'r', encoding='utf-8-sig')
csv_inflow = csv.reader(inflow)
mydict_inflow = {}
for row in csv_inflow:
     mydict_inflow[(row[0])] = float(row[1])

nodes, inflow = gp.multidict(mydict_inflow)

# set cost of all arcs = 1
arccost = open('C:/Users/Emma/Documents/2021-2022/Thesis/Data/poweronly/arcs-smallp.csv', 'r', encoding='utf-8-sig')
csv_arccost = csv.reader(arccost)
mydict_arccost = {}
for row in csv_arccost:
     mydict_arccost[(row[0],row[1])] = float(row[3])
        
arcs, cost = gp.multidict(mydict_arccost)


# Create optimization model
m = gp.Model('netflow')

# Create variables
flow = m.addVars(arcs, obj=cost, name="flow")

# flow on single arc cannot exceed capacity
m.addConstrs(
    (flow.sum(i, j) <= capacity[i, j] for i, j in arcs), "cap")

# flow into/out of node must equal supply, demand, or zero for transshipment
m.addConstrs(
  (gp.quicksum(flow[i, j] for i, j in arcs.select('*', j)) + inflow[j] ==
    gp.quicksum(flow[j, k] for j, k in arcs.select(j, '*')) for j in nodes), "node")

# Compute optimal solution
m.optimize()

# Print solution
if m.status == GRB.OPTIMAL:
    solution = m.getAttr('x', flow)
    for i, j in arcs:
        if solution[i, j] > 0:
            print('%s -> %s: %g' % (i, j, solution[i, j]))

And my output:

    Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 298 rows, 179 columns and 537 nonzeros
Model fingerprint: 0x93312151
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [9e-01, 2e+04]
Presolve removed 0 rows and 2 columns
Presolve time: 0.01s

Solved in 0 iterations and 0.01 seconds (0.00 work units)
Infeasible model

Two questions : is this model set up correctly, and if it is genuinely unfeasible, how do I see in what way it's infeasible? Right not the "inflow" parameter has negative values for demand nodes, positive values for supply, and zero values for transshipment nodes.

Answer 1

Similar to the comment by @prubin I would recommend to create a small scale test problem by providing some simpler csv that you know are feasible. Then you can validate your model. With a valid model you can proceed to find out why your data may be invalid.

I'd suggest to code some basic data validation. Given your problem the following rules must hold

1. total demand needs to be equal to total supply (resp. the absolute values of those)
2. the sum of all incoming or outgoing arcs into a supply or demand node must be at least as large as to accomodate the respective inflow

Furthermore, you could also first try to solve a pure maxflow prior to treating it as mincost-maxflow. Transform your graph into a network with just one source node that connects to all supply nodes with arcs having capacity equal to the supply. Then connect all demand nodes with a target node with arcs' capacity equal to the demand (respectively its absolute value). The respective maxflow should saturate all the arcs that you have added, i.e., maxflow = total demand. Otherwise, your network's capacity is too small.

When solving the maxflow yields that the network's capacity is large enough, you can add the demand/supply into the flow equation and solve it as the final mincost-maxflow problem that you intended to do.

Alternatively to solving your problem as maxflow first, you can also add some variables to relax the flow conservation constraint in your existing formulation. E.g. which add or subtract an additional amount so that the model can become feasible even when inflow would not be. However, I'd suggest to make these variables just positive and apply the inflow always on the respective side of the equation where it would be negative. You can then bound each variable in the range of the inflow. Finally, you'd add them to the objective function with a high penalty term so that the solver needs to set these to 0 to achieve the feasible optimal solution. Then it's easy to check if your model would be infeasible in the original formulation by comparing whether any of those relaxation variables is non-zero.

Answer 2

Below constraint of flow restriction on an arc need not be summed as it is a restriction at an arc level

m.addConstrs( (flow.sum(i, j) <= capacity[i, j] for i, j in arcs), "cap")

hence,it has to be corrected to below:

m.addConstr((flow[i,j] <= capacity[i,j] for i,j in arcs),"cap")

Answer 3

There are a number of things you can try.

First, the Gurobi output says the lower limit on right-hand side values is 7e-16, rather than zero, which looks a bit suspicious to me. You might want to track down where that occurs and see if the constraint has any visible issues.

Next, you can ask Gurobi for an irreducible infeasible subset (IIS) of constraints and variable bounds. If there is a problem with the model, it will be in one of those constraints or bounds.

If you know what should be a feasible solution (no matter how poor in objective terms), you can try fixing all the variables to their values in that solution (by setting lower bound = upper bound = value) and running the solver. Assuming it still says infeasible, get an IIS and check the constraints in the set by substituting your feasible solution and seeing what goes wrong.

If you do not know a feasible solution, yet another possibility is to construct a small test problem for which you do know a feasible solution and try that (same code, different input files). There is no guarantee that whatever problem the model has will render your test case infeasible, but if it does you can use the previous approach.

Answer 4

The first thing to check: in order for a network flow model to be feasible, the sum of supplies and demands over all nodes must be zero.

If you know that test passes, then you can start to find an initial feasible flow. You can fail if the search algorithm concludes that there is no way to flow all the supply through the network in order to satisfy all the demand. That can happen if there is a cut separating supply nodes from some set of demand nodes with a capacity smaller than the amount of the cut-off demand.