Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-f554764f5-wjqwx Total loading time: 0 Render date: 2025-04-21T22:42:04.904Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  04 April 2025

Timo Berthold ,
Andrea Lodi  and
Domenico Salvagnin
Timo Berthold
Affiliation:
FICO
Andrea Lodi
Affiliation:
Cornell Tech
Domenico Salvagnin
Affiliation:
Università degli Studi di Padova, Italy
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Primal Heuristics in Integer Programming , pp. 118 - 127
Publisher: Cambridge University Press
Print publication year: 2025

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

Achterberg, T.. Constraint integer programming. PhD thesis, Technische Universität Berlin, 2007.Google Scholar
Achterberg, T.. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, 2009.Google Scholar
Achterberg, T.. LP basis selection and cutting planes. Presentation slides from MIP 2010 workshop in Atlanta. www.isye.gatech.edu/sites/default/files/documents/conferences/2010mip/mip-program.pdf, 2010.Google Scholar
Achterberg, T.. LP relaxation modification and cut selection in a MIP solver. US patent, US20110131167, 2011.Google Scholar
Achterberg, T. and Berthold, T.. Improving the feasibility pump. Discrete Optimization, 4(1):77–86, 2007.CrossRefGoogle Scholar
Achterberg, T. and Wunderling, R.. Mixed integer programming: Analyzing 12 years of progress. In Jünger, M. and Reinelt, G., editors, Facets of Combinatorial Optimization – Festschrift for Martin Grötschel, pages 449–481. Springer, 2013.CrossRefGoogle Scholar
Ahuja, R. K., Orlin, J. B., and Sharma, D.. Very large-scale neighborhood search. International Transactions in Operational Research, 7(4–5):301–317, 2000.Google Scholar
Baena, D. and Castro, J.. Using the analytic center in the feasibility pump. Operations Research Letters, 39(5):310–317, 2011.CrossRefGoogle Scholar
Balas, E., Ceria, S., Dawande, M., Margot, F., and Pataki, G.. OCTANE: A new heuristic for pure 0-1 programs. Operations Research, 49(2):207–225, 2001.CrossRefGoogle Scholar
Balas, E. and Martin, C. H.. Pivot and complemen: a heuristic for 0–1 programming. Management Science, 26(1):86–96, 1980.Google Scholar
Belotti, P. and Berthold, T.. Three ideas for a feasibility pump for nonconvex MINLP. Optimization Letters, 11(1):3–15, 2017.Google Scholar
Bengio, Y., Lodi, A., and Prouvost, A.. Machine learning for combinatorial optimization: A methodological tour dhorizon. European Journal of Operational Research, 290(2):405–421, 2021.Google Scholar
Bénichou, M., Gauthier, J.-M., Girodet, P., Hentges, G., Ribière, G., and Vincent, O.. Experiments in mixed-integer programming. Mathematical Programming, 1:76–94, 1971.Google Scholar
Benoist, T., Estellon, B., Gardi, F., Megel, R., and Nouioua, K.. LocalSolver 1.x: A black-box local-search solver for 0–1 programming. 4OR – A Quarterly Journal of Operations Research, 9(3):299–316, 2011.Google Scholar
Bertacco, L., Fischetti, M., and Lodi, A.. A feasibility pump heuristic for general mixed-integer problems. Discrete Optimization, 4(1):63–76, 2007.Google Scholar
Berthold, T.. Primal heuristics for mixed integer programs. Diploma thesis, Technische Universität Berlin, 2006.Google Scholar
Berthold, T.. Measuring the impact of primal heuristics. Operations Research Letters, 41(6):611–614, 2013.Google Scholar
Berthold, T.. Heuristic algorithms in global MINLP solvers. PhD thesis, Technische Universität Berlin, 2014.Google Scholar
Berthold, T.. RENS: the optimal rounding. Mathematical Programming Computation, 6(1):33–54, 2014.Google Scholar
Berthold, T.. Finding Proper Hardware to Improve your Optimization Software Performance. https://community.fico.com/s/blog-post/a5Q4w000000CvM9EAK/fico2741, 2021.Google Scholar
Berthold, T., Feydy, T., and Stuckey, P. J.. Rapid learning for binary programs. In Lodi, A., Milano, M., and Toth, P., editors, Proceedings of CPAIOR 2010, volume 6140 of Lecture Notes in Computer Science, pages 51–55. Springer, June 2010.Google Scholar
Berthold, T., Francobaldi, M., and Hendel, G.. Learning to use local cuts. arXiv preprint arXiv:2206.11618, 2022.Google Scholar
Berthold, T. and Gleixner, A. M.. Undercover: A primal MINLP heuristic exploring a largest sub-MIP. Mathematical Programming, 144(1–2):315–346, 2014.Google Scholar
Berthold, T., Heinz, S., Pfetsch, M. E., and Vigerske, S.. Large neighborhood search beyond MIP. In L. Gaspero, D., Schaerf, A., and Stützle, T., editors, Proceedings of the 9th Metaheuristics International Conference (MIC 2011), pages 51–60, 2011.Google Scholar
Berthold, T. and Hendel, G.. Shift-and-propagate. Journal of Heuristics, 21(1):73–106, 2015.CrossRefGoogle Scholar
Berthold, T. and Hendel, G.. Learning to scale mixed-integer programs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3661–3668, AAAI, 2021.Google Scholar
Berthold, T., Hendel, G., and Koch, T.. From feasibility to improvement to proof: Three phases of solving mixed-integer programs. Optimization Methods and Software, 33(3):499–517, 2018.Google Scholar
Berthold, T., Lodi, A., and Salvagnin, D.. Ten years of feasibility pump, and counting. EURO Journal on Computational Optimization, 7(1):1–14, 2019.Google Scholar
Berthold, T., Perregaard, M., and Mészáros, C.. Four good reasons to use an interior point solver within a MIP solver. In Kliewer, N., Ehmke, J., and Borndörfer, R., editors, Operations Research Proceedings 2017, pages 159–164, Springer, 2018.CrossRefGoogle Scholar
Berthold, T. and Salvagnin, D.. Cloud branching. In Gomes, C. and Sellmann, M., editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 7874 of Lecture Notes in Computer Science, pages 28–43. Springer, 2013.Google Scholar
Berthold, T., Stuckey, P. J., and Witzig, J.. Local rapid learning for integer programs. In Rousseau, L.-M. and Stergiou, K., editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 67–83. Springer, 2019.Google Scholar
Bestuzheva, K., Besançon, M., Chen, W.-K., et al. The SCIP Optimization Suite 8.0. arXiv preprint arXiv:2112.08872, 2021.Google Scholar
Bishop, C. M.. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer, 2006.Google Scholar
Boland, N. L., Eberhard, A. C., Engineer, F. G. et al. Boosting the feasibility pump. Mathematical Programming Computation, 6:255–279, 2014.Google Scholar
Boland, N. L., Eberhard, A. C., Engineer, F. G., and Tsoukalas, A.. A new approach to the feasibility pump in mixed integer programming. SIAM Journal on Optimization, 22(3):831–861, 2012.CrossRefGoogle Scholar
Bonami, P., Biegler, L. T., Conn, A. R., et al. An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5:186–204, 2008.CrossRefGoogle Scholar
Bonami, P., Cornuéjols, G., Lodi, A., and Margot, F.. A feasibility pump for mixed integer nonlinear programs. Mathematical Programming, 119(2):331–352, 2009.Google Scholar
Bonami, P. and Gonçalves, J.. Heuristics for convex mixed integer nonlinear programs. Computational Optimization and Applications, 51:729–747, 2012.Google Scholar
Bonami, P., Lodi, A., and Zarpellon, G.. A classifier to decide on the linearization of mixed-integer quadratic problems in CPLEX. Operations Research, 70(6):3303–3320, 2022.Google Scholar
Borosh, I. and Treybig, L. B.. Bounds on positive integral solutions of linear Diophantine equations. Proceedings of the American Mathematical Society, 55(2):299–304, 1976.CrossRefGoogle Scholar
Brearley, A., Mitra, G., and Williams, H.. Analysis of mathematical programming problems prior to applying the simplex algorithm. Mathematical Programming, 8:54–83, 1975.Google Scholar
Burkard, R., DellAmico, M., and Martello, S.. Assignment Problems. SIAM, 2009.Google Scholar
Bussieck, M. R., Drud, A. S., and Meeraus, A.. MINLPLib – a collection of test models for mixed-integer nonlinear programming. INFORMS Journal on Computing, 15(1):114–119, 2003.Google Scholar
Cappart, Q., Chételat, D., Khalil, E. B. et al. Combinatorial optimization and reasoning with graph neural networks. In IJCAI, pages 4348–4355, 2021.Google Scholar
Cappart, Q., Chételat, D., Khalil, E. B. et al. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24:1–61, 2023.Google Scholar
Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., and Pokutta, S.. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 34:24235–24246, 2021.Google Scholar
Christophel, P. M.. An improved heuristic for the MOPS mixed integer programming solver. Diploma thesis, Universität Paderborn, 2005.Google Scholar
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C.. Introduction to Algorithms. MIT Press, 2001.Google Scholar
D’Ambrosio, C., Frangioni, A., Liberti, L., and Lodi, A.. Experiments with a feasibility pump approach for nonconvex MINLPs. In Festa, P., editor, Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 350–360. Springer, 2010.Google Scholar
D’Ambrosio, C., Frangioni, A., Liberti, L., and Lodi, A.. A storm of feasibility pumps for nonconvex MINLP. Mathematical Programming, 136:375–402, 2012.Google Scholar
Danna, E., Rothberg, E., and Pape, C. L.. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, 102(1):71–90, 2004.Google Scholar
De Santis, M., Lucidi, S., and Rinaldi, F.. A new class of functions for measuring solution integrality in the feasibility pump approach. SIAM Journal on Optimization, 23(3):1575–1606, 2013.Google Scholar
De Santis, M., Lucidi, S., and Rinaldi, F.. Feasibility pump-like heuristics for mixed integer problems. Discrete Applied Mathematics, 165:152–167, 2014.Google Scholar
Dey, S. S., Iroume, A., Molinaro, M., and Salvagnin, D.. Improving the randomization step in feasibility pump. SIAM Journal on Optimization, 28(1):355–378, 2018.Google Scholar
Ding, J.-Y., Zhang, C., Shen, L. et al. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1452–1459, 2020.Google Scholar
Duran, M. A. and Grossmann, I. E.. An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming, 36(3):307–339, 1986.Google Scholar
Eckstein, J. and Nediak, M.. Pivot, cut, and dive: A heuristic for 0–1 mixed integer programming. Journal of Heuristics, 13(5):471–503, 2007.Google Scholar
Faaland, B. H. and Hillier, F. S.. Interior path methods for heuristic integer programming procedures. Operations Research, 27:1069–1087, 1979.Google Scholar
Feo, T. A. and Resende, M. G. C.. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.CrossRefGoogle Scholar
FICO Xpress Optimizer. www.fico.com/en/products/fico-xpressoptimization.Google Scholar
Fischetti, M., Glover, F., and Lodi, A.. The feasibility pump. Mathematical Programming, 104(1):91–104, 2005.Google Scholar
Fischetti, M. and Lodi, A.. Local branching. Mathematical Programming, 98(1–3):23–47, 2003.Google Scholar
Fischetti, M. and Lodi, A.. Repairing MIP infeasibility through local branching. Computers & Operations Research, 35(5):1436–1445, 2008.Google Scholar
Fischetti, M. and Monaci, M.. Branching on nonchimerical fractionalities. Operations Research Letters, 40(3):159–164, 2012.Google Scholar
Fischetti, M. and Monaci, M.. Proximity search for 0-1 mixed-integer convex programming. Journal of Heuristics, 20(6):709–731, 2014.CrossRefGoogle Scholar
Fischetti, M. and Salvagnin, D.. Feasibility pump 2.0. Mathematical Programming Computation, 1:201–222, 2009.Google Scholar
Ford, L. R. and Fulkerson, D. R.. Maximal flow through a network. Canadian Journal of Mathematics, 8(3):399–404, 1956.CrossRefGoogle Scholar
Frank, M. and Wolfe, P.. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2):95–110, 1956.Google Scholar
Gamrath, G., Berthold, T., Heinz, S., and Winkler, M.. Structure-driven fix-andpropagate heuristics for mixed integer programming. Mathematical Programming Computation, 11:675–702, 2019.Google Scholar
Gardi, F.. Toward a mathematical programming solver based on local search. Habilitation thesis, Université Pierre et Marie Curie, 2013.Google Scholar
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A.. Exact combinatorial optimization with graph convolutional neural networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 15580–15592. Curran Associates, 2019.Google Scholar
Gauthier, J.-M. and Ribière, G.. Experiments in mixed-integer linear programming using pseudo-costs. Mathematical Programming, 12(1):26–47, 1977.CrossRefGoogle Scholar
Geißler, B., Morsi, A., Schewe, L., and Schmidt, M.. Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps. SIAM Journal on Optimization, 27(3):1611–1636, 2017.Google Scholar
Ghosh, S.. DINS, a MIP improvement heuristic. In Fischetti, M. and Williamson, D. P., editors, Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Proceedings, volume 4513 of Lecture Notes in Computer Science, pages 310–323. Springer, 2007.Google Scholar
Ghosh, S. and Hayward, R. B.. Pivot and Gomory cut: A MIP feasibility heuristic. Technical report, University of Alberta, 2010.Google Scholar
Gleixner, A., Gottwald, L., and Hoen, A.. Papilo: A parallel presolving library for integer and linear programming with multiprecision support. INFORMS Journal on Computing, 35(6):1329–1341, 2022.CrossRefGoogle Scholar
Glover, F.. Tabu search – part I. ORSA Journal on Computing, 1:190–206, 1989.Google Scholar
Glover, F. W. and Kochenberger, G. A., editors. Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science. Kluwer / Springer, 2003.Google Scholar
Gomory, R. E.. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275–278, 1958.Google Scholar
Gomory, R. E.. An algorithm for the mixed integer problem. Technical report, RAND Corporation, 1960.Google Scholar
Gondzio, J.. Presolve analysis of linear programs prior to applying an interior point method. INFORMS Journal on Computing, 9:73–91, 1997.Google Scholar
Goodfellow, I., Bengio, Y., and Courville, A.. Deep Learning. MIT Press, 2016.Google Scholar
Graver, J. E.. On the foundations of linear and integer linear programming I. Mathematical Programming, 9(1):207–226, 1975.Google Scholar
Gupta, P., Gasse, M., Khalil, E., et al. Hybrid models for learning to branch. Advances in Neural Information Processing Systems, 33:18087–18097, 2020.Google Scholar
Gurobi optimization. www.gurobi.com/.Google Scholar
Halbig, K., Hoen, A., Gleixner, A., Witzig, J., and Weninger, D.. A diving heuristic for mixed-integer problems with unbounded semi-continuous variables. arXiv preprint arXiv:2403.19411, 2024.Google Scholar
Hanafi, S., Lazić, J., and Mladenović, N.. Variable neighbourhood pump heuristic for 0-1 mixed integer programming feasibility. Electronic Notes in Discrete Mathematics, 36(0):759–766, 2010.CrossRefGoogle Scholar
Hansen, P. and Jaumard, B.. Reduction of indefinite quadratic programs to bilinear programs. Journal of Global Optimization, 2(1):4160, 1992.Google Scholar
Haralick, R. M. and Elliott, G. L.. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3):263–313, 1980.CrossRefGoogle Scholar
Haus, U.-U., Köppe, M., and Weismantel, R.. The integral basis method for integer programming. Mathematical Methods of Operations Research, 53(3):353–361, 2001.CrossRefGoogle Scholar
Hendel, G.. Empirical analysis of solving phases in mixed integer programming. Master’s thesis, Technische Universität Berlin, 2014.Google Scholar
Hendel, G.. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation, 14(2):185–221, 2022.Google Scholar
Hendel, G., Miltenberger, M., and Witzig, J.. Adaptive algorithmic behavior for solving mixed integer programs using bandit algorithms. In Fortz, B. and Labbé, M., editors, Operations Research Proceedings 2018, pages 513–519, 2019.Google Scholar
Hillier, F. S.. Efficient heuristic procedures for integer linear programming with an interior. Operations Research, 17:600–637, 1969.CrossRefGoogle Scholar
Hoffman, A. J., Mannos, M., Sokolowsky, D., and Wiegmann, N. A.. Computational experience in solving linear programs. Journal of the Society for Industrial and Applied Mathematics, 1(1):17–33, 1953.Google Scholar
Hoffman, K. L. and Padberg, M.. Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6):657–776, 1993.Google Scholar
, J. N. Hooker. Integrated Methods for Optimization. Springer, 2007.Google Scholar
Howard, R. A.. Dynamic Programming and Markov Processes. MIT Press, 1960.Google Scholar
Huang, T., Ferber, A., Tian, Y., Dilkina, B., and Steiner, B.. Local branching relaxation heuristics for integer linear programs. In Cire, A. A., editor, International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 96–113. Springer, 2023.Google Scholar
Ibaraki, T., Ohashi, T., and Mine, H.. A heuristic algorithm for mixed-integer programming problems. Mathematical Programming Study, 2:115–136, 1974.Google Scholar
IBM ILOG CPLEX Optimizer. www-01.ibm.com/software/integration/optimization/cplex-optimizer/.Google Scholar
Junttila, T. and Kaski, P.. Engineering an efficient canonical labeling tool for large and sparse graphs. In Applegate, D., Brodal, G. S., Panario, D., and Sedgewick, R., editors, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pages 135–149. SIAM, 2007.Google Scholar
Karp, R.. Reducibility among combinatorial problems. In Miller, R. and Thatcher, J., editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.Google Scholar
Khalil, E. B., Dilkina, B., Nemhauser, G. L., Ahmed, S., and Shao, Y.. Learning to run heuristics in tree search. In Proceedings of the Twenty-sixth International Joint Conference on Artificial Intelligence, pages 659–666, 2017.Google Scholar
Khalil, E. B., Morris, C., and Lodi, A.. MIP-GNN: A data-driven framework for guiding combinatorial solvers. In Rousseau, L.-M. and Stergiou, K., editors, Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219–10227, 2022.Google Scholar
Koch, T., Achterberg, T., Andersen, E. et al. MIPLIB 2010. Mathematical Programming Computation, 3(2):103–163, 2011.Google Scholar
Kotary, J., Fioretto, F., Van Hentenryck, P., and Wilder, B.. End-to-end constrained optimization learning: A survey. In Zho, Z.-H., editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 4475–4482, 2021.Google Scholar
Land, A. H. and Doig, A. G.. An automatic method of solving discrete programming problems. Econometrica, 28(3):497–520, 1960.Google Scholar
Letchford, A. N. and Lodi, A.. Primal cutting plane algorithms revisited. Mathematical Methods of Operations Research, 56(1):67–81, 2002.Google Scholar
Liberti, L., Mladenović, N., and Nannicini, G.. A recipe for finding good solutions to MINLPs. Mathematical Programming Computation, 3:349–390, 2011.Google Scholar
Liberti, L., Nannicini, G., and Mladenović, N.. A good recipe for solving MINLPs. In Maniezzo, V., Stützle, T., and Voß, S., editors, Matheuristics, volume 10 of Annals of Information Systems, pages 231–244. Springer, 2010.Google Scholar
Lin, P., Cai, S., Zou, M., and Lin, J.. New characterizations and efficient local search for general integer linear programming. arXiv preprint arXiv:2305.00188, 2024.Google Scholar
Liu, D., Fischetti, M., and Lodi, A.. Learning to search in local branching. In Sycara, K., Honaver, V., and Spaan, M., editors, Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):3796–3803, 2022.Google Scholar
Liu, D., Fischetti, M., and Lodi, A.. Revisiting local branching with a machine learning lens. arXiv preprint arXiv:2112.02195, 2022.Google Scholar
Localsolver: News. www.localsolver.com/news.html?id=32. Accessed July 30, 2014.Google Scholar
Lodi, A.. Mixed integer programming computation. In Jünger, M., Liebling, T. M., Naddef, D., Nemhauser, G. L., Pulleyblank, W. R., Reinelt, G., Rinaldi, G., and Wolsey, L. A., editors, 50 Years of Integer Programming 1958–2008, pages 619–645. Springer, 2010.Google Scholar
Lodi, A. and Tramontani, A.. Performance variability in mixed-integer programming. In Theory Driven by Influential Applications, pages 1–12. INFORMS, 2013.Google Scholar
Lodi, A. and Zarpellon, G.. On learning and branching: A survey. TOP, 25:207–236, 2017.Google Scholar
Løkketangen, A., Jörnsten, K., and Storøy, S.. Tabu search within a pivot and complement framework. International Transactions in Operational Research, 1(3):305–316, 1994.Google Scholar
Lourenço, H. R., Martin, O. C., and Stützle, T.. Iterated local search: Framework and applications. In Glover, F. and Kochenberger, G., editors, Handbook of Metaheuristics, volume 57, pages 321–353. Kluwer Academic Publishers, 2002.Google Scholar
Luteberget, B. and Sartor, G.. Feasibility jump: An LP-free Lagrangian MIP heuristic. Mathematical Programming Computation, 15:365–388, 2023.Google Scholar
Mahmoud, H. and Chinneck, J. W.. Achieving MILP feasibility quickly using general disjunctions. Computers & Operations Research, 40(8):2094–2102, 2013.Google Scholar
Maniezzo, V., Boschetti, M. A., and Stützle, T.. Matheuristics, Algorithms and Implementations. Springer, 2021.Google Scholar
Maros, I.. Computational Techniques of the Simplex Method. Kluwer Academic Publishers, 2002.Google Scholar
Martello, S. and Toth, P.. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.Google Scholar
Martin, A.. Integer programs with block structure. Habilitation thesis, Preprint SC 99-03, Zuse Institute Berlin, 1999.Google Scholar
Mexi, G., Berthold, T., and Salvagnin, D.. Using multiple reference vectors and objective scaling in the feasibility pump. EURO Journal on Computational Optimization, 11:1–18, 2023.Google Scholar
Mexi, G., Besançon, M., Bolusani, S. et al. Scylla: A matrix-free fixpropagate-and-project heuristic for mixed-integer optimization. arXiv preprint arXiv:2307.03466, 2023.Google Scholar
Miplib 2017. http://miplib.zib.de.Google Scholar
Misener, R. and Floudas, C. A.. Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewiselinear and edge-concave relaxations. Mathematical Programming, 136:155–182, 2012.Google Scholar
Misener, R. and , C. A. Floudas. GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization, 57:3–50, 2013.Google Scholar
Mitchell, M.. An Introduction to Genetic Algorithms. MIT Press, 1996.Google Scholar
Moskewicz, M. H., Madigan, C. F., Zhao, Y., Zhang, L., and Malik, S.. Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th Design Automation Conference, pages 530–535. ACM, 2001.Google Scholar
Munguía, L.-M., Ahmed, S., Bader, D. A., Nemhauser, G. L., and Shao, Y.. Alternating criteria search: A parallel large neighborhood search algorithm for mixed integer programs. Computational Optimization and Applications, 69:1–24, 2018.Google Scholar
Nair, V., Bartunov, S., Gimeno, F. et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.Google Scholar
Nannicini, G. and Belotti, P.. Rounding-based heuristics for nonconvex MINLPs. Mathematical Programming Computation, 4(1):1–31, 2012.Google Scholar
Nannicini, G., Belotti, P., and Liberti, L.. A local branching heuristic for MINLPs. arXiv preprint arXiv:0812.2188, 2008.Google Scholar
Naoum-Sawaya, J.. Recursive central rounding for mixed integer programs. Computers & Operations Research, 43:191–200, 2014.CrossRefGoogle Scholar
Naoum-Sawaya, J. and Elhedhli, S.. An interior point cutting plane heuristic for mixed integer programming. Computers & Operations Research, 38:1335–1341, 2011.Google Scholar
Nemhauser, G. L. and Wolsey, L. A.. Integer and Combinatorial Optimization. Wiley, 1988.Google Scholar
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L.. An analysis of approximations for maximizing submodular set functions – I. Mathematical Programming, 14(1):265–294, 1978.Google Scholar
Neumann, C., Schwarze, S., Stein, O., and Müller, B.. Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization. EURO Journal on Computational Optimization, 10:100051, 2022.Google Scholar
Neumann, C., Stein, O., and Sudermann-Merx, N.. A feasible rounding approach for mixed-integer optimization problems. Computational Optimization and Applications, 72:309–337, 2019.Google Scholar
Ostrowski, J., Linderoth, J., Rossi, F., and Smriglio, S.. Orbital branching. Mathematical Programming, 126(1):147–178, 2011.Google Scholar
Pal, A. and Charkhgard, H.. A feasibility pump and local search based heuristic for bi-objective pure integer linear programming. INFORMS Journal on Computing, 31(1):115–133, 2019.Google Scholar
Patel, J. and Chinneck, J. W.. Active-constraint variable ordering for faster feasibility of mixed integer linear programs. Mathematical Programming, 110:445–474, 2007.Google Scholar
Pryor, J. and Chinneck, J. W.. Faster integer-feasibility in mixed-integer linear programs by branching to force change. Computers & Operations Research, 38(8):1143–1152, 2011.Google Scholar
Quesada, I. and Grossmann, I. E.. An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Computers & Chemical Engineering, 16(10):937–947, 1992.Google Scholar
Rossi, F., van Beek, P., and Walsh, T., editors. The Handbook of Constraint Programming. Elsevier, 2006.Google Scholar
Rothberg, E.. An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing, 19(4):534–541, 2007.CrossRefGoogle Scholar
Saltzman, R. M. and Hillier, F. S.. A heuristic ceiling point algorithm for general integer linear programming. Management Science, 38(2):263–283, 1992.Google Scholar
Salvagnin, D.. Detecting and exploiting permutation structures in MIPS. In Simonis, H., editor, Proceedings of CPAIOR 2014, volume 8451 of Lecture Notes in Computer Science, pages 29–44. Springer, 2014.Google Scholar
Salvagnin, D., Roberti, R., and Fischetti, M.. A fix-propagate-repair heuristic for mixed integer programming. Technical report, DEI, University of Padova, 2023.Google Scholar
Savelsbergh, M. W. P.. Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6:445–454, 1994.Google Scholar
Scavuzzo, L., Aardal, K., Lodi, A., and Yorke-Smith, N.. Machine learning augmented branch and bound for mixed integer linear programming. arXiv preprint arXiv:2402.05501, 2024.Google Scholar
Schöning, U.. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceedings of 40th Annual Symposium on Foundations of Computer Science, pages 410–414. IEEE, 1999.CrossRefGoogle Scholar
Schulte, C.. Programming constraint services. PhD thesis, Universität des Saarlandes, Germany, 2000.Google Scholar
Schulte, C. and Stuckey, P. J.. Speeding up constraint propagation. In Wallace, M., editor, Principles and Practice of Constraint Programming – CP 2004, 10th International Conference, volume 3258 of Lecture Notes in Computer Science, pages 619–633. Springer, 2004.Google Scholar
Sharma, S.. Mixed-integer nonlinear programming heuristics applied to a shale gas production optimization problem. Master’s thesis, Norwegian University of Science and Technology, 2013.Google Scholar
Sharma, S., Knudsen, B. R., and Grimstad, B.. Towards an objective feasibility pump for convex MINLPS. Computational Optimization and Applications, 63:737–753, 2016.Google Scholar
Shaw, P.. Using constraint programming and local search methods to solve vehicle routing problems. In Maher, M. and Puget, J.-F., editors, Principles and Practice of Constraint Programming – CP98, volume 1520 of Lecture Notes in Computer Science, pages 417–431. Springer, 1998.Google Scholar
Smith, K. A.. Neural networks for combinatorial optimization: A review of more than a decade of research. INFORMS Journal on Computing, 11:15–34, 1999.Google Scholar
Sonnevend, G.. An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In Prékopa, A., Szelezsáan, J., and Strazicky, B., editors, System Modelling and Optimization, volume 84 of Lecture Notes in Control and Information Sciences, pages 866–875. Springer, 1986.Google Scholar
Sonnevend, G.. Applications of the notion of analytic center in approximation (estimation) problems. Journal of Computational and Applied Mathematics, 28:349–358, 1989.Google Scholar
SoPlex. An open source LP solver implementing the revised simplex algorithm. http://soplex.zib.de/.Google Scholar
Streeter, M.. Using online algorithms to solve NP-hard problems more efficiently in practice. PhD thesis, Carnegie Mellon University, 2007.Google Scholar
Sutton, R. S. and Barto, A. G.. Reinforcement Learning: An Introduction. MIT Press, 1998.Google Scholar
Turner, M., Berthold, T., Besanon, M., and Koch, T.. Cutting plane selection with analytic centers and multiregression. In Proceedings of CPAIOR 2023, volume 13884, pages 52–68, 2023.Google Scholar
Ugray, Z., Lasdon, L., Plummer, J. et al. Scatter search and local NLP solvers: A multistart framework for global optimization. INFORMS Journal on Computing, 19(3):328–340, 2007.Google Scholar
Vigerske, S.. Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. PhD thesis, Humboldt-Universität zu Berlin, 2012.Google Scholar
Wallace, C.. ZI round, a MIP rounding heuristic. Journal of Heuristics, 16(5):715–722, 2010.Google Scholar
Weismantel, R.. Test sets of integer programs. Mathematical Methods of Operations Research, 47(1):1–37, 1998.Google Scholar
Witzig, J. and Gleixner, A.. Conflict-driven heuristics for mixed integer programming. INFORMS Journal on Computing, 33(2):706–720, 2021.Google Scholar
Wunderling, R.. Paralleler und Objektorientierter Simplex-Algorithmus. PhD thesis, Technische Universität Berlin, 1996.Google Scholar
Young, R. D.. A simplified primal (all-integer) integer programming algorithm. Operations Research, 16(4):750–782, 1968.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×