A Computational Study Of Parametric Tabu Search For 01 Mixed Integer Programs

We present a computational study of parametric tabu search for solving 01 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems proposed by Glover [Glover F. Parametric tabu-search for mixed integer programs. Computers and Operations Research 2006; 33: 244994.]. This approach solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature. © 2010 Elsevier Ltd. All rights reserved.382464473Achterberg, T., Berthold, T., Improving the feasibility pump (2007) Discrete Optimization, 4, pp. 77-86Achterberg, T., Koch, T., Martin, A., (2003) The Mixed Integer Programming Library, , http://miplib.zib.deAchterberg, T., Koch, T., Martin, A., Branching rules revisited (2005) Operations Research Letters, 33, pp. 42-54Atamtrk, A., Savelsbergh, M.W.P., Integer-programming software systems (2005) Annals of Operations Research, 140, pp. 67-124Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G., OCTANE: A new heuristic for pure 01 programs (2001) Operations Research, 49 (2), pp. 207-225Balas, E., Martin, C.H., Pivot-and-complement: A heuristic for 01 programming (1980) Management Science, 26 (1), pp. 86-96Balas, E., Schmieta, S., Wallace, C., Pivot and shifta mixed integer programming heuristic (2004) Discrete Optimization, 1 (1), pp. 3-12Bnichou, M., Gauthier, J.M., Girodet, P., Hentges, G., Ribire, G., Vincent, O., Experiments in mixed-integer linear programming (1971) Mathematical Programming, 1, pp. 76-94Bertacco, L., Fischetti, M., Lodi, A., A feasibility pump heuristic for general mixed-integer problems (2007) Discrete Optimization, 4, pp. 63-76Danna, E., Rothberg, E., Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions (2005) Mathematical Programming Series A, 102 (1), pp. 71-90Eckstein, J., Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5 (1994) SIAM Journal on Optimization, 4, pp. 794-814Faaland, B.H., Hillier, F.S., Interior path methods for heuristic integer programming procedures (1979) Operations Research, 27 (6), pp. 1069-1087Fischetti, M., Glover, F., Lodi, A., The feasibility pump (2005) Mathematical Programming Series A, 104 (1), pp. 91-104Fischetti, M., Lodi, A., Local branching (2003) Mathematical Programming Series B, 98, pp. 23-47Fischetti, M., Lodi, A., Repairing MIP infeasibility through local branching (2008) Computers & Operations Research, 35, pp. 1436-1445Glover, F., Parametric branch and bound (1978) OMEGA the International Journal of Management Science, 6 (2), pp. 145-152Glover, F., Parametric tabu-search for mixed integer programs (2006) Computers & Operations Research, 33, pp. 2449-2494Glover, F., Infeasible/feasible search trajectories and directional rounding in integer programming (2007) Journal of Heuristics, 13, pp. 505-541Glover, F., Laguna, M., General purpose heuristics for integer programmingpart i (1997) Journal of Heuristics, 2, pp. 343-358Glover, F., Laguna, M., General purpose heuristics for integer programmingpart II (1997) Journal of Heuristics, 3, pp. 161-179Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer Academic Publisher Boston, Dordrecht, LondonGhosh, S., DINS, a MIP improvement heuristic (2007) Integer Programming and Combinatorial Optimization, 4513, pp. 310-323Golden, B.L., Stewart, W.R., Empirical analysis of heuristics (1985) The Traveling Salesman Problem, pp. 207-250Hansen, P., Mladenović, N., Uroević, D., Variable neighborhood search and local branching (2006) Computers & Operations Research, 33, pp. 3034-3045Hillier, F.S., Efficient heuristic procedures for integer linear programming with an interior (1969) Operations Research, 17, pp. 600-637Ibaraki, T., Ohashi, T., Mine, H., A heuristic algorithm for mixed-integer programming problems (1974) Mathematical Programming Study, 2, pp. 115-136http://www.ilog.com/products/cplexLinderoth, J.T., Savelsbergh, M.W.P., A computational study of search strategies for mixed integer programming (1999) Informs Journal on Computing, 11, pp. 173-187Løkketangen, A., Glover, F., Solving zero/one mixed integer programming problems using tabu search (1998) European Journal of Operational Research, 106, pp. 624-658Løkketangen, A., Jrnsten, K., Storøy, S., Tabu search within a pivot and complement framework (1994) International Transactions in Operational Research, 1 (3), pp. 305-316Mittelmann, H., (2003) Decision Tree for Optimization Software: Benchmarks for Optimization Software, , http://plato.asu.edu/bench.htmlMosteller, F., Rourke, R.E.K., (1973) Sturdy Statistics: Nonparametrics and Order Statistics, , Addison-WesleyPatel, J., Chinneck, J.W., Active constraint variable ordering for faster feasibility of mixed integer linear programs (2007) Mathematical Programming Series A, 110, pp. 445-474Saltzman, R.M., Hillier, F.S., A heuristic ceiling point algorithm for general integer linear programming (1992) Management Science, 38 (2), pp. 263-28