×

zbMATH — the first resource for mathematics

Generation techniques for linear programming instances with controllable properties. (English) Zbl 1452.90214
Summary: This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable of generating any feasible bounded linear program, and that parameterised generators and search algorithms using this approach generate only feasible bounded instances. Our results demonstrate that controlled generation and instance space search using this method achieves feature diversity more effectively than using a direct representation.
MSC:
90C05 Linear programming
68W40 Analysis of algorithms
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Asahiro, Y.; Iwama, K.; Miyano, E., Random generation of test instances with controlled attributes, DIMACS Ser. Discrete Math. Theor. Comput. Sci., 26, 377-393 (1996) · Zbl 0864.90089
[2] Bischl, B.; Kerschke, P.; Kotthoff, L.; Lindauer, M.; Malitsky, Y.; Fréchette, A.; Hoos, H.; Hutter, F.; Leyton-Brown, K.; Tierney, K.; Vanschoren, J., ASlib: a benchmark library for algorithm selection, Artif. Intell., 237, 41-58 (2016) · Zbl 1357.68202
[3] Bixby, R.E.: A brief history of linear and mixed-integer programming computation. Documenta Mathematica—Extra Volume ISMP pp. 107-121 (2012) · Zbl 1270.90003
[4] Bowly, S.: simonbowly/lp-generators: v0.2-beta (Version v0.2-beta). Zenodo. doi:10.5281/zenodo.1220448 (2018)
[5] Chakraborty, S.; Choudhury, PP, A statistical analysis of an algorithm’s complexity, Appl. Math. Lett., 13, 5, 121-126 (2000) · Zbl 0965.68139
[6] Cotta, C.; Moscato, P., A mixed evolutionary-statistical analysis of an algorithm’s complexity, Appl. Math. Lett., 16, 1, 41-47 (2003) · Zbl 1081.68012
[7] Culberson, J.: Graph Coloring Page. http://webdocs.cs.ualberta.ca/ joe/Coloring/ (2010). Accessed 03 April 2017
[8] Drugan, M.M.: Instance generator for the quadratic assignment problem with additively decomposable cost function. In: 2013 IEEE Congress on Evolutionary Computation, pp. 2086-2093. IEEE (2013)
[9] Gao, W., Nallaperuma, S., Neumann, F.: Feature-based diversity optimization for problem instance classification. In: International Conference on Parallel Problem Solving from Nature, pp. 869-879. Springer (2016)
[10] Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T., Bastubbe, M., Berthold, T., Christophel, P.M., Jarck, K., Koch, T., Linderoth, J., Lübbecke, M., Mittelmann, H.D., Ozyurt, D., Ralphs, T.K., Salvagnin, D., Shinano, Y.: MIPLIB 2017. https://miplib.zib.de/ (2018). Accessed 30 July 2019
[11] Hall, N.G., Posner, M.E.: The generation of experimental data for computational testing in optimization. In: Experimental Methods for the Analysis of Opimization Algorithms, pp. 73-101. Springer, Berlin Heidelberg (2010) · Zbl 1206.90246
[12] Hill, R.; Moore, J.; Hiremath, C.; Cho, Y., Test problem generation of binary knapsack problem variants and the implications of their use, Int. J. Oper. Quant. Manag., 18, 2, 105-128 (2011)
[13] Hill, RR; Reilly, CH, The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance, Manage. Sci., 46, 2, 302-317 (2000) · Zbl 1231.90323
[14] Hooker, JN, Needed: an empirical science of algorithms, Oper. Res., 42, 2, 201-212 (1994) · Zbl 0805.90119
[15] Hooker, JN, Testing heuristics: we have it all wrong, J. Heuristics, 1, 1, 33-42 (1995) · Zbl 0853.68155
[16] Hutter, F.; Hoos, HH; Leyton-Brown, K.; Stützle, T., ParamILS: an automatic algorithm configuration framework, J. Artif. Intell. Res., 36, 1, 267-306 (2009) · Zbl 1192.68831
[17] Hutter, F.; Xu, L.; Hoos, HH; Leyton-Brown, K., Algorithm runtime prediction: methods & evaluation, Artif. Intell., 206, 1, 79-111 (2014) · Zbl 1334.68185
[18] Kadioglu, S.; Malitsky, Y.; Sellmann, M.; Tierney, K., ISAC-instance-specific algorithm configuration, ECAI, 215, 751-756 (2010)
[19] Klingman, D.; Napier, A.; Stutz, J., NETGEN: a program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems, Manage. Sci., 20, 5, 814-821 (1974) · Zbl 0303.90042
[20] 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: mixed integer programming library version 5, Math. Program. Comput., 3, 2, 103-163 (2011)
[21] Leyton-Brown, K.; Nudelman, E.; Shoham, Y., Empirical hardness models: methodology and a case study on combinatorial auctions, J. ACM, 56, 4, 1-52 (2009) · Zbl 1325.68110
[22] Lin, S.; Kernighan, BW, An effective heuristic algorithm for the traveling-salesman problem, Oper. Res., 21, 2, 498-516 (1973) · Zbl 0256.90038
[23] McGeoch, CC, Feature article—toward an experimental method for algorithm simulation, INFORMS J. Comput., 8, 1, 1-15 (1996)
[24] Pilcher, MG; Rardin, RL, Partial polyhedral description and generation of discrete optimization problems with known optima, Nav. Res. Logist. (NRL), 39, 6, 839-858 (1992) · Zbl 0795.90051
[25] Rice, JR, The algorithm selection problem, Adv. Comput., 15, 65-118 (1976)
[26] Smith-Miles, K.; Bowly, S., Generating new test instances by evolving in instance space, Comput. Oper. Res., 63, 102-113 (2015) · Zbl 1349.68325
[27] Smith-Miles, K.; Lopes, L., Measuring instance difficulty for combinatorial optimization problems, Comput. Oper. Res., 39, 875-889 (2012) · Zbl 1251.90339
[28] Todd, MJ, Probabilistic models for linear programming, Math. Oper. Res., 16, 4, 671-693 (1991) · Zbl 0751.90056
[29] Van Hemert, JI, Evolving combinatorial problem instances that are difficult to solve, Evol. Comput., 14, 4, 433-462 (2006)
[30] Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Hydra-MIP: automated algorithm configuration and selection for mixed integer programming. In: RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence (IJCAI), pp. 16-30 (2011)
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.