Measuring instance difficulty for combinatorial optimization problems
type: Item
instance of: scholarly article
title: Measuring instance difficulty for combinatorial optimization problems
zbMATH Open document ID: 1251.90339
author: Leo Lopes
author: Kate A. Smith-Miles
published in: Computers \& Operations Research
publication date: 2012-11-15T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6107520
zbMATH Keywords: algorithm selection
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: hardness prediction
zbMATH Keywords: instance difficulty
zbMATH Keywords: landscape analysis
zbMATH Keywords: phase transition
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: assignment problem
zbMATH Keywords: knapsack problem
zbMATH Keywords: bin-packing
zbMATH Keywords: graph coloring
zbMATH Keywords: timetabling
describes a project that uses: Hyperheuristics
describes a project that uses: OR-Library
describes a project that uses: PYTHIA
describes a project that uses: Knapsack
describes a project that uses: GAUSS
describes a project that uses: Paramils
MaRDI profile type: Publication
full work available at URL: j.cor.2011.07.006
OpenAlex ID: W1967715425
Wikidata QID: Q62033372
cites work: Efficient testing of large graphs
cites work: A combinatorial characterization of the testable graph properties
cites work: On the classification of NP-complete problems in terms of their correlation coefficient
cites work: Solving large quadratic assignment problems on computational grids
cites work: A new bound for the quadratic assignment problem based on convex quadratic programming
cites work: A note on some computationally difficult set covering problems
cites work: An Algorithm for Large Zero-One Knapsack Problems
cites work: Designing and reporting on computational experiments with heuristic methods
cites work: Reactive local search for the maximum clique problem
cites work: Evolutionary Computation in Combinatorial Optimization
cites work: Q3500152
cites work: Q4398864
cites work: Evolution towards the maximum clique
cites work: Q3145799
cites work: SOFSEM 2004: Theory and Practice of Computer Science
cites work: Graph Classes: A Survey
cites work: Ranking learning algorithms: Using IBL and meta-learning on accuracy and time results
cites work: Solving Lift-and-Project Relaxations of Binary Integer Programs
cites work: Hyper-Heuristics: An Emerging Direction in Modern Search Technology
cites work: Q4012216
cites work: A hard knapsack problem
cites work: Open problems of Paul Erd�s in graph theory
cites work: Hard Knapsack Problems
cites work: Problem structure heuristics and scaling behavior for genetic algorithms
cites work: Q3002852
cites work: Q5687258
cites work: An introduction to timetabling
cites work: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
cites work: Graph coloring with adaptive evolutionary algorithms
cites work: Q3267900
cites work: Q4717984
cites work: The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
cites work: Q4124603
cites work: Learning dynamic algorithm portfolios
cites work: Heuristic solution of open bin packing problems
cites work: The TSP phase transition
cites work: Q4692508
cites work: Q4224925
cites work: Property testing in bounded degree graphs
cites work: Q5704408
cites work: 10.1162/153244303322753616
cites work: Generating Experimental Data for Computational Testing with Machine Scheduling Applications
cites work: Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
cites work: Statistical mechanics of the vertex-cover problem
cites work: Phase Transitions in Combinatorial Optimization Problems
cites work: The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Testing heuristics: We have it all wrong

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Towards a characterisation of the behaviour of stochastic local search algorithms for SAT

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: A Bayesian approach to tackling hard computational problems. (Preliminary report)

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: ParamILS: An Automatic Algorithm Configuration Framework

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q4461912

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q4878666

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Evolutionary Computation in Combinatorial Optimization

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Algorithms for some hard knapsack problems

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: The quadratic assignment problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Evolutionary Computation in Combinatorial Optimization

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Objective function features providing barriers to rapid global optimization

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Generating applicable synthetic instances for branch problems

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: What makes an optimization problem hard?.

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Setting the research agenda in automated timetabling: the second international timetabling competition

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Determining computational complexity from characteristic ‘phase transitions’

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Principles and Practice of Constraint Programming – CP 2004

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Cheeger Constant and Connectivity of Graphs

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Edge cuts leaving components of order at least \(m\)

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Some Examples of Difficult Traveling Salesman Problems

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Where are the hard knapsack problems?

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Copositive and semidefinite relaxations of the quadratic assignment problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q4550779

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: GAUSS: an online algorithm selection system for numerical quadrature

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Landscapes, operators and heuristic search

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Synthetic optimization problem generation: show us the correlations!

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: On the Convergence of an Algorithm for Best Tchebycheff Approximations

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q4788610

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q4449707

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: On the facial structure of the set covering polytope

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: A review of metrics on permutations for search landscape analysis

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Generating hard satisfiability problems

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Discovering the suitability of optimisation algorithms by learning from evolved instances

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: The landscape of the traveling salesman problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Evolutionary Computation in Combinatorial Optimization

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Comparison of iterative searches for the quadratic assignment problem

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q2779799

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Formulations and Reformulations in Integer Programming

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Evolutionary Computation in Combinatorial Optimization

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: PYTHIA

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: Q5715669

Measuring instance difficulty for combinatorial optimization problems (cites work)
cites work: A study of complexity transitions on the asymmetric traveling salesman problem

Measuring instance difficulty for combinatorial optimization problems (DBLP publication ID)
DBLP publication ID: journals/cor/Smith-MilesL12

Measuring instance difficulty for combinatorial optimization problems (DOI)
DOI: 10.1016/J.COR.2011.07.006