ISSN: 2222-6990
Open access
In this paper a novel and very fast low order knowledge-based algorithm (called LOKBA)
is presented to solve binary integer programming (BIP) problems. The factors in the
objective function and the constraints of any BIP problem contains specific knowledge
and information that can be used to better search the solution space of the problem. In
this work many new definitions are introduced to elaborate on this information and
extract necessary knowledge for creating and improving solutions. Found solutions are
improved further and further until there is no new knowledge that can be extracted and
there are no more possible improvements. The proposed algorithm has many major
credentials. It produces promising results within amazingly short run times even for very
large problems such as problems with one million variables. Also, it is extendable to
solve integer programming and binary quadratic programming problems. Furthermore,
it can be combined with heuristic or meta heuristic algorithms.
Baeck, Fogel D, and Michalewicz Z (1997). Handbook of Evolutionary Computation, Oxf.
Univ. Press, NY.
Captivo ME, Climaco J, Figueira J, Martins E, Santos JL (2003),Solving Bicriteria 0-1
Knapsack Problems Using a Labeling Algorithm, Comput. Oper. Res.,30: 1865-1886
Chu PC and, Beasley JE (1998), a Genetic Algorithm for the Multidimensional Knapsack
Problem, J. Heuristics, 4: 63-86
Danna E, Rothberg E, and Pape CL (2005), Exploring Relaxation Induced Neighborhoods
to Improve MIP Solutions. Math. Program., 102:71-90
Domitrescu I and Stuetzle T (2003), Combinations of Local Search and Exact Algorithms,
Applications of Evolutionary Computations, Lect. Notes. Comput. Sc., 2611:211-223,
Springer
Fischetti M and Lodi A (2003), Local Branching, Math. Program. B, 98: 23-49
Fortin D, Tseveendorj I (2009), a Trust Branching Path for Zero-One Programming, Eur. J.
Oper. Res., 197: 439-445
Ghosh S (2007), DINS, a MIP Improvement Heuristic, Lect. Notes Comput. Sc., 4513:310-
323, Springer
Glover F and Laguna M (1997), Tabu Search, Klu. Acad. Publ.
Glover F, Laguna M, and Marti R (2000), Fundamentals of Scatter Search and Path
Relinking, Control. Cybern., 39(3): 653 681
Haartman KV, Kohn W, Zabinsky ZB (2008), A Meta-Control Algorithm for Generating
Approximate Solutions to Binary Integer Programming Problems, Nonlinear. Anal.
Hybrid Syst., 2:1232-1244
Hansen P, Mladenovic N, Urosevic D (2006),Variable Neighborhood Search and Local
Branching, Comput. Oper. Res., 33: 3034-3045
Kellerer H, Pferschy U, and Pisinger D (2004): Knapsack Problems, Springer
Kirkpatrick S, Gellat C and Vecchi M (1983), Optimization by Simulated Annealing,
Science, 220:671-680
Larranaga P and Lozano J (2001), Estimation of Distribution Algorithms, a New Tool for
Evolutionary Computation, Klu. Acad. Publ.
Lazic J, Hanafi S, Mladenovic N, Urosevic D (2009), Variable Neighborhood
Decomposition Search for 0-1 Mixed Integer Programs, Comput. Oper. Res.
P. Moscato and C. Cotta, A Gentle Introduction to Memetic Algorithms, in Handbook of
Metaheuristics, Chapter 5, pp.105-144, F. Glover and G. Kochenberger (Eds.), Klu. Acad.
Publ., Boston, Massachusetts, USA, (2003), ISBN:1-4020-7263-5
Namazifar M, Miller AJ (2008), a Parallel Macro Partitioning Framework for Solving
Mixed Integer Programs, Lect. Notes Comput. Sc., 5015: 343-348, Springer
Nemhauser G and Wolsey L (1988), Integer and Combinatorial Optimization, J. Wiley ,
NY.
Vasquez M , Hao JK (2001), a Hybrid Approach for the 0-1 Multidimensional Knapsack
problem, Int. Joint. Conf. Artif.,
Wang Z, Xing W (2009), a Successive Approximation Algorithm for the Multiple Knapsack
Problem, J. Comb. Optim.,17: 347-366
Wolsey LA (1998), Integer Programming, J. Wiley, NY.
N/A
Copyright: © 2012 The Author(s)
Published by HRMARS (www.hrmars.com)
This article is published under the Creative Commons Attribution (CC BY 4.0) license. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this license may be seen at: http://creativecommons.org/licences/by/4.0/legalcode