Many scientific, industrial engineering and economic problems may be cast into an integer-programming model. This paper attempts to review various approaches that have been developed for solving this model, emphasizing on the methodological view. For the sake of space, we restrict ourselves mainly to the pure integer-programming problem. The paper is expository in nature and it includes many references to give credit to essential results in the field and help readers obtain more detailed information on issues of interest.
AardalK.NemhauserG.WeismantelR., (Eds.) (2005), Handbooks in Operations and Management Science.
2.
AbbasM.BellahceneF., (2006), “Cutting Plane Method for Multiple Objective Stochastic Integer Linear Programming”, European J. Op. Research, Vol. 168, pp. 967–984.
3.
AlvelosF.CarvalhoJ. M. V. (2003), Comparing Branch-and-Price Algorithms for the Unsplittable Multi-Commodity Flow Problem, International Network Optimization Conference, Institut National des Telecommunications, France, pp. 7–12.
4.
BalasE. (1967), “Discrete Programming Method by Method”, Operations Research, Vol. 15, pp. 915–957.
5.
BalasE. (1971), “Intersection Cuts — A New Type of Cutting Planes for Integer Programming”, Operations Research, Vol. 19, pp. 19–39.
6.
BalasE.CeriaS.CornuejolsG.NatrajN. (1996), “Gomory Cuts Revisited”, Operations Research Letters, Vol. 19, pp. 1–9.
7.
BarnhartC.JohnsonE. L.NemhauserG. L.SavelsberghM. W. P.VanceP. H. (1998), Branch and Price Column Generation for Solving Huge Integer Programs, Operations Research, Vol. 46, pp 316–329.
8.
BarnhartC.HaneC. A.VanceP. H. (2000), Using branch-and-price-and-cut to solve origin-destination integer multi-commodity flow problems, Operations Research, Vol. 48, pp. 318–326.
9.
BealieE. M. L. (1979), “Branch and Bound Methods for Mathematical Programming Systems”, Annals of Discrete Mathematics, Vol. 5, pp. 201–219.
10.
BeasleyJ. E., (Ed), (1996), Advances in Linear and Integer Programming, Oxford University Press.
11.
BelienJ. (2006), “Exact and Heuristic Methodologies For Scheduling In Hospitals: Problems, Formulations And Algorithms”, 4OR:Quarterly Journal of Operations Research, Vol. 5 (2), pp. 157–160.
12.
BertsimasD.WeismantelR. (2005), Optimization over Integers, Dynamic Ideas, Belmont, Massachusetts.
13.
BienstockD.NemhauserG. L. (2004), Integer Programming and Combinatorial Optimization, 10th International ICPO Conference, New York, Springer Verlag. LNCS 3064.
14.
BoyedE. A. (1994), “Fenchel Cutting Planes for Integer Programs”, Operations Research, Vol. 42, pp. 53–64.
15.
BrunettaL.ConfortiM.RinaldiG. (1997), “A Branch and Cut Algorithm for the Equicut Problem”, Mathematical Programming, Vol. 78, pp. 243–263.
16.
BuckleyJ. J.JowersL. (2008), “Fuzzy Integer Programming, in Studies in Fuzziness and Software Computing”, Kacpryzk (Ed.), Vol. 222. pp. 223–226.
17.
ChvatalV. (1985), “Cutting Planes in Combinatorics”, European Journal of Combinatorics, Vol. 6, pp. 217–226.
18.
DakinR. J. (1965), “A Tree Search Algorithm for Mixed Integer Programming Problems”, The Computer Journal, Vol. 8, pp 250–255.
19.
DantzigG. B. (1959), “Note on Solving Linear Programs in Integers”, Naval Research Logistics Quarterly, Vol. 6, pp. 75–76.
20.
DobsonG. (1982), “Worst-Case Analysis of Greedy Heuristics for IP with Non-Negative Data”, Mathematics of Operations Research, Vol. 7, pp. 515–531.
21.
DorigoM.BirattariM.BlumC.GambardellaL. M.MondadaF.StiitzleT. (2006), Ant colony optimization and Swarm Intellenge, Springer.
22.
DuboisD.PradeH. (1980), Fuzzy sets and systems: Theory and Application, Academic Press.
23.
ElfM.GutwengerC.JüngerM. J.RinaldiG. (2001), Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS. In Computational Combinatorial Optimization, NaddefD.JüngerM. (Eds.), Springer, Berlin, 157.
24.
EshghiK.NematianJ. (2009), “Special Classes of Fuzzy Integer Programming Models with All-different Constraint”, Transactions E: Industrial Engineering, Vol. 16, pp. 1–10.
25.
FisherM. L. (1981), “The Lagrangian Method for Solving Integer Programming Problems”, Management Science, Vol. 27, pp. 1–18.
26.
FukasawaR.LongoH.LysgaardJ.Poggi de AragaoM.UchoaE.WerneckR. F. (2006), “Robust Branch-And-Cut-Price for the Capacitated Vehicle Routing Problem”, Mathematical Programming Series A, Vol. 106, pp. 491–511.
27.
GendreauM.PoyvinJ. Y. (2005), “Meta-Heuristic in Combinatorial Optimization”, Annals of Operations Research, Vol. 140, pp.189–213.
28.
GeoffrionA. M. (1974), “Lagrangian Relaxation and its Uses in Integer Programming”, Mathematical Programming Study, Vol. 2, pp. 82–114.
29.
GloverF.LagunaM. (1997a), “General Purpose Heuristic for IP, Part 1”, Journal of Heuristics, Vol. 3, pp. 161–179.
30.
GloverF.LagunaM. (1997b), “General Purpose Heuristic for IP, Part 11”, Journal of Heuristics, Vol. 4, pp. 343–358.
31.
GomoryR. E. (1958), “Outline of an Algorithm for Integer Solutions to Linear Programs”, Bulletin of the American Mathematical Society, Vol. 64, pp. 275–278.
32.
GomoryR. E. (1965), “On the Relation between Integer and Non Integer Solutions to Linear Programs”, Proceedings of the National Academy of Sciences of the United States of America, Vol. 53, pp. 260–265.
33.
GomoryR. E. (1969), “Some Polyhedra Related to Combinatorial Problems and its Applications”, Linear Algebra and its Applications, Vol. 2, pp. 451–458.
34.
GomoryR. E.JohnsonE. L. (1972), “Some Continuous Functions Related to Corner Polyhedra”, Mathematical Programming, Vol. 3, pp. 23–85.
35.
GomoryR. E.JonsonE. L.EvansL. (2003), “Corner Polyhedra and their Connections with Integer Programming”, Maths. Progm., Ser. B, Vol. 96, pp. 321–339.
36.
GuingardM.KimS. (1997), “Lagangian Decomposition: A Model Yielding Stronger Lagrangian Bounds”, Mathematical Programming, Vol. 39, pp. 215–228.
37.
HaneveldW. K. K.Van der VlerkM. H. (1999), “Stochastic Integer Programming: General Models and Algorithms”, Journal of Operations Research, Vol. 85, pp. 39–57.
38.
HerreraF.VerdegayJ. L. (1995), “Three Models of Fuzzy Integer Linear Programming”, European Journal of Operational Research, Vol. 83, pp. 581–593.
39.
HillierF. S.LiebermanG. J. (2005), “Introduction to Operations Research”, McGraw-Hill, 8th Edition.
40.
HoffmanK. L.PadbergM. (1991), “Improving LP Representation of Zero-one Linear Programs for Branch and Cut”, ORSA Journal of Computing, Vol. 3, pp.121–134.
41.
HuT. C. (1969), Integer Programming and Network Flows, Addition Wresley.
42.
HuangG. H.BaetzB.W.PatryG. G. (1995), “Grey Fuzzy Integer Programming: An Application to Regional Waste Management Planning Under Uncertainty”, Socio-Economic Planning Sciences, Vol. 29, pp. 17–38.
43.
HuynhH. N.ConnellH. J.KumarS. (1987a), Random Search Method for Mixed Integer Programming, ASOR 87, Proc. of the 8th ASOR National Conference, Melbourne, pp.109–118.
44.
HuynhH. N.KumarS.ConnellH. J. (1987b), Random search method for integer programming, Proc. of the International Conference on Optimization Techniques, (Eds.) TeoK. L.PaulH.ChewK. L.WongM.C., pp. 601–610.
45.
HuynhH. N.KumarS. (1990), “A Random Search Method for Extreme Point Mathematical Programming Problems”, Asia Pacific Journal of Operational Research, Vol. 7 (1), pp. 30–46.
46.
KarlofJ. K. (2005), Integer Programming: Theory and Practice, CRC Press.
47.
KreherD. L.StinsonD. R. (1998), Combinatorial Algorithms: Generation Enumeration and Search, CRC press.
48.
KumarS. (2005), “Information Recycling Mathematical Methods For Protean Systems: A Path-Way Approach”, South African Journal of Industrial Engineering, Vol. 16 (2), pp. 81–101.
49.
KumarS. (2006), “Information Recycling Mathematical Methods for Protean Systems: A Path-Way Approach to A Geometric Program”, South African Journal of Industrial Engineering, Vol. 17 (2), pp. 127–143.
50.
KumarS.ScrmozzianoF. (1998), “Characteristics and Applications of Random Search Methods for Integer Programming”, Vol. 18, pp. 167–181.
51.
KumarS.MunapoE.JonesB. C. (2007), “An Integer Equation Controlled Descending Path to A Protean Pure Integer Program”, Indian Journal of Mathematics, Allahabad, Vol. 49 (2), pp. 211–237.
52.
KumarS.MunapoE.JonesB.C. (2008a), “Complexity Reduction for Solving A Pure Integer Program by the Branch and Bound Method using the Gomory Constraints”, ASOR Bulletin, Vol. 27 (2), pp. 13–22.
53.
KumarS.MunapoE.JonesB. C. (2009), “Descending Hyper-Plane Approach for Solving A Binary Integer Program”, International Journal of Mathematical Modeling, Simulation and Applications, Vol. 2 (1), pp. 53–62.
54.
LandA.H.DoigA.G., (1960), “An Automatic Method for Solving Discrete Programming Problems”, Econometrica, Vol. 28, pp. 497–520.
55.
LadányiL.RalphsT. K.TrotterL. E.Jr. (2001), “Branch, cut and Price: Sequential and Parallel”, in Computational Combinatorial Optimization, NaddefN.JüengerM., eds, Springer, Berlin, 223.
56.
LubbeckeM. E.DesrosiersJ. (2005), “Selected Topics in Column Generation”, Operations Research, Vol. 53, pp. 1007–1023.
57.
ManiezzeV.StiitzleT. (2010), Hybridizing Meta-heuristic and Mathematical Programming, Annals of Information System Series.
58.
MichalewiczZ.FogelD. B. (2004), How to Solve It: Modern Heuristics, Springer.
59.
MitchellJ. E.LeeE. K. (2001a), Branch and Bound Methods for Integer Programming: In FloudasC.A.PardalosP.M. (Eds.), Encyclopedia of Optimization, Kluwer Academic Publishers.
60.
MitchellJ. E. (2001b), Branch and Cut Algorithms for Integer Programming: In FloudasC.A.PardalosP.M. (Eds.), Encyclopedia of Optimization, Kluwer Academic Publishers.
61.
MitchellJ. E. (2002), Cutting Plane Algorithms for Combinatorial Optimization Problems, In PardalosP.M.RezendeM. G. C. (Eds.), Handbook of Applied Optimization, Oxford University Press.
62.
MitsuoG.KenichI.Chang-YunL. (1999), “Hybridizing Nerural Networks and Genitic Algorithms for Solving Integer Programming”, Lecture Notes in Computer Science, Vol. 1585, pp. 421–429.
63.
MunapoE.JonesB. C.KumarS. (2009), “Ordered Branch Algorithm for Solving the Characteristic Equation and Other Strategies”, International Journal of Mathematical Modeling, Simulation and Applications, Vol. 2 (4).
64.
MunapoE.KumarS.KhanL. (2010), Information Recycling on Integer Polyhedron, Communicated for Publication.
65.
NemhauserG. L.WolseyL. A. (1999), Integer and Combinatorial Optimization, North Holland.
PadbergM. W. (1975), “A Note on Zero-One Programming”, Operations Research, Vol. 23, pp. 833–837.
68.
PadbergM.RinaldiG. (1991), “A Branch and Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems”, SIAM Review, Vol. 33 (1), pp. 60–100.
69.
PannambalammS. G.ArvindanP.RajevS. V. (2000), “A Tabu Search Algorithm for Job Shop Scheduling”, The International Journal of Advanced Manufacturing Technology, Vol. 16, pp. 765–771.
70.
PapadimitriouC. H. (1981), “On the Complexity of Integer Programming for Computing Machinery,Journal of the ACM, Vol. 28, pp. 765–768.
71.
PapaioannouG.WilsonJ. M. (2009), “Fuzzy Extensions to Integer Programming Models of Cell-Formation Problems in Machine Scheduling”, Annals of Operations ResearchVol. 166, pp.163–181.
72.
PrivaultC. (1998), “Solving a Real-World Assignment Problem with Meta-Heuristic”, Journal of Heuristics, Vol. 4, pp. 383–398.
73.
PuchingerJ.RaidiG.Pirkwieses (2010), Meta Bootsing: Enhancing IP Techniques by Meta-Heuristics, in Hybridizing Meta-Heuristic and Mathematical Programming, ManiezzoVStiitzle (Eds.).
74.
PunchingerJ.RinaldiG. R. (2005), Combining Metaheuristic and Exact Algorithms in Combinatorial Optimization: A Survey and Classification, Lecture Notes in Computer Science, MiraJ.AlvarezJR (Eds.) Springer, Vol. 3562, pp. 41–53.
75.
RezendeM. G. C.RibeiroC. C. (2003), Greedy Randomized Adaptive Search Procedures, In the Handbook of Meta-Heuristic, GloverF.KochnbergerG., Editors, Kluwer Academic Publishers, pp. 325–367.
76.
RiberioC. C.HansenP. (2002), Essays and Surveys on Meta-heuristics, Kluwer Academics.
77.
SalkinH. M. (1971), “A Note on Gomory Fractional Cuts”, Operations Research, Vol. 19, pp. 1538–1541.
78.
SalkinH. M.MathurK. (1989), Foundations of Integer Programming, North – Holland, New York.
79.
SavelsberghM. W. P. (1987), “A Branch and Price Algorithm to Solve the Generalized Assignment Problem”, Operations Research, Vol. 45, pp. 831–841.
80.
SavelsberghM. W. P. (1994), “Preprocessing and Probing Techniques for Mixed Integer Programming Problems”, ORSA Journal of Computing, Vol. 6 (4), pp. 445–454.
81.
SchrijiverA. (1986), Theory of Linear and Integer Programming, John Wiley, New York.
82.
ShapiroJ. F. (1968), “Group Theoretic Algorithm for the Integer Programming Problem. 11: Extension to a General Algorithm”, Operations Research, Vol. 16, pp. 928–947.
83.
SmithK. A. (1999), “Neural Network for Combinatorial Optimization: A Review of more than a Decade of Research”, INFORM Journal of Computing, Vol. 11, pp. 15–34.
84.
StougieL.Van der VlerkM. H. (2003), Approximation in Stochastic Integer Programming [Available from http://irs.ub.rug.nl/ppn/248283359].
85.
StougieL.Van der VlerkM. H. (1997), Stochastic Integer Programming, In Annotated Bibliographies in Combinatorial Optimization; Dell”AmicoM.MaffioliF.MartelloS., Chap 9, pp. 127–141.
86.
TahaH. A. (1975), Integer Programming, Applications and Computations, Academic Press, New York.
87.
TahaH. A. (2002), TORA Software, Windows Version 1.00.
88.
TahaH. A. (2004), Operations Research: An Introduction, Prentice-Hall India, 7th edition.
89.
TomlinJ. A. (1971), “An Improved Branch and Bound Method for Integer Programming”, Operations Research, Vol. 19, pp. 1070–1075.
Van RoyT. J.WolseyL. A. (1987), “Solving Mixed 0–1 Programs by Automatic Reformulations”, Operations Research, Vol. 35, pp. 45–57.
92.
WilhelmW. E. (2001), “A Technical Review of Column Generation in Integer Programming”, Optimization and Engineering, Vol. 2, pp. 159–200.
93.
WollmerR. D. (1980), “Two Stage Linear Programming Under Uncertainty With 0–1 Integer First Stage Variables”, Mathematical Programming, Vol. 19, pp. 279–288.
94.
WinstonW. L. (2004), Operations Research Applications and Algorithms, Duxbury Press, 4th Edition.
95.
YoungR. D. (1969), Primal Integer Programming, Chapter 17 in HuT. C., (1969), Integer Programming and Network Flows, Addison Wesley.
