Improving solver performance through redundancy

Abstract

It is well known that hierarchies of mathematical programming formulations with different numbers of variables and constraints have a considerable impact regarding the quality of solutions obtained once these formulations are fed to a commercial solver. In addition, even if dimensions are kept the same, changes in formulations may largely influence solvability and quality of results. This becomes evident especially if redundant constraints are used. We propose a related framework for information collection based on these constraints. We exemplify by means of a well-known combinatorial optimization problem from the knapsack problem family, i.e., the multidimensional multiple-choice knapsack problem (MMKP). This incorporates a relationship of the MMKP to some generalized set partitioning problems. Moreover, we investigate an application in maritime shipping and logistics by means of the dynamic berth allocation problem (DBAP), where optimal solutions are reached from the root node within the solver.

Keywords

Erraticism / redundant constraints / multidimensional multiple-choice knapsack problem / dynamic berth allocation problem

References

[1] Aardal K.. Reformulation of capacitated facility location problems: how redundant information can help. Annals of Operations Research, 1998, 82: 289-308.

[2] Beaumont N.. Using mixed integer programming to design employee rosters. Journal of the Operational Research Society, 1997, 48(6): 585-590.

[3] Buhrkal K., Zuglian S., Ropke S., Larsen J., Lusby R.. Models for the discrete berth allocation problem: a computational comparison. Transportation Research Part E, 2011, 47: 461-473.

[4] Christensen C.G., Holst C.T.. Berth allocation in container terminals, 2008

[5] Cordeau J.-F., Laporte G., Legato P., Moccia L.. Models and tabu search heuristics for the berth-allocation problem. Transportation Science, 2005, 39(4): 526-538.

[6] Danna E.. Performance variability in mixed integer programming, 2008

[7] Dulá J.. Geometry of optimal value functions with applications to redundancy in linear programming. Journal of Optimization Theory and Applications, 1994, 81(1): 35-52.

[8] Elhedhli S., Gzara F.. Integrated design of supply chain networks with three echelons, multiple commodities and technology selection. IIE Transactions, 2008, 40(1): 31-44.

[9] Fischetti M., Monaci M.. On the role of randomness in exact tree search methods, 2012.

[10] Fischetti M., Lodi A., Monaci M., Salvagnin D., Tramontani A.. Tree search stabilization by random sampling, 2013.

[11] Fischetti M., Monaci M.. Exploiting erraticism in search. Operations Research, 2014, 62(1): 114-122.

[12] Geoffrion A. M.. Indexing in modeling languages for mathematical programming. Management Science, 1992, 38(3): 325-344.

[13] Greenberg H.. Consistency, redundancy, and implied equalities in linear systems. Annals of Mathematics and Artificial Intelligence, 1996, 17(1): 37-83.

[14] Hifi M., Michrafy M., Sbihi A.. A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem. Computational Optimization and Applications, 2006, 33(2-3): 271-285.

[15] Imai A., Nishimura E., Papadimitriou S.. The dynamic berth allocation problem for a container port. Transportation Research Part B, 2001, 35(4): 401-417.

[16] Karwan M., Lotfi V., Zionts S., Telgen J.. An introduction to redundancy. Redundancy in Mathematical Programming, Volume 206 of Lecture Notes in Economics and Mathematical Systems, pages 1-13, 1983

[17] Khan S.. Quality adaptation in a multisession multimedia system: model, algorithms and architecture, 1998

[18] Koch T., Achterberg T., Andersen E., Bastert O., Berthold T., Bixby R., Danna E., Gamrath G., Gleixner A., Heinz S., et al. MIPLIB 2010. Mathematical Programming Computation, 2011, 3(2): 103-163.

[19] Lalla-Ruiz E., Voß S.. POPMUSIC as a matheuristic for the berth allocation problem, 2014.

[20] Lodi A., Tramontani A.. Performance variability in mixed-integer programming, 2013.

[21] Martin R.K.. Large Scale Linear and Integer Optimization: A Unified Approach, 1999.

[22] Miyauchi A., Sukegawa N.. Redundant constraints in the standard formulation for the clique partitioning problem. Optimization Letters, 2015, 9(1): 199-207.

[23] Paulraj S., Sumathi P.. A comparative study of redundant constraints identification methods in linear programming problems, 2010.

[24] Sharma R., Mouli G., Verma M., Verma P.. Evaluating strong, weak and hybrid formulations of the single stage capacitated warehouse location problem. International Journal of Operational Research, 2014, 20(2): 156-179.

[25] Shojaei H., Basten T., Geilen M., Davoodi A.. A fast and scalable multidimensional multiple-choice knapsack heuristic. ACM Transactions on Design Automation of Electronic Systems, 2013, 18(4): 51:1-51:32.

[26] Telgen J.. Identifying redundancy in systems of linear constraints, 1983.

[27] Thompson G. L., Tonge F. M., Zionts S.. Techniques for removing nonbinding constraints and extraneous variables from linear programming problems. Management Science, 1966, 12(7): 588-608.

[28] Voß S., Lalla-Ruiz E.. A set-partitioning reformulation for the multidimensional multiple choice knapsack problem, 2015

[29] Wolsey L.A.. Integer Programming, 1998.

[30] Wu L., Hifi M.. An equivalent model for exactly solving the multiple-choice multidimensional knapsack problem. International Journal of Combinatorial Optimization Problems and Informatics, 2012, 3: 43-58.