The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment

References

• Amaldi E, Pfetsch M, Trotter L, Cornuéjols G, Burkard RE, Woeginger GJ. Structural and algorithmic properties of the maximum feasible subsystem problem. Proc. Integer Programming and Combin. Optim. Conf. (IPCO'99) (1999) (Springer-Verlag, New York) 45–59Lecture Notes in Computer Science, Vol. 1610Crossref, Google Scholar
• Archetti C, Speranza MG, Savelsbergh MWP. An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Sci. (2008) 42(1):22–31Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L. Fast statistical alignment. PLoS Comput. Biol. (2009) 5(5):392–400Crossref, Google Scholar
• Chakravarti N. Some results concerning post-infeasibility analysis. Eur. J. Oper. Res. (1994) 73:139–143Crossref, Google Scholar
• Chandrasekaran K, Karp RM, Moreno-Centeno E, Vempala S, Randall D. Algorithms for implicit hitting set problems. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms, SODA '11 (2011) (SIAM, Philadelphia) 614–629Crossref, Google Scholar
• Chinneck JW. An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem. Ann. Math. Artificial Intelligence (1996) 17:127–144Crossref, Google Scholar
• Chinneck JW. Fast heuristics for the maximum feasible subsystem problem. INFORMS J. Comput. (2001) 13(3):210–233Link, Google Scholar
• Chinneck JW. Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods (2008) 118(Springer, New York) International Series in Operations Research and Management SciencesGoogle Scholar
• Chinneck JW, Dravnieks EW. Locating minimal infeasible constraint sets in linear programs. ORSA J. Comput. (1991) 3(2):157–168Link, Google Scholar
• Chvatal V. A greedy heuristic for the set covering problem. Math. Oper. Res. (1979) 4(3):233–235Link, Google Scholar
• Dilkina B, Gomes CP, Sabharwal A, Bessiere C. Tradeoffs in the complexity of backdoor detection. Proc. 13th Internat. Conf. Principles and Practice of Constraint Programming, CP'07 (2007) (Springer-Verlag, Berlin) 256–270Crossref, Google Scholar
• Dilkina B, Gomes CP, Malitsky Y, Sabharwal A, Sellmann M, Van Hoeve W-J, Hooke JN. Backdoors to combinatorial optimization: Feasibility and optimality. Proc. 6th Conf. Integration of AI and OR Tech. Constraint Programming (2009) (Springer-Verlag, Berlin) 56–70Crossref, Google Scholar
• Feige U. A threshold of ln n for approximating set cover. J. ACM (1998) 45(4):643–652Crossref, Google Scholar
• Franceschi DR, Fischetti M, Toth P. A new ILP-based refinement heuristic for vehicle routing problems. Math. Programming B (2006) 105(2):471–499Crossref, Google Scholar
• Gotoh O, Yamada S, Yada T, Srinivas A. Multiple sequence alignment. Handbook of Computational Molecular Biology (2006) (CRC Press, Boca Raton, FL) 3.1–3.36Chap. 3Google Scholar
• Heringa J, Andrzej KK, Crabbe MJC. Protein sequence analysis and prediction of secondary structure features. Compact Handbook of Computational Biology (2004) (Marcel Dekker, New York) 99–185Chap. 4Crossref, Google Scholar
• Hewitt M, Nemhauser GL, Savelsbergh MWP. Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS J. Comput. (2010) 22(2):314–325Link, Google Scholar
• Johnson DS. Approximation algorithms for combinatorial problems. J. Comput. System Sci. (1974) 9:256–278Crossref, Google Scholar
• Karp RM, Miller RE, Thatcher JW. Reducibility among combinatorial problems. Complexity of Computer Computations (1972) (Plenum Press, New York) 85–103Crossref, Google Scholar
• Kececioglu J, Apostolico A, Crochemore M, Galil Z, Manber U. The maximum weight trace problem in multiple sequence alignment. Combinatorial Pattern Matching (1993) 684(Springer, Berlin) 106–119Lecture Notes in Computer ScienceCrossref, Google Scholar
• Koller G, Raidl GR, Yao X, Burke E, Lozano JA, Smith J, Merelo-Guervós JJ, Bulinaria JA, Rowe J, Tino P, Kaban A, Schwefel H-P. Evolutionary algorithm for the maximum weight trace formulation of the multiple sequence alignment problem. Parallel Problem Solving from Nature VIII (2004) 3242(Springer, Berlin) 302–311Lecture Notes in Computer ScienceCrossref, Google Scholar
• Koufogiannakis C, Young NE. Beating simplex for fractional packing and covering linear programs. FOCS '07 Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (2007) (IEEE Computer Society, Washington, DC) 494–504Crossref, Google Scholar
• Lovasz L. On the ratio of optimal integral and fractional covers. Discrete Math. (1975) 13(4):383–390Crossref, Google Scholar
• Lund C, Yannakakiss M. On the hardness of approximating minimization problems. J. ACM (1994) 41(5):960–981Crossref, Google Scholar
• Mehlhorn K, Naher S. Leda: A platform for combinatorial and geometric computing. Comm. ACM (1995) 38(1):96–102Crossref, Google Scholar
• Monaci M, Toth P. A set-covering-based heuristic approach for bin-packing problems. INFORMS J. Comput. (2006) 18(1):71–85Link, Google Scholar
• Morgenstern B, Dress A, Werner T. Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc. Natl. Acad. Sci. USA (1996) 93:12098–12103Crossref, Google Scholar
• Muter I, Birbil SI, Sahin G. Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems. INFORMS J. Comput. (2010) 22(4):603–619Link, Google Scholar
• Nemhauser GL, Wolsey LA. Integer and Combinatorial Optimization (1988) (John Wiley & Sons, Chichester, UK) Crossref, Google Scholar
• Parker MR, Ryan J. Finding the minimum weight IIS cover of an infeasible system of linear inequalities. Ann. Math. Artificial Intelligence (1996) 17:107–126Crossref, Google Scholar
• Plotkin S, Shmoys DB, Tardos E. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. (1995) 20(2):495–504Link, Google Scholar
• Reinert K, Lenhof H-P, Mutzel P, Mehlhorn K, Kececioglu JD, Istrail S, Pevzner PA, Waterman MS. A branch-and-cut algorithm for multiple sequence alignment. Proc. 1st Annual Internat. Conf. Comput. Molecular Biol. (RECOMB) (1997) (ACM, New York) 241–250Crossref, Google Scholar
• Sankaran JK. A note on resolving infeasibility in linear programs by constraint relaxation. Oper. Res. Lett. (1993) 13:19–20Crossref, Google Scholar
• Savelsbergh M, Song JH. An optimization algorithm for inventory routing with continuous moves. Comput. Oper. Res. (2008) 35(7):2266–2282Crossref, Google Scholar
• Schmid V, Doerner KF, Hartl RF, Savelsbergh MWP, Stoecher W. A hybrid solution approach for ready-mixed concrete delivery. Transportation Sci. (2009) 43(1):70–85Link, Google Scholar
• Slavik P. A tight analysis of the greedy algorithm for set cover. J. Algorithms (1997) 25(2):237–254Crossref, Google Scholar
• Smith TF, Waterman MS. Identification of common molecular subsequences. J. Molecular Biol. (1981) 147(1):195–197Crossref, Google Scholar
• Williams R, Gomes CP, Selman B, Gottlob G, Walsh T. Backdoors to typical case complexity. Proc. 18th Internat. Joint Conf. Artificial Intelligence (2003) (Morgan Kaufmann Publishers Inc., San Francisco) 1173–1178Google Scholar