Combinatorial Problems -- A Subject Catalog

See also: [Artificial Intelligence page], [Operations Research page], [Kanada's home page in English], [Kanada's home page in Japanese].

Indices and General Information

• 1995 REU Proposal: Novel Combinatorial Optimisation Methods
• Combinatorial optimization -- Bibliography of books and survey papers
  compiled by Brian Borchers (borchers@nmt.edu),
• Journal of Global Optimization
• Introduction to the ACO program (ACO means Algorithms, Combinatorics and Optimization) -- A good introduction to the relation of these 3 areas and the Ph.D program of CMU.
• Global (and Local) Optimization

DIMACS and Its Challenges

What is DIMACS?

• DIMACS is an abbreviation of Center for Discrete Mathematics and Theoretical Computer Science.
• ``DIMACS is a national research center, funded by the National Science Foundation. It is a joint project, whose direct participants are Rutgers University, Princeton University, AT&T Bell Labs, and BellCore.'' (From About DIMACS)

DIMACS Challenges

• 1st Challenge (FTP)
• 2nd Challenge (FTP) on Cliques, Coloring and Satisfiability
  • M. Trick's Page on 2nd Dimacs Challenge -- An overview
  • Call for Participation
  • Graph Problems
    • Proposals
    • Benchmarks: Maximum Clique Problems, Coloring Problems, and Volume (``the standard instances that will be solved by every paper that appears in the refereed volume'' -- Thanks to Mike Trick)
    • Contributed Papers -- The workshop papers are not included.
    • Solvers: Readme
  • Satisfiability Problems
    • Proposals
• 3rd Challenge (FTP)

Miscellaneous

• DIMACS Workshop on the Satisfiability Problem: Theory and Applications: Program
• Special Year Listings, 1989- (Abstracts only)
• Publication Volumes, including On-line Algorithms, Many Graph Algorithms, and so on.
• Technical Papers, 1989-

Simulated Annealing

• Simulated Annealing Information
• Brief Note on Simulated Annealing
• Lester Ingber's Code and Reprint Archive, including ASA (Adaptive Simulated Annealing)
• Sim Anneal for Satisfiability

GSAT and WSAT

• AI Research Papers of ATT, including GSAT and WSAT code and guide

• WSAT Papers
  • Noise Strategies for Improving Local Search by Bart Selman and Henry Kautz, Proc. AAAI-94. (PostScript)
  • Joachim P. Walser, Andrew J. Parkes, Tuning Local Search for Satisfiability Testing. AAAI-96, Portland, OR, 1996. (PostScript)
• GSAT Papers at Research.ATT (in PostScript)
  • B. Selman, H. Levesque, D. Mitchell: A New Method for Solving Hard Satisfiability Problems, IJCAI '93 (93.1) (PostScript)
  • B. Selman and H. Kautz: Domain-Independent Extensions to GSAT: Solving Large Structure Satisfiability Problems (93.4) (PostScript)
  • B. Selman and H. Kautz: An Empirical Study of Greedy Local Search for Satisfiability testing, AAAI '93 (93.12) (PostScript)
  • Other Papers at Research.ATT, including SAT plan, SAT survey, ...
• Gent, I.P. and Walsh, T.: An Empirical Analysis of Search in GSAT, J. of AI Research, Volume 1, 47-59. (500kB)
• GSAT User's Guide

Satisfiability Problems

• AAAI-96 Tutorial: New Methods for Solving Large Constraint and Reasoning Problems
• Papers of David G. Mitchell
• Joachim P. Walser's papers
  • Master's Thesis - "Retrospective Analysis: Refinements of Local Search for Satisfiability Testing"
  • AAAI-96 Paper

Problem Collections

• TSPLIB -- A Collection of Traveling Salesman Problem instances.
  • TSPLIB 95
  • At Rice Univ. (FTP)
  • At Univ. Heidelberg (in HTML)
• TSPBIB Home Page
• From Evolutionary Computation Journal
  • Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSP, By Christine L. Valenzuela and Antonia J. Jones
• MIPLIB -- Collection of Mixed Integer Programming instances.
• OR-Library at Imperial College Management School, including Location, Scheduling, Steiner, 2D Cutting, Vehicle Routing Problems, etc. (but not accessible!)

Miscellaneous

Graph coloring -- Bibliographies

• Network Resources for Coloring a Graph by Michael Trick
• Bibliography on Graph Coloring
• Bibliography on Graph Coloring
• Search result by Glimpse
• Search result by Waters
• Graph Coloring Problems -- a book
• Four Color Theorem -- a book

Miscellaneous

• Where the Really Hard Problems Are by P. Cheeseman, B. Kanefsky, and W. M. Taylor (in HTML), containing Hamilton Circuits, Graph Coloring, K-Satisfiability and Travelling Salesman Problems
• Phase Transitions in Search
• Valued Constraint Satisfaction Problems: Hard and Easy Problems Thomas Schiex, Helene Fargier, and Gerard Verfaillie
• Memetic Algorithms' Home Page
• Comparisons of GA, SA and Tabu Search: Local Search with Memory: Benchmarking RTS (Reactive Tabu Search method), by R. Battiti and G Tecchiolli
• Probabilistic Constraint Satisfaction: Application to Radiosurgery by R. B. Altman and R. Tombropoulos, Knowledge Systems Laboratory, Medical Computer Science, KSL-94-35, November 1994. (Postscript available)
• An Empirical Evaluation of a Randomized Algorithm for Probabilistic Inference, by M. R. Chavez and G. F. Cooper, In M. Henrion et al., Ed., Fifth Workshop on Uncertainty in Artificial Intelligence, 191-207, Elsevier Science Publishers B.V., North-Holland, 1989. (Postscript not available)
• See Programming Page for theories of graph and other problems.
• See Operations Research Page for other optimization problems.
• See Artificial Intelligence Page for other AI-related topics.
• A Search Result on Probabilistic/Randomized Algorithm (Computation) by CS Bib