×

Solving MIPs via scaling-based augmentation. (English) Zbl 1506.90171

Summary: Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a feasible solution is iteratively augmented to a better solution or proved to be optimal. It is well known that the performance of these methods, i.e., number of iterations needed, can theoretically be improved by scaling methods. We extend these results by an improved and extended convergence analysis, which shows that bit scaling and geometric scaling theoretically perform identically well in the worst case for 0/1 polytopes, as well as show that in some cases, geometric scaling can outperform bit scaling arbitrarily, leading to the first strong separation between these two methods.
We also investigate the performance of implementations of these methods, where the augmentation directions are computed by a MIP solver. It turns out that the number of required iterations is low in most cases. While scaling methods usually do not improve the performance for easier problems, in the case of hard mixed-integer optimization problems they allow to compute solutions of very good quality and are often superior.

MSC:

90C11 Mixed integer programming
90C05 Linear programming
90C10 Integer programming

Software:

MIPLIB; SCIP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Wallacher, C.; Zimmermann, U., A combinatorial interior point method for network flow problems, Math. Program., 56, 1-3, 321-335, (1992) · Zbl 0794.90017
[2] Orlin, J. B.; Ahuja, R. K., New scaling algorithms for the assignment and minimum mean cycle problems, Math. Program., 54, 1-3, 41-56, (1992) · Zbl 0764.90059
[3] Graver, J. E., On the foundations of linear and integer linear programming I, Math. Program., 9, 1, 207-226, (1975) · Zbl 0323.90035
[4] Scarf, H. E., Test sets for integer programs, Math. Program., 79, 1-3, 355-368, (1997) · Zbl 0887.90124
[5] De Loera, J. A.; Hemmecke, R.; Köppe, M., (Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS-SIAM Series on Optimization, vol. 14, (2013), SIAM) · Zbl 1401.90012
[6] J.A. De Loera, R. Hemmecke, J. Lee, Augmentation in linear and integer linear programming, 2014. Preprint arXiv:1408.3518; J.A. De Loera, R. Hemmecke, J. Lee, Augmentation in linear and integer linear programming, 2014. Preprint arXiv:1408.3518 · Zbl 1330.90053
[7] Hemmecke, R.; Köppe, M.; Lee, J.; Weismantel, R., Nonlinear integer programming, (Jünger, M.; Liebling, T. M.; Naddef, D.; Nemhauser, G. L.; Pulleyblank, W. R.; Reinelt, G.; Rinaldi, G.; Wolsey, L. A., 50 Years of Integer Programming 1958-2008 - from the Early Years To the State-of-the-Art, (2010), Springer), 561-618 · Zbl 1187.90270
[8] Onn, S., (Nonlinear Discrete Optimization: An Algorithmic Theory, Zurich Lectures in Advanced Mathematics, (2010), European Mathematical Society Publishing House) · Zbl 1219.90003
[9] Hemmecke, R.; Köppe, M.; Weismantel, R., Graver basis and proximity techniques for block-structured separable convex integer minimization problems, Math. Program., 145, 1-2, 1-18, (2014) · Zbl 1298.90057
[10] Hemmecke, R.; Onn, S.; Weismantel, R., A polynomial oracle-time algorithm for convex integer minimization, Math. Program., 126, 1, 97-117, (2011) · Zbl 1228.90055
[11] Lee, J.; Onn, S.; Romanchuk, L.; Weismantel, R., The quadratic graver cone, quadratic integer minimization, and extensions, Math. Program., 136, 2, 301-323, (2012) · Zbl 1280.90088
[12] Lee, J.; Onn, S.; Weismantel, R., On test sets for nonlinear integer maximization, Oper. Res. Lett., 36, 4, 439-443, (2008) · Zbl 1155.90434
[13] De Loera, J. A.; Hemmecke, R.; Köppe, M.; Weismantel, R., FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Math. Program., 115, 2, 273-290, (2008) · Zbl 1151.90029
[14] Bienstock, D., Approximately Solving Large-Scale Linear Programs. I. Strengthening Lower Bounds and Accelerating Convergence. CORC Report, (1999)
[15] Bienstock, D., (Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice, International Series in Operations Research & Management Science, vol. 53, (2002), Springer) · Zbl 1088.90001
[16] Plotkin, S. A.; Shmoys, D. B.; Tardos, É., Fast approximation algorithms for fractional packing and covering problems, Math. Oper. Res., 20, 2, 257-301, (1995) · Zbl 0837.90103
[17] Arora, S.; Hazan, E.; Kale, S., The multiplicative weights update method: a meta-algorithm and applications, Theory Comput., 8, 1, 121-164, (2012) · Zbl 1283.68414
[18] Letchford, A. N.; Lodi, A., An augment-and-branch-and-cut framework for mixed 0-1 programming, (Combinatorial Optimization—Eureka, You Shrink!, (2003), Springer), 119-133 · Zbl 1024.90506
[19] Fischetti, M.; Monaci, M., Proximity search for 0-1 mixed-integer convex programming, J. Heuristics, 20, 6, 709-731, (2014) · Zbl 1360.90173
[20] Schulz, A. S.; Weismantel, R., The complexity of generic primal algorithms for solving general integer programs, Math. Oper. Res., 27, 4, 681-692, (2002) · Zbl 1082.90072
[21] McCormick, S. T.; Shioura, A., Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks, Oper. Res. Lett., 27, 5, 199-207, (2000) · Zbl 1096.90543
[22] A.S. Schulz, R. Weismantel, G.M. Ziegler, 0/1-integer programming: Optimization and augmentation are equivalent, in: Algorithms -ESA ’95, Proceedings, 1995, pp. 473-483.; A.S. Schulz, R. Weismantel, G.M. Ziegler, 0/1-integer programming: Optimization and augmentation are equivalent, in: Algorithms -ESA ’95, Proceedings, 1995, pp. 473-483.
[23] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 2, 248-264, (1972) · Zbl 0318.90024
[24] Garg, N.; Koenemann, J., Faster and simpler algorithms for multicommodity flow and other fractional packing problems, SIAM J. Comput., 37, 2, 630-652, (2007) · Zbl 1137.90014
[25] Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 5, 877-898, (1976) · Zbl 0358.90053
[26] Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 1-3, 23-47, (2003) · Zbl 1060.90056
[27] Conn, A. R.; Gould, N. I.M.; Toint, P. L., Trust Region Methods, (2000), SIAM
[28] Schrijver, A., Theory of Linear and Integer Programming, (1986), Wiley · Zbl 0665.90063
[29] Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization, (1988), Wiley · Zbl 0652.90067
[30] Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, vol. 1, (1995), Elsevier · Zbl 0833.05001
[31] Frank, A.; Tardos, É., An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 1, 49-65, (1987) · Zbl 0641.90067
[32] Ben-Tal, A.; Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, (2001), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0986.90032
[33] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41, (2009) · Zbl 1171.90476
[34] SCIP. Solving Constraint Integer Programs, Version 3.2.0, 2015, http://scip.zib.de/; SCIP. Solving Constraint Integer Programs, Version 3.2.0, 2015, http://scip.zib.de/
[35] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R. E.; Danna, E.; Gamrath, G.; Gleixner, A. M.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, D. E.; Wolter, K., MIPLIB 2010: mixed integer programming library version 5, Math. Program. Comput., 3, 2, 103-163, (2011)
[36] Hansen, P.; Mladenović, N.; Urošević, D., Variable neighborhood search and local branching, Comput. Oper. Res., 33, 3034-3045, (2006) · Zbl 1086.90042
[37] S. Dash, A note on QUBO instances defined on Chimera graphs, 2013. Preprint arXiv:1306.1202; S. Dash, A note on QUBO instances defined on Chimera graphs, 2013. Preprint arXiv:1306.1202
[38] Dash, S.; Puget, J.-F., On quadratic unconstrained binary optimization problems defined on Chimera graphs, Optima, 98, 2-6, (2015)
[39] P. Le Bodic, J.W. Pavelka, M.E. Pfetsch, S. Pokutta, Solving MIPs via Scaling-based Augmentation. Technical Report 2015. arXiv:1509.03206; P. Le Bodic, J.W. Pavelka, M.E. Pfetsch, S. Pokutta, Solving MIPs via Scaling-based Augmentation. Technical Report 2015. arXiv:1509.03206 · Zbl 1506.90171
[40] Berthold, T., Measuring the impact of primal heuristics, Oper. Res. Lett., 41, 6, 611-614, (2013) · Zbl 1287.90037
[41] Berthold, T., Heuristic Algorithms in Global MINLP Solvers, (2014), TU Berlin, (Ph.D. thesis)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.