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

Yoshua Bengio, Andrea Lodi, Antoine Prouvost · European Journal of Operational Research / arXiv · 2021 · operations-research · 10.1016/j.ejor.2020.07.063 · record bengio2021-ml-combinatorial
tag layer · index · concepts · authors · עברית
Where this record's text came from. faceted 2026-08 by reading the locally held text (pdftext); every evidence string verified as an exact substring of that text before merging. Claim relations is empty deliberately. The paper cites prior work densely, but every contrastive sentence I could find ('contrary to the aforementioned papers') compares two surveyed papers with each other, not this paper with named prior work; the paper never positions itself as building on, extending, contradicting or replicating a specific named study. Discipline straddles machine-learning and operations-research (the venue is EJOR and the paper explicitly addresses both communities); I recorded the ML side because the methodological framing is ML's. 2026-08-14 and 2026-08-17 schema-0.3 passes: every quote verified as an exact substring of the staged text and anchored at merge time; concept terms verified present; every edge endpoint an existing node.
Some quotes on this page contain (cid:NN). The PDF this text was extracted from encodes 2 characters in a way that names no letter, so the extractor could not say what they were. The quotes keep them because a quote is reproduced exactly or it proves nothing — the marks are the source’s, not the tagging’s.
This record’s own method is review, and the tags below follow from that. A review’s findings, quantities and statistics are things stated IN this paper, and some of them report results obtained elsewhere. No tag on this page names a different author. Measured across every review in this corpus, 81% of a review’s tags carry no citation at all — most of them are the review speaking. The corpus does not adjudicate the rest: read an unmarked tag as a claim this paper makes, not necessarily one it made first.
How to read this page. The article itself is not reproduced here — this paper is not cleared for redistribution, so what follows is the tag layer alone. The evidence sentences are withheld with the article. The table at the foot lists every tag the record carries; each row names the facet it belongs to, and the whose words column says whether the tag records the paper's own wording or the tagger's sentence about the paper. Every tag links to each other paper in the corpus carrying it. The machine-readable edition of the same thing is the TEI file beside this one, where the tags live in standOff, and the article is at its publisher via the link below. When we have changed our mind. Some entries in the table begin with a word in capitals and the reason for it. EVIDENCE CORRECTED — the finding still stands, but we had quoted the wrong sentence from the paper, and the quotation has been replaced with the right one. RETRACTED — the entry itself was wrong; it stays on the page, marked, with the reason, rather than being deleted. WITHDRAWN AND REPLACED — the entry was wrong, and a corrected version of it appears in the entries below. Each mark carries its own reason, in brackets, because the reasons differ from one entry to the next. An entry we have WITHDRAWN is removed from this page and kept in the record, with its reason. A line reading Audit and a date is a later re-reading of the entry against its whole sentence: DOUBTFUL means it was kept, and the reason says what is loose about it. Quotation marks inside the tagger's sentence. Where a tag is the tagger's own sentence, a phrase in quotation marks inside it is borrowed from the paper — the tagger's wording around it is not. The paper's own sentence is the evidence quote for that row; on this page it is withheld with the article, and the article is at its publisher. Nothing inside quotation marks anywhere on this page is ours: if it is quoted, it is the paper's. Whose words a concept carries. A concept entry records a term the paper itself uses, so the term, the sense given for it, and its evidence are the paper's own words, quoted where the paper fixes them. This is the opposite of a sense entry in the tag table, which is the tagger's sentence about how the paper uses a term. Where a concept entry could not be grounded in the paper's words, the entry says so on its own row.
Other fields define these differently the same word, defined another way in another discipline
machine learning 14 fields · deep learning 11 fields · overfitting 6 fields

Tags on this paper

