Abstract
In this paper, we discuss an extension of split cuts that is based on widening the underlying disjunctions. That the formula for deriving intersection cuts based on splits can be adapted to this case has been known for a decade now. For the first time though, we present applications and computational results. We further provide some theory that supports our findings, discuss extensions with respect to cut strengthening procedures and present some ideas on how to use the wider disjunctions also in branching.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andersen, K., Cornuéjols, G., Li, Y.: Reduce-and-split cuts: Improving the performance of mixed-integer Gomory cuts. Manag. Sci. 51, 1720–1732 (2005)
Andersen, K., Cornuéjols, G., Li, Y.: Split closure and intersection cuts. Math. Program. 102, 457–493 (2005)
Balas, E.: Intersection cuts-a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
Balas, E., Jeroslow, R.G.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)
Belhaiza, S., Hansen, P., Laporte, G.: A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Comput. Oper. Res. 52, 269–281 (2014)
Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)
Coughlan, E.T., Lübbecke, M.E., Schulz, J.: A Branch-and-price algorithm for multi-mode resource leveling. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 226–238. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13193-6_20
Furini, F., Ljubić, I., Sinnl, M.: ILP and CP formulations for the lazy bureaucrat problem. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 255–270. Springer, Cham (2015). doi:10.1007/978-3-319-18008-3_18
Gomory, R.E.: An algorithm for integer solutions to linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963)
Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0–1 knapsack problem. Manag. Sci. 45, 414–424 (1999)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, UK (1990)
Pisinger, D.: http://www.diku.dk/pisinger/codes.html. Accessed 19 Feb 2016
Wiese, S: On the interplay of Mixed Integer Linear, Mixed Integer Nonlinear and Constraint Programming. Ph.D. thesis, University of Bologna (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Bonami, P., Lodi, A., Tramontani, A., Wiese, S. (2017). Cutting Planes from Wide Split Disjunctions. In: Eisenbrand, F., Koenemann, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2017. Lecture Notes in Computer Science(), vol 10328. Springer, Cham. https://doi.org/10.1007/978-3-319-59250-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-59250-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59249-7
Online ISBN: 978-3-319-59250-3
eBook Packages: Computer ScienceComputer Science (R0)