Artículos de revistas
A Computational Study Of Parametric Tabu Search For 01 Mixed Integer Programs
Registro en:
Computers And Operations Research. , v. 38, n. 2, p. 464 - 473, 2011.
3050548
10.1016/j.cor.2010.07.004
2-s2.0-77956396753
Autor
Sacchi L.H.
Armentano V.A.
Institución
Resumen
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. 38 2 464 473 Achterberg, T., Berthold, T., Improving the feasibility pump (2007) Discrete Optimization, 4, pp. 77-86 Achterberg, T., Koch, T., Martin, A., (2003) The Mixed Integer Programming Library, , http://miplib.zib.de Achterberg, T., Koch, T., Martin, A., Branching rules revisited (2005) Operations Research Letters, 33, pp. 42-54 Atamtrk, A., Savelsbergh, M.W.P., Integer-programming software systems (2005) Annals of Operations Research, 140, pp. 67-124 Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G., OCTANE: A new heuristic for pure 01 programs (2001) Operations Research, 49 (2), pp. 207-225 Balas, E., Martin, C.H., Pivot-and-complement: A heuristic for 01 programming (1980) Management Science, 26 (1), pp. 86-96 Balas, E., Schmieta, S., Wallace, C., Pivot and shifta mixed integer programming heuristic (2004) Discrete Optimization, 1 (1), pp. 3-12 Bnichou, M., Gauthier, J.M., Girodet, P., Hentges, G., Ribire, G., Vincent, O., Experiments in mixed-integer linear programming (1971) Mathematical Programming, 1, pp. 76-94 Bertacco, L., Fischetti, M., Lodi, A., A feasibility pump heuristic for general mixed-integer problems (2007) Discrete Optimization, 4, pp. 63-76 Danna, E., Rothberg, E., Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions (2005) Mathematical Programming Series A, 102 (1), pp. 71-90 Eckstein, J., Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5 (1994) SIAM Journal on Optimization, 4, pp. 794-814 Faaland, B.H., Hillier, F.S., Interior path methods for heuristic integer programming procedures (1979) Operations Research, 27 (6), pp. 1069-1087 Fischetti, M., Glover, F., Lodi, A., The feasibility pump (2005) Mathematical Programming Series A, 104 (1), pp. 91-104 Fischetti, M., Lodi, A., Local branching (2003) Mathematical Programming Series B, 98, pp. 23-47 Fischetti, M., Lodi, A., Repairing MIP infeasibility through local branching (2008) Computers & Operations Research, 35, pp. 1436-1445 Glover, F., Parametric branch and bound (1978) OMEGA the International Journal of Management Science, 6 (2), pp. 145-152 Glover, F., Parametric tabu-search for mixed integer programs (2006) Computers & Operations Research, 33, pp. 2449-2494 Glover, F., Infeasible/feasible search trajectories and directional rounding in integer programming (2007) Journal of Heuristics, 13, pp. 505-541 Glover, F., Laguna, M., General purpose heuristics for integer programmingpart i (1997) Journal of Heuristics, 2, pp. 343-358 Glover, F., Laguna, M., General purpose heuristics for integer programmingpart II (1997) Journal of Heuristics, 3, pp. 161-179 Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer Academic Publisher Boston, Dordrecht, London Ghosh, S., DINS, a MIP improvement heuristic (2007) Integer Programming and Combinatorial Optimization, 4513, pp. 310-323 Golden, B.L., Stewart, W.R., Empirical analysis of heuristics (1985) The Traveling Salesman Problem, pp. 207-250 Hansen, P., Mladenović, N., Uroević, D., Variable neighborhood search and local branching (2006) Computers & Operations Research, 33, pp. 3034-3045 Hillier, F.S., Efficient heuristic procedures for integer linear programming with an interior (1969) Operations Research, 17, pp. 600-637 Ibaraki, T., Ohashi, T., Mine, H., A heuristic algorithm for mixed-integer programming problems (1974) Mathematical Programming Study, 2, pp. 115-136 http://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-187 Løkketangen, A., Glover, F., Solving zero/one mixed integer programming problems using tabu search (1998) European Journal of Operational Research, 106, pp. 624-658 Lø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-316 Mittelmann, H., (2003) Decision Tree for Optimization Software: Benchmarks for Optimization Software, , http://plato.asu.edu/bench.html Mosteller, F., Rourke, R.E.K., (1973) Sturdy Statistics: Nonparametrics and Order Statistics, , Addison-Wesley Patel, J., Chinneck, J.W., Active constraint variable ordering for faster feasibility of mixed integer linear programs (2007) Mathematical Programming Series A, 110, pp. 445-474 Saltzman, R.M., Hillier, F.S., A heuristic ceiling point algorithm for general integer linear programming (1992) Management Science, 38 (2), pp. 263-283