[en] We introduce the following cycle selection problem which is motivated by an application to kidney exchange problems. Given a directed graph, a cycle selection is a subset of arcs forming a union of directed cycles. A related optimization problem, the Maximum Weighted Cycle Selection problem can be defined as follows: given a weight for each arc, find a cycle selection which maximizes the total weight. We prove that this problem is strongly NP-hard. Next, we focus on cycle selections in complete directed graphs. We provide several ILP formulations of the problem: an arc formulation featuring an exponential number of constraints which can be separated in polynomial time, four extended compact formulations, and an extended non compact formulation. We investigate the relative strength of these formulations. We concentrate on the arc formulation and on the description of the associated cycle selection polytope. We prove that this polytope is full-dimensional, and that all the inequalities used in the arc formulation are facet-defining. Furthermore, we describe three new classes of facet-defining inequalities and a class of valid inequalities. We also consider the consequences of including additional constraints on the cardinality of a selection or on the length of the associated cycles.
Centre/Unité de recherche :
HEC Recherche. Supply Chain Management and Business Analytics - ULiège
Disciplines :
Méthodes quantitatives en économie & gestion Mathématiques
Auteur, co-auteur :
Baratto, Marie ; Université de Liège - ULiège > HEC Liège : UER > UER Opérations: Rech. opérationnelle et gest. de la product.
Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > UER Opérations: Rech. opérationnelle et gest. de la product.
Abraham, D., Blum, A., Sandholm, T., Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proceedings of the 8th ACM Conference on Electronic Commerce, 2007, ACM, New York, 295–304.
Balas, E., Oosten, M., On the cycle polytope of a directed graph. Networks, 36(1), 2000, 34,46.
Balas, E., Rüdiger, S., On the cycle polytope of a directed graph and its relaxations. Networks, 54(1), 2009, 47,55 URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.20304.
Bang-Jensen, J., Gutin, G.Z., Digraphs: Theory, Algorithms and Applications, second Springer Monographs in Mathematics, 2009, Springer, London.
Bauer, P., Linderoth, J.T., Savelsbergh, M.W.P., A branch and cut approach to the cardinality constrained circuit problem. Math. Program. 91 (2002), 307–348.
Biró, P., van de Klundert, J., Manlove, D., Pettersson, W., Andersson, T., Burnapp, L., Chromy, P., Delgado, P., Dworczak, P., Haase, B., Hemke, A., Johnson, R., Klimentova, X., Kuypers, D., Nanni Costa, A., Smeulders, B., Spieksma, F., Valentín, M.O., Viana, A., Modelling and optimisation in European kidney exchange programmes. European J. Oper. Res. 291:2 (2021), 447–456.
Conforti, M., Cornuéjols, G., Zambelli, G., Integer Programming. 2014, Springer.
Constantino, M., Klimentova, X., Viana, A., Rais, A., New insights on integer-programming models for the kidney exchange problem. European J. Oper. Res. 231:1 (2013), 57–68.
Coullard, C.R., Pulleyblank, W.R., On cycle cones and polyhedra. Linear Algebra Appl., 114(C), 1989, 613,640 URL: http://dx.doi.org/10.1016/0024-3795(89)90483-7.
Dickerson, J., Manlove, D., Plaut, B., Sandholm, T., Trimble, J., Position-indexed formulations for kidney exchange. 2016 arXiv.Org, URL: http://search.proquest.com/docview/2079148970/.
Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 6 (1981), 169–197.
Hartmann, M., Özlük, O., Facets of the p-cycle polytope. Discrete Appl. Math. 112:1 (2001), 147–178.
Hoffman, A.J., Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Bellman, R., Hall, M., (eds.) Combinatorial Analysis: Proceedings of Symposia in Applied Mathematics, Vol. 10, 1960, American Mathematical Society, Providence, 113–127.
Karp, R.M., Reducibility among combinatorial problems. Complexity of Computer Computations, 1972, Springer, 85–103.
Lam, E., Mak-Hau, V., Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange. Comput. Oper. Res., 115, 2020, 104852 URL: http://dx.doi.org/10.1016/j.cor.2019.104852.
Mak-Hau, V., On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches. J. Comb. Optim. 33 (2017), 35–59.
Mak-Hau, V., A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs. Comput. Oper. Res. 99 (2018), 13–26 URL: http://dx.doi.org/10.1016/j.cor.2018.06.008.
Roth, A.E., Sönmez, T., Ünver, M.U., Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. Amer. Econ. Rev. 97:3 (2007), 828–851.
Roth, A., Ünver, M.U., Sönmez, T., Kidney exchange. Q. J. Econ., 119(2), 2004.
Seymour, P.D., Sums of circuits. Bondy, J.A., Murty, U.S.R., (eds.) Graph Theory and Related Topics, 1979, Academic Press, New York, 341–355.
Smeulders, B., Bartier, V., Crama, Y., Spieksma, F.C.R., Recourse in kidney exchange programs. INFORMS J. Comput., in press, 2021 URL: https://orbi.uliege.be/bitstream/2268/231958/1/KidneyRecourseBCSS.pdf.
Tarjan, R.E., Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972), 146–160.