Every tag the record carries, each linking to every other paper in the corpus that carries it. A tag appears here whether or not its words occur in the article — the spans below are only the ones a sentence in this paper licenses. Of the 10 concept tags on this paper, 6 are grounded in a quoted sentence.
combinatorial optimization machine learning integer programming branch and bound reinforcement learning heuristic generalization error overfitting capacity test dataset HANDCRAFTED HEURISTICS ARE SAID TO FILL TWO DIFFERENT GAPS, AND ONE OF THEM IS DEFINITIONAL: state-of-the-art algorithms rely on handcrafted heuristics for decisions that are otherwise TOO EXPENSIVE TO COMPUTE OR MATHEMATICALLY NOT WELL DEFINED. The craft is standing in both for intractability and for the absence of a definition, and the two are named in one breath A FIELD IS INTRODUCED WITH TWO NAMES IN ITS FIRST SENTENCE: Quotation withheld to assist military planners. One discipline, two labels, and the second belongs to a different literature THE PAPER'S MAIN MOVE IS A RE-DESCRIPTION OF ITS OBJECTS AS SOMETHING ELSE: a main point is SEEING GENERIC OPTIMIZATION PROBLEMS AS DATA POINTS, and then INQUIRING WHAT IS Quotation withheld task. Problems become instances drawn from a distribution, and that shift is the contribution AN APPARENT CONTRADICTION BETWEEN A COMPLEXITY CLASS AND PRACTICE IS POSED AS THE PAPER'S OPENING QUESTION: for these problems IT IS CONSIDERED UNLIKELY that a polynomial-time algorithm exists - HOWEVER, IN PRACTICE, the algorithms solve instances with up to millions of variables and constraints - HOW IS IT POSSIBLE TO SOLVE NP-HARD PROBLEMS IN PRACTICAL TIME? The category and the practice disagree, and the disagreement is the subject WHAT IS TO BE AUTOMATED IS DESCRIBED AS UNWRITTEN, AND A PARENTHESIS CONCEDES IT MAY NOT EXIST: the aim is TO AUGMENT AND AUTOMATE THE UNWRITTEN EXPERT INTUITION **(OR LACK OF)** on various existing algorithms. Three words in brackets admit that the target of the automation might be absent, and the sentence continues as though it were not in doubt A DEFINITION IS DECLINED FOR THREE TRACTABILITY REASONS AND NONE OF THEM IS IMPOSSIBILITY: explicitly defining what makes an instance A LIKELY ONE for the company IS TEDIOUS, DOES NOT SCALE, AND IT IS NOT CLEAR HOW IT CAN BE LEVERAGED when writing the algorithm - so the definition is replaced by a wish to AUTOMATICALLY SPECIALIZE. The reasons for not defining are practical, and the paper says so plainly HUMAN TRIAL-AND-ERROR IS NAMED AS A LEAKAGE CHANNEL, WHICH IS WHY A COMPARISON NEEDS INDEPENDENT DATA: as for ALL such algorithms, A FAIR COMPARISON can only be done on AN INDEPENDENT DATASET of instances - BECAUSE THROUGH HUMAN TRIALS AND ERRORS, THE DATA USED WHEN BUILDING THE ALGORITHM LEAKS INTO THE DESIGN OF THE ALGORITHM, even without explicit training. The designer is a fitting procedure THE BASELINE IS SHOWN TO SHARE THE WEAKNESS BEING CHARGED AGAINST THE NEW METHOD: learned algorithms may be expected to FAIL ON UNSEEN INSTANCES TOO FAR FROM TRAINING - and IT IS ALSO WORTH NOTING that TRADITIONAL algorithms MIGHT NOT EVEN WORK CONSISTENTLY across all instances of a problem family, but TEND TO BE MORE ADAPTED TO PARTICULAR STRUCTURES. The complaint turns out to describe the incumbent as well A STANDING DIFFICULTY IS ATTRIBUTED TO A FUZZY DISTINCTION BETWEEN TWO DESCRIPTIONS OF ONE THING: generalization REMAINS A CHALLENGING TOPIC, PROBABLY BECAUSE OF THE FUZZY DISTINCTION BETWEEN A MULTI-TASK SETTING AND A LARGE ENVIRONMENT ENCOMPASSING ALL OF THE TASKS. The obstacle is not a missing result but an unresolved choice of description THE GRANULARITY OF A CATEGORY IS PRESENTED AS A DECISION WITH NO PRINCIPLED ANSWER, AND THE EXAMPLE IS CONCRETE: CHOOSING HOW AMBITIOUS ONE SHOULD BE IN DEFINING THE CHARACTERISTICS OF THE DISTRIBUTION IS A HARD QUESTION - if the company expands to other cities, SHOULD THEY BE CONSIDERED AS SEPARATE DISTRIBUTIONS, and one policy learned per city? Where one category ends and the next begins is a question the framework does not answer THE SURVEY'S OWN CATEGORIES ARE DISCLAIMED AS NEITHER DISJOINT NOR EXHAUSTIVE, WHILE BEING USED: the Quotation withheld A taxonomy offered with its two standard failure modes conceded and the word NATURAL doing the justifying operations research traveling salesman problem decision variables NP-hard deep learning heuristics generalizing policy combinatorial optimization (CO) traveling salesman problem (TSP) distribution of problem instances review

