Solving Minimum Cost Flow Problem

[innoken...@gmail.com]

Hello!

I want to solve Minimum Cost Flow problem with about 70000 arcs and 1000 vertices. As the first step I try to solve problem with 15620 arcs and 294 vertices, but solver can't solve even this not big dimension example. I get the following.

C:\or-tools-7.0>tools\make run SOURCE=C:\or-tools_Program\mincostflowsf.cc

cl /EHsc /MD /nologo -nologo  /D__WIN32__ /DPSAPI_VERSION=1 /DNOMINMAX /DWIN32_L

EAN_AND_MEAN=1 /D_CRT_SECURE_NO_WARNINGS /O2 -DNDEBUG /I. /Iortools/gen /I"depen

dencies\\install\\include" /I"dependencies\\install\\include" /DGFLAGS_DLL_DECL=

 /DGFLAGS_DLL_DECLARE_FLAG= /DGFLAGS_DLL_DEFINE_FLAG= /I"dependencies\\install\\

include" /DGOOGLE_GLOG_DLL_DECL= /I"dependencies\\install\\include" /I"dependenc

ies\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\

\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\ins

tall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CLP /I"dependencie

s\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\i

nstall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CBC /DUSE_GLOP /

DUSE_BOP     \

 -c C:\or-tools_Program\mincostflowsf.cc \

 /Foobjs\\mincostflowsf.obj

mincostflowsf.cc

cl /EHsc /MD /nologo -nologo  /D__WIN32__ /DPSAPI_VERSION=1 /DNOMINMAX /DWIN32_L

EAN_AND_MEAN=1 /D_CRT_SECURE_NO_WARNINGS /O2 -DNDEBUG /I. /Iortools/gen /I"depen

dencies\\install\\include" /I"dependencies\\install\\include" /DGFLAGS_DLL_DECL=

 /DGFLAGS_DLL_DECLARE_FLAG= /DGFLAGS_DLL_DEFINE_FLAG= /I"dependencies\\install\\

include" /DGOOGLE_GLOG_DLL_DECL= /I"dependencies\\install\\include" /I"dependenc

ies\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\

\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\ins

tall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CLP /I"dependencie

s\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\i

nstall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CBC /DUSE_GLOP /

DUSE_BOP     \

 objs\\mincostflowsf.obj \

  lib\\ortools.lib  \

 /Febin\\mincostflowsf.exe

bin\\mincostflowsf.exe

tools\make: *** [run] Error -1073741819

or

C:\or-tools-7.0>tools\make run SOURCE=C:\or-tools_Program\mincostflowsf.cc

cl /EHsc /MD /nologo -nologo  /D__WIN32__ /DPSAPI_VERSION=1 /DNOMINMAX /DWIN32_L

EAN_AND_MEAN=1 /D_CRT_SECURE_NO_WARNINGS /O2 -DNDEBUG /I. /Iortools/gen /I"depen

dencies\\install\\include" /I"dependencies\\install\\include" /DGFLAGS_DLL_DECL=

 /DGFLAGS_DLL_DECLARE_FLAG= /DGFLAGS_DLL_DEFINE_FLAG= /I"dependencies\\install\\

include" /DGOOGLE_GLOG_DLL_DECL= /I"dependencies\\install\\include" /I"dependenc

ies\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\

\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\ins

tall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CLP /I"dependencie

s\\install\\include" /I"dependencies\\install\\include\\coin" /I"dependencies\\i

nstall\\include" /I"dependencies\\install\\include\\coin" /DUSE_CBC /DUSE_GLOP /

DUSE_BOP     \

 objs\\mincostflowsf.obj \

  lib\\ortools.lib  \

 /Febin\\mincostflowsf.exe

bin\\mincostflowsf.exe

tools\make: *** [run] Error 255

I have installed OR-tools for C++ from source and successfully complete all the tests.

So I have the question:

Can your solver deal with problem of 70000 arcs and  1000 vertices? If it can't, do you know another solver for Minimum Cost Flow Problem, which can deal with my problem?

Thanks in advance!

[Laurent Perron]

I do believe the solver works fine on these sizes. But there may be requirements that are not met (make sure the graph is connected, maybe no duplicate arcs, that the sizes do not overflow...).

Can you share some code with me ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Matthew Galati]

SAS is pretty good at MCF:  https://go.documentation.sas.com/?cdcId=pgmsascdc&cdcVersion=9.4_3.4&docsetId=casnopt&docsetTarget=casnopt_optnet_overview.htm&locale=en

If you are looking for free/open-source, I believe LEMON is the best.

[innoken...@gmail.com]

Hi! Thanks you for your answer!

I'm not keen of programming. I just take example min_cost_flow.cc and instead definition of supplies {{0, 20}, {1, 0}, {2, 0}, {3, -5}, {4, -15}} I put the contain of file supplies.txt, instead definition of arcs { {{0, 1}, 15, 4}, {{0, 2}, 8, 4},  {{1, 2}, 20, 2}, {{1, 3}, 4, 2},  {{1, 4}, 10, 6}, {{2, 3}, 15, 1}, {{2, 4}, 4, 3},  {{3, 4}, 20, 2}, {{4, 2}, 5, 3}} I put the contain of file arcs.txt. So I can't publish the code here, because it has more than 15000 lines. :-)

// Copyright 2018 Google LLC

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

//

//     http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

#include "ortools/graph/min_cost_flow.h"

#include "ortools/base/logging.h"

namespace operations_research {

struct Arc {

  std::pair<NodeIndex, NodeIndex> nodes;

  FlowQuantity capacity;

