Instance Space Analysis for the Car Sequencing Problem
- URL: http://arxiv.org/abs/2012.10053v1
- Date: Fri, 18 Dec 2020 05:26:13 GMT
- Title: Instance Space Analysis for the Car Sequencing Problem
- Authors: Yuan Sun, Samuel Esler, Dhananjay Thiruvady, Andreas T. Ernst,
Xiaodong Li and Kerri Morgan
- Abstract summary: We investigate what characteristics make an instance hard to solve.
We compare the performance of six algorithms for solving the car sequencing problem.
Our results show that the new algorithms are state-of-the-art.
- Score: 4.822624702094427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we investigate an important research question in the car
sequencing problem, that is, what characteristics make an instance hard to
solve? To do so, we carry out an Instance Space Analysis for the car sequencing
problem, by extracting a vector of problem features to characterize an instance
and projecting feature vectors onto a two-dimensional space using principal
component analysis. The resulting two dimensional visualizations provide
insights into both the characteristics of the instances used for testing and to
compare how these affect different optimisation algorithms. This guides us in
constructing a new set of benchmark instances with a range of instance
properties. These are shown to be both more diverse than the previous
benchmarks and include many hard to solve instances. We systematically compare
the performance of six algorithms for solving the car sequencing problem. The
methods tested include three existing algorithms from the literature and three
new ones. Importantly, we build machine learning models to identify the niche
in the instance space that an algorithm is expected to perform well on. Our
results show that the new algorithms are state-of-the-art. This analysis helps
to understand problem hardness and select an appropriate algorithm for solving
a given car sequencing problem instance.
Related papers
- Exploratory Landscape Analysis for Mixed-Variable Problems [0.7252027234425334]
We provide the means to compute exploratory landscape features for mixed-variable problems where the decision space is a mixture of continuous, binary, integer, and categorical variables.
To further highlight their merit for practical applications, we design and conduct an automated algorithm selection study.
Our trained algorithm selector is able to close the gap between the single best and the virtual best solver by 57.5% over all benchmark problems.
arXiv Detail & Related papers (2024-02-26T10:19:23Z) - Algorithm Instance Footprint: Separating Easily Solvable and Challenging
Problem Instances [0.7046417074932257]
In black-box optimization, it is essential to understand why an algorithm instance works on a set of problem instances while failing on others.
We propose a methodology for formulating an algorithm instance footprint that consists of a set of problem instances that are easy to be solved and a set of problem instances that are difficult to be solved.
arXiv Detail & Related papers (2023-06-01T09:28:06Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
Pairwise learning refers to learning tasks where the loss function depends on a pair instances.
Online descent (OGD) is a popular approach to handle streaming data in pairwise learning.
In this paper, we propose simple and online descent to methods for pairwise learning.
arXiv Detail & Related papers (2021-11-23T18:10:48Z) - Generating Instances with Performance Differences for More Than Just Two
Algorithms [2.061388741385401]
We propose fitness-functions to evolve instances that show large performance differences for more than just two algorithms simultaneously.
As a proof-of-principle, we evolve instances of the multi-component Traveling Thief Problem(TTP) for three incomplete TTP-solvers.
arXiv Detail & Related papers (2021-04-29T11:48:41Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies.
We present a number of applications where the use of multiple geometric models improves accuracy.
These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
arXiv Detail & Related papers (2021-03-25T14:35:07Z) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously.
We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
arXiv Detail & Related papers (2021-03-24T23:11:32Z) - Generalization in portfolio-based algorithm selection [97.74604695303285]
We provide the first provable guarantees for portfolio-based algorithm selection.
We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
arXiv Detail & Related papers (2020-12-24T16:33:17Z) - Evolving test instances of the Hamiltonian completion problem [0.7734726150561086]
We propose a new methodology to generate a diverse set of instances by using an evolutionary algorithm.
We analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance.
arXiv Detail & Related papers (2020-10-05T20:04:58Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
We study the widely adopted ancestral sampling algorithms for auto-regressive language models.
We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation.
We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
arXiv Detail & Related papers (2020-09-15T17:28:42Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms.
We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
arXiv Detail & Related papers (2020-01-29T09:40:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.