Abstract
“Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex” This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.
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
Achterberg, T. (2010). LP basis selection and cutting planes.
Baena, D., & Castro, J. (2011). Using the analytic center in the feasibility pump. Operations Research Letters, 39(5), 310–317.
Bajgiran, O. S., Cire, A. A., & Rousseau, L. -M. (2017). A first look at picking dual variables for maximizing reduced cost fixing. In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 221–228). Springer.
Ben-Ameur, W., & Neto, J. (2007). Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks, 49(1), 3–17.
Berthold, T. (2013). Measuring the impact of primal heuristics. Operations Research Letters, 41(6), 611–614.
Berthold, T., Farmer, J., Heinz, S., & Perregaard, M. (2017). Parallelization of the FICO xpress-optimizer. Optimization Methods and Software, 1–12.
Boland, N. I., Eberhard, A. C., Engineer, F. G., Fischetti, M., Savelsbergh, M. W. P., & Tsoukalas, A. (2014). Boosting the feasibility pump. Mathematical Programming Computation, 6(3), 255–279.
Fischetti, M., Glover, F., & Lodi, A. (2005). The feasibility pump. Mathematical Programming, 104(1), 91–104.
Fischetti, M., & Monaci, M. (2014). Proximity search for 0–1 mixed-integer convex programming. Journal of Heuristics, 20(6), 709–731.
Fischetti, M., & Salvagnin, D. (2010). An in-out approach to disjunctive optimization. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming (pp. 136–140). Springer.
Goffin, J. -L., & Vial, J. -P. (2002). Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optimization Methods and Software, 17(5), 805–867.
Gondzio, J., Du Merle, O., Sarkissian, R., & Vial, J. -P. (1996). ACCPM–a library for convex optimization based on an analytic center cutting plane method. European Journal of Operational Research, 94(1), 206–211.
Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing (pp. 302–311). ACM.
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R. E., et al. (2011). MIPLIB 2010. Mathematical Programming Computation, 3(2), 103–163.
Laundy, R., Perregaard, M., Tavares, G., Tipi, H., & Vazacopoulos, A. (2009). Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study. INFORMS Journal on Computing, 21(2), 304–313.
Mészáros, C. (1999). The bpmpd interior point solver for convex quadratic problems. Optimization Methods and Software, 11(1–4), 431–449.
Mittelmann, H. Benchmarks for optimization software: Feasibility benchmark. http://plato.asu.edu/bench.html.
Naoum-Sawaya, J. (2013). Recursive central rounding for mixed integer programs. Computers and Operations Research.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley.
Nesterov, Y., & Nemirovski, A. (1994). Interior-point polynomial algorithms in convex programming., Studies in applied and numerical mathematics Philadelphia: Society for Industrial and Applied Mathematics.
Sonnevend, G. (1986). An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In A. Prékopa, J. Szelezsáan, & B. Strazicky (Eds.), System modelling and optimization (Vol. 84, pp. 866–875)., Lecture notes in control and information sciences Berlin: Springer.
Sonnevend, G. (1989). Applications of the notion of analytic center in approximation (estimation) problems. Journal of Computational and Applied Mathematics, 28, 349–358.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Berthold, T., Perregaard, M., Mészáros, C. (2018). Four Good Reasons to Use an Interior Point Solver Within a MIP Solver. In: Kliewer, N., Ehmke, J., Borndörfer, R. (eds) Operations Research Proceedings 2017. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-89920-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-89920-6_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-89919-0
Online ISBN: 978-3-319-89920-6
eBook Packages: Business and ManagementBusiness and Management (R0)