Machine learning for combinatorial optimization: a methodological tour d'horizon
From MaRDI portal
Publication:2029358
Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Mixed integer programming (90C11) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)
Abstract: This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
Recommendations
- Machine learning and combinatorial optimization. Editorial
- Reinforcement learning for combinatorial optimization: a survey
- Optimization problems for machine learning: a survey
- Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art
- Learning heuristics for the TSP by policy gradient
Cites work
- A machine learning-based approximation of strong branching
- ASlib: a benchmark library for algorithm selection
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- DASH: dynamic approach for switching heuristics
- Deep learning
- Deep learning assisted heuristic tree search for the container pre-marshalling problem
- Generalized inverse multiobjective optimization with application to cancer therapy
- Generating new test instances by evolving in instance space
- Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 1113195 (Why is no real title available?)
- scientific article; zbMATH DE number 1843025 (Why is no real title available?)
- Integer Programming
- Inverse Optimization
- Learning a classification of mixed-integer quadratic programming problems
- Learning when to use a decomposition
- Machine learning. A probabilistic perspective
- Markov chain methods for the bipartite Boolean quadratic programming problem
- Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research
- On learning and branching: a survey
- Pattern recognition and machine learning.
- Recurrent policy gradients
- Reinforcement learning. An introduction
- Theoretical challenges towards cutting-plane selection
Cited in
(only showing first 100 items - show all)- Using computational learning strategies as a tool for combinatorial optimization
- Learning heuristics for the TSP by policy gradient
- A comparative study of the leading machine learning techniques and two new optimization algorithms
- A comment on: ``What makes a VRP solution good? The generation of problem-specific knowledge for heuristics
- Scenario-based learning for stochastic combinatorial optimisation
- Optimization problems for machine learning: a survey
- Data-driven algorithm selection and tuning in optimization and signal processing
- Learning chordal extensions
- Beyond graph neural networks with lifted relational neural networks
- Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning
- Learning to select operators in meta-heuristics: an integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem
- Reinforcement learning of simplex pivot rules: a proof of concept
- Reinforcement learning for the knapsack problem
- Neural large neighborhood search for routing problems
- Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times
- Learning variable activity initialisation for lazy clause generation solvers
- Injecting domain knowledge in neural networks: a controlled experiment on a constrained problem
- Learning to reduce state-expanded networks for multi-activity shift scheduling
- SeaPearl: a constraint programming solver guided by reinforcement learning
- Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems
- Boosting ant colony optimization via solution prediction and machine learning
- Learning the travelling salesperson problem requires rethinking generalization
- Generative deep learning for decision making in gas networks
- Predicting solutions of large-scale optimization problems via machine learning: a case study in blood supply chain management
- Catch me if you scan: data-driven prescriptive modeling for smart store environments
- Machine learning and combinatorial optimization. Editorial
- Generalization of machine learning for problem reduction: a case study on travelling salesman problems
- A novel solution approach with ML-based pseudo-cuts for the flight and maintenance planning problem
- Metaheuristics ``In the large
- Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art
- On combining machine learning with decision making
- Reinforcement learning for combinatorial optimization: a survey
- Deep-learning-based partial pricing in a branch-and-price algorithm for personalized crew rostering
- Guidelines for the computational testing of machine learning approaches to vehicle routing problems
- An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning
- BDD-based optimization for the quadratic stable set problem
- Towards a machine learning-aided metaheuristic framework for a production/distribution system design problem
- Constraint-based robust planning and scheduling of airport apron operations through simheuristics
- Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem
- scientific article; zbMATH DE number 1664960 (Why is no real title available?)
- Merging AI and OR to solve high-dimensional stochastic optimization problems using approximate dynamic programming
- Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems
- High generalization performance structured self-attention model for knapsack problem
- Learning to Approximate Industrial Problems by Operations Research Classic Problems
- A note on no-free-lunch theorem
- Improving variable orderings of approximate decision diagrams using reinforcement learning
- A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX
- Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information
- JANOS: An Integrated Predictive and Prescriptive Modeling Framework
- Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints
- Online Mixed-Integer Optimization in Milliseconds
- From numerical optimization method to learning optimization method
- Empirical decision model learning
- Set-to-Sequence Methods in Machine Learning: A Review
- Embedding decision trees and random forests in constraint programming
- Learning to schedule heuristics for the simultaneous stochastic optimization of mining complexes
- Multi-objective energy-efficient hybrid flow shop scheduling using Q-learning and GVNS driven NSGA-II
- Predicting the optimal period for Cyclic Hoist Scheduling Problems
- Multi-constructor CMSA for the maximum disjoint dominating sets problem
- Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems
- \textsc{Ner4Opt}: named entity recognition for optimization modelling from natural language
- A reinforcement learning approach for transaction scheduling in a shuttle‐based storage and retrieval system
- ReLU neural networks of polynomial size for exact maximum flow computation
- An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
- A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment
- Research trends in combinatorial optimization
- Towards Lower Bounds on the Depth of ReLU Neural Networks
- A data driven Dantzig-Wolfe decomposition framework
- The first AI4TSP competition: learning to solve stochastic routing problems
- A reinforced hybrid genetic algorithm for the traveling salesman problem
- Machine learning augmented approaches for hub location problems
- Adaptive solution prediction for combinatorial optimization
- Navigational guidance -- a deep learning approach
- Designing topological data to forecast bankruptcy using convolutional neural networks
- gym-flp: a Python package for training reinforcement learning algorithms on facility layout problems
- Machine learning-based online scheduling in distributed computing
- Tutorial on Amortized Optimization
- Targeted configuration of an SMT solver
- Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
- Integrating driver behavior into last-mile delivery routing: combining machine learning and optimization in a hybrid decision support framework
- Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications
- Learning to repeatedly solve routing problems
- Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning
- A differentiable approach to the maximum independent set problem using dataless neural networks
- CCGnet: a deep learning approach to predict Nash equilibrium of chance-constrained games
- Container port truck dispatching optimization using Real2Sim based deep reinforcement learning
- Predicting and optimizing marketing performance in dynamic markets
- Learning to sample initial solution for solving 0-1 discrete optimization problem by local search
- A unified pre-training and adaptation framework for combinatorial optimization on graphs
- Facility location decisions for drone delivery: a literature review
- Solution algorithms for dock scheduling and truck sequencing in cross-docks: a neural branch-and-price and a metaheuristic
- Explainable AI for operational research: a defining framework, methods, applications, and a research agenda
- A model-agnostic and data-independent tabu search algorithm to generate counterfactuals for tabular, image, and text data
- Graphs connected to isotopes of inverse property quasigroups: a few applications
- One-shot learning for MIPs with SOS1 constraints
- A deep reinforcement learning assisted simulated annealing algorithm for a maintenance planning problem
- Automatic MILP Solver configuration by learning problem similarities
- Outlier robust feature correspondence by learning based matching process
- Differentiable discrete optimization using dataless neural networks
- Machine learning constructives and local searches for the travelling salesman problem
This page was built for publication: Machine learning for combinatorial optimization: a methodological tour d'horizon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029358)
