| phenomenon | machine learning for combinatorial optimization— “We survey different uses of ML to help solve combinatorial optimization problems and organize them along two orthogonal axes.” |
| claim-type | method— “We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so.” |
| method — evidence | — “This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems.” |
| transfer | from artificial intelligence (machine learning): using machine learning to learn heuristics for combinatorial optimization problems— “at leveraging machine learning to solve combinatorial optimization problems” | transfers[0] |
| mechanism | 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— “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.” | mechanisms[0] |
| mechanism | A FIELD IS INTRODUCED WITH TWO NAMES IN ITS FIRST SENTENCE: operations research, ALSO REFERRED TO AS PRESCRIPTIVE ANALYTICS, started in the second world war as an initiative to use mathematics and computer science to assist military planners. One discipline, two labels, and the second belongs to a different literature— “Operations research, also referred to as prescriptive analytics, started in the second world war as an initiative to use mathematics and computer science” | mechanisms[1] |
| mechanism | 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 THE RELEVANT DISTRIBUTION OF PROBLEMS to use for learning on a given task. Problems become instances drawn from a distribution, and that shift is the contribution— “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.” | mechanisms[2] |
| mechanism | 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— “This is bad news, in the sense that, for those problems, it is considered unlikely that an algorithm whose running time is polynomial in the size of the input exists. However, in practice, CO algorithms can solve instances with up to millions of decision variables and constraints. How is it possible to solve NP-hard problems in practical… | mechanisms[3] |
| mechanism | 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— “Rather, it aims to augment and automate the unwritten expert intuition (or lack of) on various existing algorithms. Given that these problems are highly structured, we believe it is relevant to augment solving algorithms with machine learning – and especially deep learning to address the high dimensionality of such problems.” | mechanisms[4] |
| mechanism | 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— “Explicitly defining what makes a TSP a likely one for the company is tedious, does not scale, and it is not clear how it can be leveraged when explicitly writing an optimization algorithm. We would like to automatically specialize TSP algorithms for this company.” | mechanisms[5] |
| mechanism | 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— “However, as for all CO algorithms, a fair comparison to another algorithm can only be done on an independent dataset of instances, as in (4). This is because through human trials and errors, the data used when building the algorithm leaks into the design of the algorithm” | mechanisms[6] |
| mechanism | 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— “and so we may expect CO algorithms that leverage ML models to fail when evaluated on unseen problem instances that are too far from what has been used for training the ML predictor. As previously motivated, it is also worth noting that traditional CO algorithms might not even work consistently across all possible instances of a problem… | mechanisms[7] |
| mechanism | 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— “Generalization in RL remains a challenging topic, probably because of the fuzzy distinction between a multi-task setting, and a large environment encompassing all of the tasks.” | mechanisms[8] |
| mechanism | 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— “Choosing how ambitious one should be in defining the characteristics of the distribution is a hard question. For instance, if the Montreal company expands its business to other cities, should they be considered as separate distributions, and learn one branching policy per” | mechanisms[9] |
| mechanism | THE SURVEY'S OWN CATEGORIES ARE DISCLAIMED AS NEITHER DISJOINT NOR EXHAUSTIVE, WHILE BEING USED: the sections ARE NOT NECESSARILY DISJOINT NOR EXHAUSTIVE BUT ARE A NATURAL WAY TO LOOK AT THE LITERATURE. A taxonomy offered with its two standard failure modes conceded and the word NATURAL doing the justifying— “sections are not necessarily disjoint nor exhaustive but are a natural way to look at the literature.” | mechanisms[10] |
| builds-on | machine learning (from CS/AI)— “leveraging machine learning to solve combinatorial optimization problems” | claim_relations[0] |
| sense | generalizing - 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— “Keeping the performances similar between the instances used for learning and the unseen ones is known in ML as generalizing” | senses[0] |
| sense | generalize - 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— “A model is said to generalize, if low objective values of (2) translate in low objective values” | senses[1] |
| sense | the 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— “we can only learn an algorithm that performs well on a finite set of TSPs sampled from this distribution (for instance, a set of historical instances collected by the company)” | senses[2] |
| edge | capacity —causes→ overfitting— “If a model (i.e., a family of functions) can represent many different functions, the model is said to have high capacity and is prone to overfitting: doing well on the training data but not generalizing to the test data” | concept_edges[0] |
| edge | generalization error —operationalised-as→ test dataset— “we estimate the generalization error by evaluating the trained model on a separate test dataset” | concept_edges[1] |
| for which use | limitation — every imitation-learning result: THE PERFORMANCE OF THE LEARNED POLICY IS BOUNDED BY THE EXPERT - it cannot exceed what it imitates— “the performance of the learned policy is bounded by the expert” | limitations[0] |
| for which use | limitation — any generalisation claim: the learned algorithm MAY NOT WORK PROPERLY ON OTHER INSTANCES FROM THE TRUE PROBABILITY DISTRIBUTION— “may not work properly on other instances from the true probability distribution” | limitations[1] |
| for which use | limitation — 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]— “In light of the current state of the field, the literature we survey is exploratory, i.e., we aim at highlighting promising research directions in the use of ML within CO, instead of reporting on already mature algorithms.” | limitations[2] |
| for which use | limitation — the coverage of the survey: unsupervised learning is excluded— “Because unsupervised learning has received so far little attention in conjunction with CO and its immediate use seems difficult, we are not discussing it any further.” | limitations[3] |
| for which use | limitation — 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— “The part of imitation learning presented here is limited compared to the current literature in ML.” | limitations[4] |
| for which use | limitation — 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— “In general, 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] |
| for which use | limitation — 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— “state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined” | limitations[6] |
| for which use | limitation — 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— “This is unknown, and cannot even be mathematically characterized in an explicit way. Because we do not know what is in this distribution, we can only learn an algorithm that performs well on a finite set of TSPs sampled from this distribution (for instance, a set of historical instances collected by the company), thus implicitly incorporating… | limitations[7] |
| for which use | limitation — 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— “Because (1) remains inaccessible, we estimate the generalization error by evaluating the trained model on a separate test dataset” | limitations[8] |
| evidence status note | mechanism — 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.— “Operations research, also referred to as prescriptive analytics, started in the second world war as an initiative to use mathematics and computer science” | mechanisms[1] |
| evidence status note | mechanism — 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.— “However, as for all CO algorithms, a fair comparison to another algorithm can only be done on an independent dataset of instances, as in (4). This is because through human trials and errors, the data used when building the algorithm leaks into the design of the algorithm” | mechanisms[6] |
| evidence status note | mechanism — 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.— “Choosing how ambitious one should be in defining the characteristics of the distribution is a hard question. For instance, if the Montreal company expands its business to other cities, should they be considered as separate distributions, and learn one branching policy per” | mechanisms[9] |
| replication | untested |
| limitation | in imitation-learning settings, performance is bounded by the (possibly suboptimal) expert— “the performance of the learned policy is bounded by the expert” | limitations[0] |
| limitation | learned algorithms may not generalize to unseen problem instances— “may not work properly on other instances from the true probability distribution” | limitations[1] |
| limitation | The literature surveyed is early-stage rather than mature, so the survey reports directions rather than settled algorithms.— “In light of the current state of the field, the literature we survey is exploratory, i.e., we aim at highlighting promising research directions in the use of ML within CO, instead of reporting on already mature algorithms.” | limitations[2] |
| limitation | Unsupervised learning is excluded from the survey.— “Because unsupervised learning has received so far little attention in conjunction with CO and its immediate use seems difficult, we are not discussing it any further.” | limitations[3] |
| limitation | The treatment of imitation learning is a simplification of the ML literature.— “The part of imitation learning presented here is limited compared to the current literature in ML.” | limitations[4] |
| limitation | Choosing which learning algorithm will perform best is outside the scope of the proposed methodology.— “In general, 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] |
| limitation | The expert decisions the learned models are fitted to are stated to be, in part, mathematically not well defined.— “state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined” | limitations[6] |
| limitation | The 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.— “This is unknown, and cannot even be mathematically characterized in an explicit way. Because we do not know what is in this distribution, we can only learn an algorithm that performs well on a finite set of TSPs sampled from this distribution (for instance, a set of historical instances collected by the company), thus implicitly incorporating… | limitations[7] |
| limitation | The quantity that defines success is stated to be inaccessible, and every reported figure is an estimate of it on held-out data.— “Because (1) remains inaccessible, we estimate the generalization error by evaluating the trained model on a separate test dataset” | limitations[8] |