1
$\begingroup$

I'm running a simple MCNF model to see if my network is balanced. I'm using Gurboi in Python and with the IIS I can see that there are 2 constraint violations making it infeasible. How do I fix these constraint violations without changing the overall supply or demand?

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-smallp2.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/inflow2.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-smallp2.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[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]))
m.computeIIS() 

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.00s

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

IIS computed: 2 constraints and 2 bounds
IIS runtime: 0.00 seconds (0.00 work units)

Edit: I was able to produce a .lp log with the following results. What does it mean and how do I fix it?

\ Model netflow_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
 
Subject To
 node[1]: flow[3,1] = 500
 node[3]: - flow[3,1] - flow[3,4] - flow[3,12] = 525
Bounds
 flow[3,1] free
End
$\endgroup$
5
  • $\begingroup$ If I am reading this correctly (a big "if"), you are allowing flows to be either positive or negative. Does that mean that a positive value for flow[3,1] is a flow from node 3 to node 1 and a negative value is a flow from node 1 to node 3? Also, are all the flow variables free (domain $(-\infty, +\infty)$)? $\endgroup$
    – prubin
    Commented Mar 20, 2022 at 22:36
  • $\begingroup$ Do you maybe have the wrong sign on inflow[j]? $\endgroup$
    – RobPratt
    Commented Mar 20, 2022 at 22:41
  • $\begingroup$ I realized the way I had set up the model used single directional links when they should have been bidirectional. That ended up producing a feasible model! I'm not sure why the domain is free since all arcs had a capacity of 15,000 but I guess it doesn't matter now. $\endgroup$ Commented Mar 20, 2022 at 22:55
  • 1
    $\begingroup$ I think the reason the variables were free is that you put the capacity limits in as functional constraints (inequalities). Had you put the capacities as upper/lower bounds on the flow variables, they would not have been free. $\endgroup$
    – prubin
    Commented Mar 20, 2022 at 23:50
  • $\begingroup$ So can we consider this question as answered, or is it still open? $\endgroup$
    – prubin
    Commented Mar 20, 2022 at 23:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.