Legend

relation to other workclaim_relationshow this paper stands to another: agrees, contradicts, extends, qualifies
claim typeclaim_typethe shape of the claim: existence, mechanism, method, critique, prediction, null
concept edgeconcept_edgesan asserted relation between two concepts, with the sentence asserting it
conceptconceptsan idea the paper works with, quoted where the paper uses it
content tagcontent_tagsa finding, definition, quantity, statistic or variable named in the paper
limitationlimitationswhat the paper says its evidence cannot support
mechanismmechanismshow the reported effect is said to come about
methodmethodhow the paper produced its evidence
phenomenonphenomenonthe effect or regularity under study
sensesensesa distinct use of a term, quoted where the paper fixes it
transfertransfersa method or concept carried in from another field

The paper

The full text is not reproduced here. This article is not cleared for redistribution, so the page carries the tag layer only. Its evidence sentences are withheld; the grounding status remains with each tag, and the article itself is at https://doi.org/10.1016/j.ejor.2020.07.063. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 1 · claim_type 1 · concept_edges 2 · concepts 6 · content_tags 14 · limitations 9 · mechanisms 11 · method 1 · phenomenon 1 · senses 3 · transfers 1

Relations on this page carry a quotation for the claim. Where a relation was separately evidenced — and so tested against the vocabulary for its type — the row says so; none of 2 relations here carry that mark. The rest are the tagger’s reading of the sentence quoted beside them.

This record holds no controls. A layer is empty when the tagger recorded nothing in it — which is not the same as the paper having nothing to record.

