Measuring instance difficulty for combinatorial optimization problems

DOI10.1016/j.cor.2011.07.006zbMath1251.90339OpenAlexW1967715425WikidataQ62033372 ScholiaQ62033372MaRDI QIDQ1762054

Leo Lopes, Kate A. Smith-Miles

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.07.006

zbMATH Keywords

combinatorial optimizationphase transitiongraph coloringknapsack problemtraveling salesman problemtimetablingassignment problembin-packingalgorithm selectionlandscape analysishardness predictioninstance difficulty

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Algorithms in computer science (68W99)

Related Items (34)

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem ⋮ Unified encoding for hyper-heuristics with application to bioinformatics ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ A step counting hill climbing algorithm applied to university examination timetabling ⋮ Towards objective measures of algorithm performance across instance space ⋮ A cutting plane algorithm for the site layout planning problem with travel barriers ⋮ MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration ⋮ Accelerating the branch-and-price algorithm using machine learning ⋮ Generating new test instances by evolving in instance space ⋮ The representation of partially-concurrent open shop problems ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Instance space analysis and algorithm selection for the job shop scheduling problem ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Stochastic local search and parameters recommendation: a case study on flowshop problems ⋮ Discovering the suitability of optimisation algorithms by learning from evolved instances ⋮ The international timetabling competition on sports timetabling (ITC2021) ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Instance spaces for machine learning classification ⋮ Advancing Shannon entropy for measuring diversity in systems ⋮ Generation techniques for linear programming instances with controllable properties ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Algorithm runtime prediction: methods \& evaluation ⋮ Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art ⋮ A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem ⋮ A methodology for determining an effective subset of heuristics in selection hyper-heuristics ⋮ A global search framework for practical three-dimensional packing with variable carton orientations ⋮ Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis ⋮ Random walk's correlation function for multi-objective NK landscapes and quadratic assignment problem ⋮ Instance space analysis for a personnel scheduling problem ⋮ Selecting algorithms for large berth allocation problems ⋮ Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations ⋮ Scheduling with uncertain processing times in mixed-criticality systems ⋮ Solving the selective multi-category parallel-servicing problem ⋮ Evolving test instances of the Hamiltonian completion problem

Uses Software

• Hyperheuristics
• Paramils
• PYTHIA
• OR-Library
• Knapsack
• GAUSS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discovering the suitability of optimisation algorithms by learning from evolved instances
• An introduction to timetabling
• Objective function features providing barriers to rapid global optimization
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Learning dynamic algorithm portfolios
• A review of metrics on permutations for search landscape analysis
• What makes an optimization problem hard?.
• On the facial structure of the set covering polytope
• Graph coloring with adaptive evolutionary algorithms
• Landscapes, operators and heuristic search
• Evolution towards the maximum clique
• The TSP phase transition
• Ranking learning algorithms: Using IBL and meta-learning on accuracy and time results
• Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
• Where are the hard knapsack problems?
• Solving large quadratic assignment problems on computational grids
• Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach
• GAUSS: an online algorithm selection system for numerical quadrature
• Designing and reporting on computational experiments with heuristic methods
• Testing heuristics: We have it all wrong
• On the classification of NP-complete problems in terms of their correlation coefficient
• Heuristic solution of open bin packing problems
• Edge cuts leaving components of order at least \(m\)
• Generating hard satisfiability problems
• A study of complexity transitions on the asymmetric traveling salesman problem
• Problem structure heuristics and scaling behavior for genetic algorithms
• The Quadratic Assignment Problem
• Generating Applicable Synthetic Instances for Branch Problems
• Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition
• Synthetic Optimization Problem Generation: Show Us the Correlations!
• A combinatorial characterization of the testable graph properties
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
• On the Convergence of an Algorithm for Best Tchebycheff Approximations
• Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications
• ParamILS: An Automatic Algorithm Configuration Framework
• A hard knapsack problem
• The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
• A note on some computationally difficult set covering problems
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• Some Examples of Difficult Traveling Salesman Problems
• Comparison of iterative searches for the quadratic assignment problem
• Graph Classes: A Survey
• [https://portal.mardi4nfdi.de/wiki/Publication:4337503 Open problems of Paul Erd�s in graph theory]
• PYTHIA
• Hyper-Heuristics: An Emerging Direction in Modern Search Technology
• Cheeger Constant and Connectivity of Graphs
• 10.1162/153244303322753616
• Determining computational complexity from characteristic ‘phase transitions’
• Formulations and Reformulations in Integer Programming
• Phase Transitions in Combinatorial Optimization Problems
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Statistical mechanics of the vertex-cover problem
• Evolutionary Computation in Combinatorial Optimization
• Evolutionary Computation in Combinatorial Optimization
• Principles and Practice of Constraint Programming – CP 2004
• Evolutionary Computation in Combinatorial Optimization
• Evolutionary Computation in Combinatorial Optimization
• Evolutionary Computation in Combinatorial Optimization
• SOFSEM 2004: Theory and Practice of Computer Science
• A new bound for the quadratic assignment problem based on convex quadratic programming
• Efficient testing of large graphs
• Reactive local search for the maximum clique problem
• The landscape of the traveling salesman problem
• Property testing in bounded degree graphs

This page was built for publication: Measuring instance difficulty for combinatorial optimization problems