Weak Flow Cover Inequalities for the Capacitated Facility Location Problem
| Autor: | Pasquale Avella, Maurizio Boccia, Sara Mattia, Fabrizio Rossi |
|---|---|
| Přispěvatelé: | Avella, P., Boccia, M., Mattia, S., Rossi, F. |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Polynomial
Mathematical optimization separation Information Systems and Management General Computer Science Computer science Cut-and-branch Facility location Flow cover Separation Valid inequalities 0211 other engineering and technologies cut-and-branch flow cover 02 engineering and technology Management Science and Operations Research valid inequalities Industrial and Manufacturing Engineering Set (abstract data type) 0502 economics and business Time complexity 050210 logistics & transportation 021103 operations research Heuristic facility location 05 social sciences Facility location problem Flow (mathematics) Modeling and Simulation Cover (algebra) |
| Zdroj: | European journal of operational research 289 (2021): 485–494. info:cnr-pdr/source/autori:P. Avella, M. Boccia, S. Mattia, F. Rossi./titolo:Weak Flow Cover Inequalities for the Capacitated Facility Location Problem/doi:/rivista:European journal of operational research/anno:2021/pagina_da:485/pagina_a:494/intervallo_pagine:485–494/volume:289 |
| Popis: | The Capacitated Facility Location Problem calls for opening a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of customers. We present a new class of valid inequalities, the Weak Flow Cover inequalities. We show that Weak Flow Cover inequalities can be separated in polynomial time and turned into violated Flow Cover inequalities. In this way, we are able to provide a polynomial separation heuristic for the latter. Embedding the separation procedure into a cut-and-branch approach, we get results significantly better than those reported in the recent literature both for the lower and the upper bounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|