Back

Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

Yoshua BengioAndrea LodiAntoine Prouvost

article2018European Journal of Operational Research1,915 citations

Establishes a foundational methodological framework bridging operations research and machine learning to replace handcrafted heuristics with models trained on distributions of combinatorial optimization problems.

Listen

Modern industries rely heavily on discrete optimization to make critical operational decisions in supply chain logistics, transportation, finance, energy, and scheduling. However, many real-world problems are combinatorial in nature and mathematically complex, meaning exact solutions cannot be guaranteed in reasonable timeframes as problem sizes scale. Current state-of-the-art commercial and open-source solvers address this difficulty by embedding hand-crafted rules and heuristic approximations into their underlying algorithms. While effective, these heuristic rules are manually engineered, often rigid, and fail to exploit the specific, repeated patterns present in the problem distributions that specific organizations actually face.

The article provides a comprehensive methodological review of how machine learning can be systematically integrated into discrete optimization algorithms. It investigates the conceptual foundations, algorithmic structures, and practical considerations required to replace or augment manual heuristic rules with learned decision policies.

The review synthesizes emerging research across both the operations research and machine learning communities. It categorizes existing efforts along two main axes: how decision policies are trained (through supervised imitation of expert algorithms or direct trial-and-error reinforcement learning) and how machine learning models interact with the optimization solver (pure end-to-end prediction, high-level algorithm configuration, or repeated, iterative decision-making alongside an exact solver). The analysis examines how these combined systems operate across varying problem distributions and structured data representations.

Key findings show that machine learning is most effective when combined with existing exact solvers rather than replacing them entirely. End-to-end deep learning approaches that output solutions directly struggle to guarantee feasibility and suffer from degraded performance when applied to instances larger than those seen during training. In contrast, embedding learned models into exact frameworks—such as guiding variable selection, node exploration, or cut generation within branch-and-bound trees—retains formal theoretical guarantees for optimality and feasibility while accelerating execution. Furthermore, while imitation learning offers fast approximations of computationally expensive expert strategies, it is fundamentally capped by the expert's quality; reinforcement learning can discover novel and superior strategies from scratch, though it requires significantly more training time and complex reward engineering.

These findings have direct operational and strategic implications for organizations solving large-scale operational challenges. By training optimization software on an organization’s historical problem instances, decision-makers can build specialized solvers that perform substantially faster on daily operations without sacrificing mathematical correctness. This hybrid paradigm reduces computational costs, shortens decision latency for real-time tactical applications, and avoids the need for manual, case-by-case heuristic engineering.

Organizations and technology leaders should consider adopting a hybrid approach: retain classical exact solver architectures as the overarching backbone and deploy targeted machine learning models only to automate computationally heavy or poorly defined sub-decisions. When developing these systems, practitioners should define a targeted problem distribution, begin by imitating existing heuristics, and subsequently refine performance through reinforcement learning. Further work should prioritize standardized instance benchmarks, robust graph-based data representations, and transfer learning methods before broad commercial deployment is pursued.

While promising, the findings reflect an exploratory field with distinct limitations. Learned models struggle to generalize to problem instances that diverge significantly in size or structure from training data. In addition, highly expressive neural networks can introduce inference overhead that diminishes overall runtime gains if not carefully balanced. Decision-makers should view this technology as a high-potential innovation that requires rigorous domain-specific validation and safety guardrails prior to production rollout.

Mila – Québec Artificial Intelligence InstitutePolytechnique MontréalUniversité de Montréalcombinatorial problemsdata pointsmachine learningcombinatorial optimizationmachine learningdiscrete optimization
arXiv: 1811.06128
Cover for Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

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.

Topics

combinatorial problemsdata pointsmachine learningoptimization problemsquadratic assignment problems

Keywords

combinatorial optimizationmachine learningdiscrete optimizationprimal heuristicsimitation learningreinforcement learninglinear programmingheuristic tree searchdynamic programmingsupervised learning

