Publication detail

Network Flow Problem Heuristic Reduction Using Machine Learning

ROSECKÝ, M. PLUSKAL, J. ŠOMPLÁK, R.

Original Title

Network Flow Problem Heuristic Reduction Using Machine Learning

Type

journal article in Web of Science

Language

English

Original Abstract

Most of the supporting tools developed for logistic optimization and processing infrastructure planning are based on the network flow problem. The real-world application of these instruments can provide great insight and help to ensure long-term sustainability. The main limitation of these tools lies in great computing demand when there is the necessity of solving large-scale tasks in great detail. It means that the ability to find the optimal solution for real-world problems is limited. Thus, the detail of infrastructure is often reduced by data aggregation or heuristic approaches are used to find a suboptimal solution. This paper proposes a machine learning classification model to reduce the number of variables for an exact solution algorithm. First, the design of experiments is used to create a set of smaller problems that are possible to solve exactly. Artificial data are used at this stage, while domain knowledge is used to set appropriate distribution and parameters. Second, the classification model estimates the probability of the presence of each arc in the optimal solution. Features, which are related to costs and capacity, of each arc are utilized in the classification model. Models created on a subset of generated problems are then tested on the other problems. Finally, the proposed framework is applied to the waste management problem in the Czech Republic. The results of the verification show, that it is possible to remove 95 % of arcs without impact on strategic decisions and without significant change of an objective function. The computing time of the reduced problem takes only 7 % of the original task.

Keywords

Model-size reduction techniques; Classification model; Arcs removal; Waste-to-Energy localization; Large-scale optimization

Authors

ROSECKÝ, M.; PLUSKAL, J.; ŠOMPLÁK, R.

Released

23. 9. 2023

Publisher

Springer Nature

Location

DORDRECHT

ISBN

1389-4420

Periodical

OPTIMIZATION AND ENGINEERING

Year of study

25

Number

1

State

Swiss Confederation

Pages from

93

Pages to

119

Pages count

27

URL

https://link.springer.com/article/10.1007/s11081-023-09838-4

Full text in the Digital Library

http://hdl.handle.net/11012/214428

BibTex

@article{BUT184474,
  author="Martin {Rosecký} and Jaroslav {Pluskal} and Radovan {Šomplák}",
  title="Network Flow Problem Heuristic Reduction Using Machine Learning",
  journal="OPTIMIZATION AND ENGINEERING",
  year="2023",
  volume="25",
  number="1",
  pages="27",
  doi="10.1007/s11081-023-09838-4",
  issn="1389-4420",
  url="https://link.springer.com/article/10.1007/s11081-023-09838-4"
}