Á. Corberán, M. Landete, J. Peiró, F. Saldanha-da-Gama

p-hub location problems in transportation networks are NP-hard combinatorial optimization problems with many industrial applications. In the r-allocation variant, three optimization subproblems are involved: a service facility location problem, an assignment problem, and a routing problem.

In this work we focus on finding new valid inequalities for this variant. Some of them have been adapted from inequalities proposed for related problems, while other inequalities are new contributions.

The intersection of many of them defines a set packing polyhedron, which has an associated conflict graph that we have studied in order to generate new valid inequalities for the problem, especially those of the clique and odd-hole classes.

Computational results will be provided showing that the new inequalities help in strengthen the linear relaxation of the original formulation.

Keywords: hub location, non-stop services, set packing problem, clique, odd hole, branch and cut


GT1-1 Location
September 3, 2019  3:30 PM
I3L8. Georgina Blanes building

Other papers in the same session

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.