Table of Contents

  • 1 Introduction
  • 1.1 Motivation
  • 1.2 Setting
  • 1.3 Outline
  • 2 Preliminaries
  • 2.1 Combinatorial Optimization
  • 2.2 Machine Learning
  • 3 Recent approaches
  • 3.1 Learning methods
  • 3.1.1 Demonstration
  • 3.1.2 Experience
  • 3.2 Algorithmic structure
  • 3.2.1 End to end learning
  • 3.2.2 Learning to configure algorithms
  • 3.2.3 Machine learning alongside optimization algorithms
  • 4 Learning objective
  • 4.1 Multi-instance formulation
  • 4.2 Surrogate objectives
  • 4.3 On generalization
  • 4.4 Single instance learning
  • 4.5 Fine tuning and meta-learning
  • 4.6 Other metrics
  • 5 Methodology
  • 5.1 Demonstration and experience
  • 5.2 Partial observability
  • 5.3 Exactness and approximation
  • 6 Challenges
  • 6.1 Feasibility
  • 6.2 Modelling
  • 6.3 Scaling
  • 6.4 Data generation
  • 7 Conclusions
  • References

Knowls

  1. Knowl 1 — Taxonomy of Machine Learning Integration in Combinatorial Optimization

    model/method

    The methodological framework for integrating machine learning (ML) into combinatorial optimization (CO) is organized along two orthogonal dimensions:

    1. Learning Paradigm:

      • Learning by Demonstration (Imitation Learning): A policy π\pi is trained via supervised learning to mimic the decisions of an expert algorithm or oracle πe\pi_e on state-action pairs, optimizing an action discrepancy loss without requiring explicit reward feedback.
      • Learning by Experience (Reinforcement Learning): A policy is trained through trial-and-error interactions modeled as a Markov Decision Process (MDP), optimizing the expected cumulative reward (return) directly without requiring an expert.

    2. Solver Interaction Structure:

      • End-to-End Learning: An ML model directly maps the raw instance definition to a complete solution without invoking a traditional CO algorithm.
      • Learning to Configure Algorithms: An ML model acts once per problem instance prior to solver execution to select global algorithmic parameters, decomposition strategies, or algorithm portfolios.
      • Machine Learning Alongside Optimization Algorithms: An ML model is repeatedly queried throughout the iterative execution of a master CO algorithm to make recurrent, low-level algorithmic decisions (such as branching variable selection, cutting plane selection, or primal heuristic scheduling).

  2. Knowl 2 — Multi-Instance Expected Performance Optimization Formulation

    equation

    Let I\mathcal{I} denote a set of combinatorial optimization problem instances and P\mathcal{P} a probability distribution over I\mathcal{I}. Let A\mathcal{A} be a family of algorithms, and let m:I×A→Rm: \mathcal{I} \times \mathcal{A} \to \mathbb{R} be a performance metric where lower values indicate superior performance (e.g., solution cost, solving time, or optimality gap).

    The true multi-instance optimization problem is defined as finding an algorithm a∈Aa \in \mathcal{A} that minimizes expected performance under P\mathcal{P}:

    min⁡a∈AEi∼P[m(i,a)]\min_{a \in \mathcal{A}} \mathbb{E}_{i \sim \mathcal{P}} [m(i, a)]

    Because the true distribution P\mathcal{P} is inaccessible analytically, the objective is approximated via empirical risk minimization over a finite dataset of training instances Dtrain={ik}k=1N\mathcal{D}_{\text{train}} = \{i_k\}_{k=1}^N drawn independently from P\mathcal{P}:

    min⁡a∈A1∣Dtrain∣∑i∈Dtrainm(i,a)\min_{a \in \mathcal{A}} \frac{1}{|\mathcal{D}_{\text{train}}|} \sum_{i \in \mathcal{D}_{\text{train}}} m(i, a)

  3. Knowl 3 — Learning Objective for Internal Solver Policies Under Stochasticity

    equation

    When machine learning parametrizes an internal algorithmic policy π∈Π\pi \in \Pi (such as a neural network πθ\pi_\theta with parameters θ∈Rp\theta \in \mathbb{R}^p) embedded within a solver, execution is subject to instance variation and sources of stochasticity τ\tau (e.g., randomized tie-breaking, asynchronous hardware execution, or solver random seeds). Letting a(π,τ)a(\pi, \tau) denote the stochastic execution of the algorithm with policy π\pi and randomness τ\tau, and m(i,a(π,τ))m(i, a(\pi, \tau)) denote the resulting performance measure on instance i∈Ii \in \mathcal{I}, the learning problem over the policy space Π\Pi is:

    min⁡π∈ΠEi∼P[Eτ[m(i,a(π,τ))∣i]]\min_{\pi \in \Pi} \mathbb{E}_{i \sim \mathcal{P}} \left[ \mathbb{E}_{\tau} [m(i, a(\pi, \tau)) \mid i] \right]

    When π\pi operates sequentially, the inner expectation Eτ\mathbb{E}_\tau corresponds to the expected return across trajectories generated by the transition dynamics p(s′,r∣s,a)p(s', r \mid s, a) of the internal solver environment.

  4. Knowl 4 — Surrogate Objective Formulation for Demonstration-Based Imitation Learning

    equation

    In demonstration-based policy learning for combinatorial optimization, the non-differentiable global performance metric m(i,a)m(i, a) is replaced by a surrogate supervised loss ℓ\ell defined over the decision/action space. Let P\mathcal{P} be the instance distribution, πe\pi_e be an expert policy (such as strong branching in Branch-and-Bound), ss denote the internal state of the algorithm, and π∈Π\pi \in \Pi be the learned policy.

    The training problem minimizes the expected imitation discrepancy over the state distribution induced by the expert policy:

    min⁡π∈ΠEi∼P[Es[ℓ(π(s),πe(s))∣i,πe]]\min_{\pi \in \Pi} \mathbb{E}_{i \sim \mathcal{P}} \left[ \mathbb{E}_{s} [\ell(\pi(s), \pi_e(s)) \mid i, \pi_e] \right]

    Here ℓ(⋅,⋅)\ell(\cdot, \cdot) is a task-dependent loss function (such as cross-entropy loss for classification or squared error for regression). A low surrogate loss does not formally guarantee an improvement in the true solver performance metric m(i,a)m(i, a), and deviations from the expert during testing can lead to compounding errors because the test state distribution diverges from the training distribution induced by πe\pi_e.

  5. Knowl 5 — Exactness Conditions for Machine Learning Components in Combinatorial Optimization

    theoretical result

    An optimization algorithm incorporating machine learning components retains its theoretical guarantees of exactness (global optimality and feasibility) if and only if all decisions produced by the ML model are restricted to valid solver choices:

    1. Branch-and-Bound Tree Search: Exactness is preserved if ML policies are used strictly for variable selection (branching on fractional variables of linear programming relaxations), node selection among open tree nodes, cutting plane selection from valid inequalities, or deciding whether to run heuristic routines.
    2. Loss of Exactness via Bounding: Exactness is broken if ML approximations replace rigorous lower bounds or upper bounds in the search tree (e.g., using a neural network to estimate lower bounds), as overestimation of lower bounds can lead to invalid node pruning and eliminate optimal integer solutions.
    3. End-to-End ML Solvers: Pure end-to-end ML architectures cannot offer optimality guarantees and generally provide only weak or structural feasibility guarantees unless specialized differentiable constraints (such as Sinkhorn layers or pointer mechanisms) or post-processing projection steps are enforced.

  6. Knowl 6 — Repeated Decision Architecture for ML Alongside Optimization Algorithms

    model/method

    In the 'ML alongside optimization' paradigm, a master combinatorial optimization algorithm (such as a Branch-and-Bound or Branch-and-Cut solver) controls the high-level tree search and exact bounding guarantees, while an internal machine learning policy is repeatedly queried at each algorithmic step to guide lower-level heuristic decisions.

    Key applications in mixed-integer linear programming (MILP) solvers include:

    • Branching Variable Selection: Replacing computationally expensive full strong branching (which solves exploratory LP relaxations for all fractional candidates) with a trained neural network or regression model that mimics strong branching scores using static and dynamic node features.
    • Cutting Plane Selection: Using a classifier or regression model to filter and select the most effective linear inequalities (e.g., approximating semidefinite programming bound improvements) without paying the computational cost of full separation.
    • Primal Heuristic Scheduling: Using a classifier to predict whether running a primal heuristic at a given node will successfully find an improved incumbent solution, preventing unnecessary computational overhead when the probability of improvement is low.

  7. Knowl 7 — Dual-Level Generalization in Machine Learning for Combinatorial Optimization

    definition

    Generalization in machine learning for combinatorial optimization operates across two distinct, nested levels:

    1. Instance-Level Generalization: The ability of a learned policy trained on a finite set of problem instances Dtrain∼P\mathcal{D}_{\text{train}} \sim \mathcal{P} to perform effectively on unseen problem instances drawn from P\mathcal{P}, as well as out-of-distribution instances differing in problem size (number of variables/constraints) or graph topology.
    2. State-Level Generalization: The ability of a sequential decision policy π\pi to select effective actions across unseen internal algorithmic states ss within the execution trajectory of a single optimization run, especially when solver execution drifts away from the state distribution seen during training.

  8. Knowl 8 — Single-Instance Learning Paradigm in Combinatorial Optimization

    model/method

    Single-instance learning is an edge case of ML for combinatorial optimization where a model is trained from scratch during the execution of a single problem instance, without requiring an external distribution of prior training instances.

    In this framework, the learning time is counted directly as part of the total solver running time. An expensive expert heuristic (e.g., strong branching) is executed at the top nodes of the Branch-and-Bound tree to collect state-action pairs. A lightweight model (e.g., a linear regressor or decision tree) is trained on-the-fly on these initial decisions and subsequently replaces the expert heuristic for all remaining nodes deeper in the search tree. Generalization in this setting applies exclusively at the state level (generalizing from top-of-tree states to deeper tree states) rather than across distinct problem instances.

  9. Knowl 9 — Trade-offs Between Demonstration and Experience in Algorithmic Policy Learning

    model/method

    Policy learning for combinatorial optimization exhibits fundamental methodological trade-offs between imitation learning (demonstration) and reinforcement learning (experience):

    • Demonstration (Imitation Learning):

      • Strengths: Sample-efficient training, stable supervised optimization, and effective for speeding up known computationally heavy heuristics (e.g., strong branching or semidefinite programming approximations).
      • Weaknesses: The learned policy's performance is strictly bounded by the expert's quality; susceptible to covariate shift and compounding error cascades when the policy visits states outside the expert's training trajectory.

    • Experience (Reinforcement Learning):

      • Strengths: Capable of discovering novel heuristics that outperform existing human-designed algorithms; flexible when multiple actions yield equivalent objective values.
      • Weaknesses: High sample complexity; prone to local optima in large search spaces; vulnerable to sparse reward challenges where feedback is only received upon solver termination unless surrogate reward shaping is applied.

    • Hybrid Warm-Starting: A standard hybrid methodology trains an initial policy on expert demonstrations and subsequently refines the policy through reinforcement learning with task reward signals.

  10. Knowl 10 — State Representation and Structural Inductive Biases via Graph Neural Networks

    model/method

    Representing the internal state of a combinatorial optimization problem for neural networks requires handling variable-sized, permutation-invariant input structures:

    • Bipartite Graph Formulation for MILP: A mixed-integer linear program subproblem at a search node is represented as an uncompressed bipartite graph G=(Vc,Vv,E)G = (V_c, V_v, E), where VcV_c is the set of constraint nodes, VvV_v is the set of variable nodes, and edges eij∈Ee_{ij} \in E represent non-zero constraint coefficients AijA_{ij}.
    • Graph Neural Network (GNN) Message Passing: Graph Convolutional Networks or Graph Attention Networks perform parameter-shared message passing between variable and constraint nodes. This maintains invariance to variable and constraint permutations and enables generalization across problem instances of varying dimensions without discarding matrix sparsity or structural relationships.

Coverage note — Specific experimental findings and implementations from individual third-party literature cited within the survey (e.g., specific empirical TSP neural architectures, MaxSAT portfolio tuners, or quadratic assignment setups) were consolidated into the core methodological taxonomy, exactness analysis, and mathematical formulations, which constitute the paper's original contribution.

References

  1. 1.Ahuja, R. K. and Orlin, J. B. (2001). Inverse Optimization. Operations Research, 49(5):771–783.
  2. 2.Andrychowicz, M., Denil, M., Gómez, S., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., and de Freitas, N. (2016). Learning to learn by gradient descent by gradient descent. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems 29, pages 3981–3989. Curran Associates, Inc.
  3. 3.Ansótegui, C., Heymann, B., Pon, J., Sellmann, M., and Tierney, K. (2019). Hyper-Reactive Tabu Search for MaxSAT. In Battiti, R., Brunato, M., Kotsireas, I., and Pardalos, P. M., editors, Learning and Intelligent Optimization, Lecture Notes in Computer Science, pages 309–325. Springer International Publishing.
  4. 4.Ansótegui, C., Pon, J., Sellmann, M., and Tierney, K. (2017). Reactive Dialectic Search Portfolios for MaxSAT. In Thirty-First AAAI Conference on Artificial Intelligence.
  5. 5.Applegate, D., Bixby, R., Chvátal, V., and Cook, W. (2007). The traveling salesman problem. A computational study. Princeton University Press.
  6. 6.Bahdanau, D., Cho, K., and Bengio, Y. (2015). Neural machine translation by jointly learning to align and translate. In ICLR’2015, arXiv:1409.0473.
  7. 7.Baltean-Lugojan, R., Misener, R., Bonami, P., and Tramontani, A. (2018). Strong sparse cut selection via trained neural nets for quadratic semidefinite outer-approximations. Technical report, Imperial College, London.
  8. 8.Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. (2017). Neural Combinatorial Optimization with Reinforcement Learning. In International Conference on Learning Representations.
  9. 9.Bengio, Y., Bengio, S., Cloutier, J., and Gecsei, J. (1991). Learning a synaptic learning rule. In IJCNN, pages II–A969.
  10. 10.Bischl, B., Kerschke, P., Kotthoff, L., Lindauer, M., Malitsky, Y., Fréchette, A., Hoos, H., Hutter, F., Leyton-Brown, K., Tierney, K., and Vanschoren, J. (2016). ASlib: A benchmark library for algorithm selection. Artificial Intelligence, 237:41–58.
  11. 11.Bishop, C. M. (2006). Pattern Recognition and Machine Learning. springer.
  12. 12.Bonami, P., Lodi, A., and Zarpellon, G. (2018). Learning a Classification of Mixed-Integer Quadratic Programming Problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, pages 595–604. Springer, Cham.
  13. 13.Chan, T. C. Y., Craig, T., Lee, T., and Sharpe, M. B. (2014). Generalized Inverse Multiobjective Optimization with Application to Cancer Therapy. Operations Research, 62(3):680–695.
  14. 14.Conforti, M., Conrnuéjols, G., and Zambelli, G. (2014). Integer Programming. Springer.
  15. 15.Creswell, A., White, T., Dumoulin, V., Arulkumaran, K., Sengupta, B., and Bharath, A. A. (2018). Generative Adversarial Networks: An Overview. IEEE Signal Processing Magazine, 35(1):53–65.
  16. 16.Dai, H., Dai, B., and Song, L. (2016). Discriminative Embeddings of Latent Variable Models for Structured Data. In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2702–2711, New York, New York, USA. PMLR.
  17. 17.Dey, S. and Molinaro, M. (2018). Theoretical challenges towards cuttingplane selection. Mathematical Programming, 170:237–266.
  18. 18.Emami, P. and Ranka, S. (2018). Learning Permutations with Sinkhorn Policy Gradient. arXiv:1805.07010 [cs, stat].
  19. 19.Finn, C., Abbeel, P., and Levine, S. (2017). Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1126–1135, International Convention Centre, Sydney, Australia. PMLR.
  20. 20.Fischetti, M. and Lodi, A. (2011). Heuristics in Mixed Integer Programming, volume 3, pages 2199–2204. Wiley Online Library.
  21. 21.Fitzgerald, T., Malitsky, Y., O’Sullivan, B., and Tierney, K. (2014). ReACT: Real-Time Algorithm Configuration through Tournaments. In Seventh Annual Symposium on Combinatorial Search.
  22. 22.Fortun, M. and Schweber, S. S. (1993). Scientists and the legacy of world war ii: The case of operations research (or). Social Studies of Science, 23(4):595–642.
  23. 23.Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A. (2019). Exact combinatorial optimization with graph convolutional neural networks. arXiv preprint arXiv:1906.01629.
  24. 24.Gendreau, M. and Potvin, J.-Y., editors (2010). Handbook of metaheuristics, volume 2. Springer.
  25. 25.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017). Neural Message Passing for Quantum Chemistry. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1263–1272, International Convention Centre, Sydney, Australia. PMLR.
  26. 26.Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep Learning. MIT press.
  27. 27.He, H., Daume III, H., and Eisner, J. M. (2014). Learning to Search in Branch and Bound Algorithms. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q., editors, Advances in Neural Information Processing Systems 27, pages 3293–3301. Curran Associates, Inc.
  28. 28.Hochreiter, S., Younger, A. S., and Conwell, P. R. (2001). Learning to learn using gradient descent. In Dorffner, G., Bischof, H., and Hornik, K., editors, Artificial Neural Networks — ICANN 2001, pages 87–94, Berlin, Heidelberg. Springer Berlin Heidelberg.
  29. 29.Hoos, H. H. (2012). Automated Algorithm Configuration and Parameter Tuning. In Hamadi, Y., Monfroy, E., and Saubion, F., editors, Autonomous Search, pages 37–71. Springer Berlin Heidelberg, Berlin, Heidelberg.
  30. 30.Hottung, A., Tanaka, S., and Tierney, K. (2017). Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem. arXiv:1709.09972 [cs]. arXiv: 1709.09972.
  31. 31.Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. (2017). Imitation Learning: A Survey of Learning Methods. ACM Computing Surveys, 50(2):21:1–21:35.
  32. 32.Karapetyan, D., Punnen, A. P., and Parkes, A. J. (2017). Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem. European Journal of Operational Research, 260(2):494–506.
  33. 33.Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. (2017a). Learning Combinatorial Optimization Algorithms over Graphs. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 6348–6358. Curran Associates, Inc.
  34. 34.Khalil, E. B., Bodic, P. L., Song, L., Nemhauser, G., and Dilkina, B. (2016). Learning to Branch in Mixed Integer Programming. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, pages 724–731, Phoenix, Arizona. AAAI Press.
  35. 35.Khalil, E. B., Dilkina, B., Nemhauser, G. L., Ahmed, S., and Shao, Y. (2017b). Learning to Run Heuristics in Tree Search. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 659–666.
  36. 36.Kool, W. W. M. and Welling, M. (2018). Attention Solves Your TSP, Approximately. arXiv:1803.08475 [cs, stat].
  37. 37.Kruber, M., Lübbecke, M. E., and Parmentier, A. (2017). Learning When to Use a Decomposition. In Integration of AI and OR Techniques in Constraint Programming, Lecture Notes in Computer Science, pages 202–210. Springer, Cham.
  38. 38.Larsen, E., Lachapelle, S., Bengio, Y., Frejinger, E., Lacoste-Julien, S., and Lodi, A. (2018). Predicting Solution Summaries to Integer Linear Programs under Imperfect Information with Machine Learning. arXiv:1807.11876 [cs, stat].
  39. 39.Larson, R. C. and Odoni, A. R. (1981). Urban operations research. Number Monograph.
  40. 40.Li, K. and Malik, J. (2017). Learning to Optimize Neural Nets. arXiv:1703.00441 [cs, math, stat].
  41. 41.Liberto, G. D., Kadioglu, S., Leo, K., and Malitsky, Y. (2016). DASH: Dynamic Approach for Switching Heuristics. European Journal of Operational Research, 248(3):943–953.
  42. 42.Lindauer, M. and Hutter, F. (2018). Warmstarting of Model-Based Algorithm Configuration. In Thirty-Second AAAI Conference on Artificial Intelligence.
  43. 43.Lodi, A. (2009). MIP computation. In Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., and Wolsey, L., editors, 50 Years of Integer Programming 1958-2008, pages 619–645. Springer-Verlag.
  44. 44.Lodi, A. and Zarpellon, G. (2017). On learning and branching: A survey. TOP, 25(2):207–236.
  45. 45.Lombardi, M. and Milano, M. (2018). Boosting Combinatorial Problem Modeling with Machine Learning. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 5472–5478. International Joint Conferences on Artificial Intelligence Organization.
  46. 46.Mahmood, R., Babier, A., McNiven, A., Diamant, A., and Chan, T. C. Y. (2018). Automated Treatment Planning in Radiation Therapy using Generative Adversarial Networks. In Proceedings of Machine Learning for Health Care, volume 85 of Proceedings of Machine Learning Research.
  47. 47.Malitsky, Y., Merschformann, M., O’Sullivan, B., and Tierney, K. (2016). Structure-Preserving Instance Generation. In Festa, P., Sellmann, M., and Vanschoren, J., editors, Learning and Intelligent Optimization, Lecture Notes in Computer Science, pages 123–140. Springer International Publishing.
  48. 48.Marcos Alvarez, A., Louveaux, Q., and Wehenkel, L. (2014). A supervised machine learning approach to variable branching in branch-and-bound. Technical report, Université de Liège.
  49. 49.Marcos Alvarez, A., Louveaux, Q., and Wehenkel, L. (2017). A Machine Learning-Based Approximation of Strong Branching. INFORMS Journal on Computing, 29(1):185–195.
  50. 50.Marcos Alvarez, A., Wehenkel, L., and Louveaux, Q. (2016). Online Learning for Strong Branching Approximation in Branch-and-Bound. Technical report, Université de Liège.
  51. 51.Mascia, F., López-Ibáñez, M., Dubois-Lacoste, J., and Stützle, T. (2014). Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools. Computers & Operations Research, 51:190–199.
  52. 52.McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems. Mathematical Programming, 10(1):147–175.
  53. 53.Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT press.
  54. 54.Nagarajan, P., Warnell, G., and Stone, P. (2019). Deterministic implementations for reproducibility in deep reinforcement learning. In AAAI 2019 Workshop on Reproducible AI.
  55. 55.Nair, V., Dvijotham, D., Dunning, I., and Vinyals, O. (2018). Learning fast optimizers for contextual stochastic integer programs. In Conference on Uncertainty in Artifical Intelligence, pages 591–600.
  56. 56.Nowak, A., Villar, S., Bandeira, A. S., and Bruna, J. (2017). A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks. arXiv:1706.07450 [cs, stat].
  57. 57.Ravi, S. and Larochelle, H. (2017). Optimization as a model for few-shot learning. In International Conference on Learning Representations.
  58. 58.Schmidhuber, J. (1992). Learning to control fast-weight memories: An alternative to dynamic recurrent networks. Neural Computation, 4(1):131–139.
  59. 59.Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., and Dill, D. L. (2018). Learning a SAT Solver from Single-Bit Supervision. arXiv:1802.03685 [cs].
  60. 60.Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489.
  61. 61.Smith, K. A. (1999). Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research. INFORMS Journal on Computing, 11(1):15–34.
  62. 62.Smith-Miles, K. and Bowly, S. (2015). Generating new test instances by evolving in instance space. Computers & Operations Research, 63:102–113.
  63. 63.Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT press Cambridge, second edition.
  64. 64.Thrun, S. and Pratt, L. Y., editors (1998). Learning to Learn. Kluwer Academic.
  65. 65.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is All you Need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 5998–6008. Curran Associates, Inc.
  66. 66.Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph attention networks. In International Conference on Learning Representations.
  67. 67.Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer Networks. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems 28, pages 2692–2700. Curran Associates, Inc.
  68. 68.Wichrowska, O., Maheswaranathan, N., Hoffman, M. W., Colmenarejo, S. G., Denil, M., de Freitas, N., and Sohl-Dickstein, J. (2017). Learned Optimizers that Scale and Generalize. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3751–3760, International Convention Centre, Sydney, Australia. PMLR.
  69. 69.Wierstra, D., Förster, A., Peters, J., and Schmidhuber, J. (2010). Recurrent policy gradients. Logic Journal of the IGPL, 18(5):620–634.
  70. 70.Wolsey, L. A. (1998). Integer Programming. Wiley.
  71. 71.Özcan, E., Misir, M., Ochoa, G., and Burke, E. K. (2012). A Reinforcement Learning: Great-Deluge Hyper-Heuristic for Examination Timetabling. Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends, pages 34–55.

Citation

MLA
Bengio, Y., et al. “Machine Learning for Combinatorial Optimization: A Methodological Tour d'Horizon”. arXiv, 2018, http://arxiv.org/abs/1811.06128v2.
APA
Bengio, Y., Lodi, A., & Prouvost, A. (2018). Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon. arXiv. http://arxiv.org/abs/1811.06128v2
Chicago
Bengio, Y., A. Lodi, and A. Prouvost. 2018. “Machine Learning for Combinatorial Optimization: A Methodological Tour d'Horizon”. arXiv. http://arxiv.org/abs/1811.06128v2.
Harvard
Bengio, Y., Lodi, A. and Prouvost, A. (2018) “Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1811.06128v2.
Vancouver
1. Bengio Y, Lodi A, Prouvost A (2018) Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon. arXiv

BibTeX

@article{bengio2018machine,
  title = {Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon},
  author = {Bengio, Yoshua and Lodi, Andrea and Prouvost, Antoine},
  year = {2018},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1811.06128v2},
  eprint = {1811.06128}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF