I have questions about the solution of the problem of the flow of minimum cost available solvers / software packages (such as MATLAB, gurobi, etc.)

Problem formulation: Given an oriented graph G (V, A, s, t) V is the set of vertices of the graph (| N | = n); A is the set of arcs of the graph (| A | = m); s - selected vertex, source; t - selected vertex, sink. For each arc, the cost of sending the stream unit c_ {a} and the throughput of the arc u_ {a} are known. It is necessary to send the flow from the source s to the drain t along the arcs of the graph so that this flow has the minimum cost and satisfies the constraints on the carrying capacity of the arcs. Unfortunately, I cannot give the statement of the problem as LaTEX, this site does not allow it. But the wording is simple and easy to search on the Internet.

In the formulation of the problem, m (the number of arcs in the digraph G) is the number of variables, n + m (the number of vertices + the number of arcs) is the number of constraints.

I am trying to solve this problem with 70,000 arcs and 1000 vertices in MATLAB (using a linprog linear programming solver) on my computer with an A10 processor and 6 GB of RAM. It is easy to calculate that to solve the problem, you need to store a matrix of 71000x70000 = 4970000000 with almost 5 billion cells. For my computer with a RAM limit in MATLAB, I can create a matrix with a maximum of 740,000,000 cells. There was also an attempt to solve this problem using google OR-tools, but there I could not solve the problem with dimensions of 15620 arcs and 292 vertices.

Actually questions to the knowledgeable:

  1. What is the limit on the number of cells in the matrix for gurobi? (I could not find this value in freely accessible places)

  2. Is there any tricky way to reduce the dimension of a task from 70,000 arcs and 1000 vertices to visible values?

  3. As usual, such problems are generally solved? With the attraction of super-computers, or how?

0