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
Improve this question
$\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 ♦
    Mar 20, 2022 at 22:36
  • $\begingroup$ Do you maybe have the wrong sign on inflow[j]? $\endgroup$
    – RobPratt
    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$
    – Emma Kuttler
    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 ♦
    Mar 20, 2022 at 23:50
  • $\begingroup$ So can we consider this question as answered, or is it still open? $\endgroup$
    – prubin ♦
    Mar 20, 2022 at 23:50

0

Reset to default

Your Answer

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