  FlowQuantity unit_cost;

};

void SolveMinCostFlow() {

  // Define supply of each node.

  const std::vector<std::pair<NodeIndex, FlowQuantity>> supplies = {

      {0, 20}, {1, 0}, {2, 0}, {3, -5}, {4, -15}}; // !!!Here I put the contain of file supplies.txt!!!

  // Define each arc

  // Can't use std::tuple<NodeIndex, NodeIndex, FlowQuantity>

  // Initialization list is not working on std:tuple cf. N4387

  // Arc are stored as {{begin_node, end_node}, capacity}

  const std::vector<Arc> arcs = {

      {{0, 1}, 15, 4}, {{0, 2}, 8, 4},  {{1, 2}, 20, 2},

      {{1, 3}, 4, 2},  {{1, 4}, 10, 6}, {{2, 3}, 15, 1},

      {{2, 4}, 4, 3},  {{3, 4}, 20, 2}, {{4, 2}, 5, 3}}; // !!!Here I put the contain of file arcs.txt!!!

  StarGraph graph(supplies.size(), arcs.size());

  MinCostFlow min_cost_flow(&graph);

  for (const auto &it : arcs) {

    ArcIndex arc = graph.AddArc(it.nodes.first, it.nodes.second);

    min_cost_flow.SetArcCapacity(arc, it.capacity);

    min_cost_flow.SetArcUnitCost(arc, it.unit_cost);

  }

  for (const auto &it : supplies) {

    min_cost_flow.SetNodeSupply(it.first, it.second);

  }

  LOG(INFO) << "Solving min cost flow with: " << graph.num_nodes()

            << " nodes, and " << graph.num_arcs() << " arcs.";

  // Find the maximum flow between node 0 and node 4.

  min_cost_flow.Solve();

  if (MinCostFlow::OPTIMAL != min_cost_flow.status()) {

    LOG(FATAL) << "Solving the max flow is not optimal!";

  }

  FlowQuantity total_flow_cost = min_cost_flow.GetOptimalCost();

  LOG(INFO) << "Minimum cost flow: " << total_flow_cost;

  LOG(INFO) << "";

  LOG(INFO) << "Arc   : Flow / Capacity / Cost";

  for (int i = 0; i < arcs.size(); ++i) {

    LOG(INFO) << graph.Tail(i) << " -> " << graph.Head(i) << ": "

              << min_cost_flow.Flow(i) << " / " << min_cost_flow.Capacity(i)

              << " / " << min_cost_flow.UnitCost(i);

  }

}

}  // namespace operations_research

int main(int argc, char **argv) {

  google::InitGoogleLogging(argv[0]);

  FLAGS_logtostderr = 1;

  operations_research::SolveMinCostFlow();

  return EXIT_SUCCESS;

}

I have mentioned above about example with 15620 arcs and 294 vertices. Let's forget about it.

Actually, I want to solve Transportation Problem, but with some additional constraints, which are included in Minimum Cost Flow Problem enviroment. Minimum Cost Flow Problem is a generalization of Transportation Problem.

As the first step I try to solve usual Transportation Problem: I have 142 origins and 110 destinations. Each origin connects with each destination, 142*110=15620 arcs. Also I introduce dummy arcs for common source and common sink, 15620+142+110=15872 arcs and 142+110+2=254 vertices. I want to push through the graph from source (vertex number 253) to sink (vertex number 254) 100 units of flow. For dummy arcs, which go from source to origins, I put capacity of each arc equals supply of this origin and cost equals zero. For dummy arcs, which go from destinations to sink, I put capacity of each arc equals demand of this destination and cost equals zero. For all other arcs from origin to destination I put capacity equals 1000 and cost equals value of kilometers from origin to destination.

As you can see graph permit 461 units of flow, so it can't be non-connected or have duplicate arcs. Furthermore I put capacitites of arc between origins and destinations equals to 1000.

But solver do not solve this quite easy problem. May be it's my mistake, but I can't find it.

I'm not good at objective programming. I can understand the code, but I can't produce something like objective programming.

May be you have some program, which takes information from 2 files similiar to supplies.txt and arcs.txt (I attach theese files to message) and solve the problem? Do you have something like this?

Is my insertion of huge part of code into min_cost_flow.cc appropriate?

What does Error 255 means?

среда, 10 апреля 2019 г., 23:13:23 UTC+7 пользователь Laurent Perron написал:

[innoken...@gmail.com]

Thank you, Matthew for your answer! I have deal with simple examples for LEMON, but I have not inspected this library deeply.

четверг, 11 апреля 2019 г., 1:17:28 UTC+7 пользователь Matthew написал:

[innoken...@gmail.com]

Now I try to solve even easier problem with 72 origins and 32 destinations (2408 arcs, 106 verticies), but I get the following.

 

A then command line types Error 255...

 

What am I doing wrong?

And I repeat my questions:

Is my insertion of huge part of code (arcs+supplies) into min_cost_flow.cc appropriate?

What do Errors 255 and -1073741819 mean?

Thanks in advance!

[Laurent Perron]

Can you try with the SimpleMinCostFlow API ?

Le jeu. 11 avr. 2019 à 10:08, <innoken...@gmail.com> a écrit :

Now I try to solve even easier problem with 72 origins and 32 destinations (2408 arcs, 106 verticies), but I get the following.

 

What am I doing wrong?

And I repeat my questions:

Is my insertion of huge part of code (arcs+supplies) into min_cost_flow.cc appropriate?

What do Errors 255 and -1073741819 mean?

Thanks in advance!

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[innoken...@gmail.com]

Dear Laurent Perron, could you answer my question, please? What do Errors 255 and -1073741819 mean?

I install or-tools for C++ from source on Windows 7.

Thanks in advance!

[Laurent Perron]

Nothing. It crashed.

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cc56e30e-1140-40dc-9aa2-a3707c7864c0%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

--Laurent