facettagfieldconf.whose words
claim_typemethod
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
claim_typethe paper's words
phenomenonmachine learning for combinatorial optimization
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
phenomenonthe paper's words
methodreview
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: review
methodthe paper's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[0]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
about this quote: RE-SLICED. The acceptance footnote and licence notice are spliced INTO this sentence - "to use mathematics and computer science * Accepted to the European Journal of Operations Research. c(cid:13)2020. Licensed under the Creative Commons cbnd 1 to assist military planners" - so it cannot be quoted whole. The naming is at its head. 'c(cid:13)' is a copyright symbol that failed to map.
mechanisms[1]0.85the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[2]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[3]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[4]0.85the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[5]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
about this quote: RE-SLICED, AND MY OWN CUT-WORD GUARD IS WHAT CAUGHT IT. My first end key was "...even without e" - which is where a 240-character DEBUG PRINT had truncated the sentence while I was searching the file. I used the output of my own truncated display as a key. The guard refused it, and the real text is "even without explicit learning components". Slice from the FILE, never from a print of the file.
mechanisms[6]0.85the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[7]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[8]0.95the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
about this quote: EXTENDED: the first cut stopped before "and learn one branching policy per city?", which the tag depends on - the question mark carries the whole force of the point.
mechanisms[9]0.85the tagger's words
mechanismsmechanisms
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
mechanisms[10]0.95the tagger's words
limitationsin imitation-learning settings, performance is bounded by the (possibly suboptimal) expert
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: every imitation-learning result: Quotation withheld - it cannot exceed what it imitates
limitations[0]the tagger's words
limitationslearned algorithms may not generalize to unseen problem instances
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: any generalisation claim: the learned algorithm Quotation withheld
limitations[1]the tagger's words
limitationsThe literature surveyed is early-stage rather than mature, so the survey reports directions rather than settled algorithms.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: the standing of the survey's conclusions: THE LITERATURE WE SURVEY IS EXPLORATORY, I.E., WE AIM AT HIGHLIGHTING PROMISING RESEARCH DIRECTIONS ... INSTEAD OF RE[porting settled results]
limitations[2]the tagger's words
limitationsUnsupervised learning is excluded from the survey.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: the coverage of the survey: unsupervised learning is excluded
limitations[3]the tagger's words
limitationsThe treatment of imitation learning is a simplification of the ML literature.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: the imitation-learning material as a guide to that literature: THE PART OF IMITATION LEARNING PRESENTED HERE IS LIMITED COMPARED TO THE CURRENT LITERATURE IN ML
limitations[4]the tagger's words
limitationsChoosing which learning algorithm will perform best is outside the scope of the proposed methodology.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: any use of the methodology to choose between algorithms: IDENTIFYING WHICH ALGORITHM WILL PERFORM BEST IS AN OPEN RESEARCH QUESTION UNLIKELY TO HAVE A SIMPLE ANSWER, AND IS OUTSIDE OF THE SCOPE OF THE METHODOLOGY PRESENTED HERE
limitations[5]the tagger's words
limitationsThe expert decisions the learned models are fitted to are stated to be, in part, mathematically not well defined.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: a learned replacement for a solver heuristic: the decisions in question are ones that are either too expensive to compute or mathematically not well defined, so for some of them there is no formal target the model could be right or wrong about
limitations[6]1.0the tagger's words
limitationsThe distribution the method is supposed to learn cannot be characterised, so a finite set of collected instances silently becomes the definition of the problem class.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: a claim that a learned CO algorithm solves a problem class: the true distribution is unknown and cannot be characterised explicitly, so what is learned is whatever a finite collected set - for instance a company's historical instances - happens to contain
limitations[7]1.0the tagger's words
limitationsThe quantity that defines success is stated to be inaccessible, and every reported figure is an estimate of it on held-out data.
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
what this limits: any reported generalization error: the objective it estimates remains inaccessible, so the number is the model's performance on a particular held-out set and not the property itself
limitations[8]1.0the tagger's words
transfersusing machine learning to learn heuristics for combinatorial optimization problems
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
transfers[0]the tagger's words
conceptscombinatorial optimization
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
concepts[0]the paper's words
conceptsheuristic
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: heuristic
concepts[5]the paper's words
conceptsgeneralization error
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
concepts[6]the paper's words
conceptsoverfitting
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: overfitting
concepts[7]the paper's words
conceptscapacity
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: capacity
concepts[8]the paper's words
conceptstest dataset
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: test dataset
concepts[9]the paper's words
sensesgeneralizing - THE INFORMAL SENSE: performance stays similar between the instances used for learning and unseen ones, which is how the word is used throughout the survey
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
senses[0]1.0the tagger's words
sensesgeneralize - THE FORMAL SENSE, AGAINST SOMETHING INACCESSIBLE: low values of the empirical objective translating into low values of the true one, where the true one cannot be computed and is estimated on a test set instead
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
senses[1]1.0the tagger's words
sensesthe distribution of problems - AS WHATEVER WAS COLLECTED: unknown, not explicitly characterisable, and represented in practice by a finite set of historical instances, which is what the learned algorithm actually fits
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
senses[2]1.0the tagger's words
claim_relationsbuilds-on → machine learning (from CS/AI)
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
claim_relations[0]the tagger's words
concept_edgescapacity —causes→ overfitting
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
strength of the relation: 1
also in: capacity · overfitting
concept_edges[0]the tagger's words
concept_edgesgeneralization error —operationalised-as→ test dataset
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
strength of the relation: 1
concept_edges[1]the tagger's words
content_tagsmillions — scale CO solvers reach in practice
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.quantities[0]the tagger's words
content_tags2 — ways ML can improve a CO algorithm
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.quantities[1]the tagger's words
content_tags2 — survey axes the paper derives
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.quantities[2]the tagger's words
content_tagsML is a natural candidate to replace hand-crafted heuristic decisions
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.findings[0]the tagger's words
content_tagsadding learning need not compromise overall theoretical guarantees
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted.
content_tags.findings[1]the tagger's words
content_tagsthe surveyed CO problems are NP-hard
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.findings[2]the tagger's words
content_tagsgeneric optimization problems can be treated as data points
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.findings[3]the tagger's words
content_tagsdecision variables
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.variables[0]the tagger's words
content_tagsdistribution of problem instances
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.variables[1]the tagger's words
content_tagspolicy
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: policy
content_tags.variables[2]the tagger's words
content_tagscombinatorial optimization (CO)
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted.
content_tags.definitions[0]the tagger's words
content_tagstraveling salesman problem (TSP)
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.definitions[1]the tagger's words
content_tagsgeneralizing
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
also in: generalizing
content_tags.definitions[2]the tagger's words
content_tagsoperations research
Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.
content_tags.definitions[3]the tagger's words

Interpretive choices

Tags that could not be placed in the text:

What was deliberately not tagged, and why, is recorded per paper by the tagger. Where a paper has no such record, this page says so rather than implying that nothing was declined.

© 2026 Shir Sivroni · ORCID 0009-0000-2597-2824