Gurobi network simplex

Answered

Rosario Scatamacchia

February 02, 2024 09:21

• 
• 
• 

Hi, 

I am testing instances of the transportation problem with the Gurobi's network simplex algorithm.

I can write down the corresponding LP models and then set the parameter NetworkAlg to 1. However, I have memory issues in very large instances due to the LP models.

Is there a way to launch the network simplex with Gurobi without specifically building an LP model (using only the input information about transportation costs, supplies and demands)? 

Thank you, 

Best regards

Rosario

0

• 

  David Torres Sanchez

  • Gurobi Staff

  February 02, 2024 15:05 Edited

  Hi Rosario,

  For the command line we only accept the following Model File Formats.

  Alternatively, you can load the instances to another interface (e.g. a graph modelling tool) and use the Gurobi API to formulate the model and solve it (this won't require you to write any new file).
  I did recently for the min-cost flow DIMACs instances so I share the code below (no guarantees). Usage \(\texttt{python3 script_name.py path/to/dimacs.min}\)

  Cheers, 
  David

  import time
  import sys
  from pathlib import Path
  
  import gurobipy as gp
  from networkx import DiGraph
  
  
  def read_dimacs_flow(fname):
      g = DiGraph()
  
      ecount = 0
      with open(fname) as f:
          lines = f.readlines()
          for l in lines:
              if "c " in l:
                  continue
              if "n " in l:
                  if "min" in l:
                      continue
                  s = l.split(" ")
                  nid = int(s[1])
                  nsupply = int(s[2])
                  g.add_node(nid, demand=nsupply)
              if "a " in l:
                  s = l.split(" ")
                  source_id = int(s[1])
                  target_id = int(s[2])
                  low = int(s[3])
                  cap = int(s[4])
                  cost = int(s[5])
                  g.add_edge(source_id, target_id, capacity=cap, weight=cost)
                  ecount += 1
      print(f"Loaded graph with")
      print(f"Num of nodes: {g.number_of_nodes()}")
      print(f"Num of arcs:  {g.number_of_edges()} {ecount=}")
      return g
  
  
  def solve(g, name):
      with gp.Env(params={"NetworkAlg": 1}) as env, gp.Model(name, env=env) as model:
          edges, capacities, costs = gp.multidict(
              {(i, j): [d["capacity"], d["weight"]] for i, j, d in g.edges(data=True)}
          )
          nodes = list(g.nodes(data=True))
          x = {
              (i, j): model.addVar(
                  name=f"flow[{i},{j}]",
                  ub=capacities[i, j],
                  obj=costs[i, j],
              )
              for i, j in edges
          }
  
          flow_constrs = {}
          for n, data in nodes:
              dmd = 0
              if "demand" in data:
                  dmd = data["demand"]
              flow_constrs[n] = model.addConstr(
                  (
                      gp.quicksum(x[n, j] for j in g.successors(n))
                      - gp.quicksum(x[j, n] for j in g.predecessors(n))
                      == dmd
                  ),
                  name=f"flow_balance[{n}]",
              )
  
          model.write(f"{name}.mps.bz2")
          t = time.time()
          model.optimize()
          print(f"Using Gurobi\t{model.objval}\ttaken {time.time() - t}")
  
  
  def get_name(s):
      return str(Path(s).stem)
  
  
  g = read_dimacs_flow(sys.argv[1])
  solve(g, get_name(sys.argv[1]))

   

  0
• 

  Rosario Scatamacchia

  February 02, 2024 15:37

  • 
  • 
  • 

  Hi David, 

  thank you for your fast reply and your advice!

  Cheers,

  Rosario

   

   

  0

Please sign in to leave a comment.