×

zbMATH — the first resource for mathematics

A feasible rounding approach for mixed-integer optimization problems. (English) Zbl 1414.90239
Summary: We introduce granularity as a sufficient condition for the consistency of a mixed-integer optimization problem, and show how to exploit it for the computation of feasible points: For optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixed-integer problem. Thus, the resulting feasible rounding approach is deterministic and even efficient, i.e., it computes feasible points in polynomial time. The optimization problems appearing in the feasible rounding approaches have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics, as long as the problem is granular. For instance, the computational cost of our approach always corresponds to merely a single step of the feasibility pump. A computational study on optimization problems from the MIPLIB libraries demonstrates that granularity may be expected in various real world applications. Moreover, a comparison with Gurobi indicates that state of the art software does not always exploit granularity. Hence, our algorithms do not only possess a worst-case complexity advantage, but can also improve the CPU time needed to solve problems from practice.

MSC:
90C11 Mixed integer programming
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optim., 4, 77-86, (2007) · Zbl 1170.90443
[2] Achterberg, T., Bixby, R., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming, Technical Report pp. 16-44, ZIB
[3] Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Oper. Res. Lett., 34, 361-372, (2006) · Zbl 1133.90300
[4] Baum, SP; Trotter, LE, Integer rounding for polymatroid and branching optimization problems, SIAM J. Algebraic Discrete Methods, 2, 416-425, (1981) · Zbl 0518.90058
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172
[6] Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 63-76, (2007) · Zbl 1169.90415
[7] Berthold, T., RENS—the optimal rounding, Math. Program. Comput., 6, 33-54, (2014) · Zbl 1304.90147
[8] Berthold, T.; Gleixner, AM, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144, 315-346, (2014) · Zbl 1291.90144
[9] Boland, NL; Eberhard, AC; Engineer, FG; Fischetti, M.; Savelsbergh, MWP; Tsoukalas, A., Boosting the feasibility pump, Math. Program. Comput., 6, 255-279, (2014) · Zbl 1323.65065
[10] Bonami, P.; Gonçalves, JPM, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51, 729-747, (2012) · Zbl 1241.90189
[11] Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, New York (2014) · Zbl 1307.90001
[12] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 91-104, (2005) · Zbl 1077.90039
[13] Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Math. Program. Comput., 1, 201-222, (2009) · Zbl 1180.90208
[14] Hillier, FS, Efficient heuristic procedures for integer linear programming with an interior, Oper. Res., 17, 600-637, (1969) · Zbl 0176.49902
[15] Kannan, R.; Bachem, A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput., 8, 499-507, (1979) · Zbl 0446.65015
[16] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, RE; Danna, E.; Gamrath, G.; Gleixner, AM; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, DE; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 103-163, (2011)
[17] Nannicini, G.; Belotti, P., Rounding-based heuristics for nonconvex MINLPs, Math. Program. Comput., 4, 1-31, (2012) · Zbl 1257.90059
[18] Neumann, C., Stein, O., Sudermann-Merx, N.: Granularity in nonlinear mixed-integer optimization. Optimization Online, Preprint ID 2017-12-6367 (2017)
[19] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998) · Zbl 0970.90052
[20] Stein, O., Error bounds for mixed integer linear optimization problems, Math. Program., 156, 101-123, (2016) · Zbl 1345.90061
[21] Stein, O., Error bounds for mixed integer nonlinear optimization problems, Optim. Lett., 10, 1153-1168, (2016) · Zbl 1377.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.