Comparisons of Commercial MIP Solvers and an Adaptive Memory (Tabu Search) Procedure for a Class of 0-1 Integer Programming Problems

Authors

  • Lars Magnus Hvattum Norwegian University of Science and Technology
  • Arne Løkketangen Molde University College, Specialized University in Logistics
  • Fred Glover OptTek System Inc.

Keywords:

zero-one integer programming, Boolean optimization, commercial solvers, metaheuristics

Abstract

The Boolean optimization problem (BOOP) is a highly useful formulation that embraces a variety of 0-1 integer programming problems, including weighted versions of covering, partitioning and maximum satisfiability problems. Several years ago Hvattum, Løkketangen and Glover (2006) introduced an adaptive memory (tabu search) method for BOOP which proved effective compared to competing approaches. However, in the intervening years, major advances have taken place in exact solvers for integer programming problems, leading to widely publicized successes by the leading commercial solvers XPRESS, CPLEX and GUROBI. The implicit message is that an alternative methodology for any broad class of IP problems such as Boolean Optimization Problems would now be dominated by the newer versions of these leading solvers.

We test this hypothesis by performing new computational experiments comparing the tabu search method for the BOOP class against XPRESS, CPLEX and GUROBI, and documenting improvements provided by the exact codes. The outcomes are somewhat surprising.

Author Biography

Lars Magnus Hvattum, Norwegian University of Science and Technology

Department of Industrial Economics and Technology Management

Downloads

Additional Files

Published

2012-07-26

How to Cite

Hvattum, L. M., Løkketangen, A., & Glover, F. (2012). Comparisons of Commercial MIP Solvers and an Adaptive Memory (Tabu Search) Procedure for a Class of 0-1 Integer Programming Problems. Algorithmic Operations Research, 7(1), Pages 13 – 20. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18595

Issue

Vol. 7 No. 1 (2012)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.