Formele, exacte en metaheuristische methodes voor combinatorische optimalisatie
Bibliographic record
Abstract
Combinatorial optimization problems are ubiquitous in real life and hence a wide range of solving paradigms are available. Each paradigm has its own characteristics, which are potentially complementary. Therefore, investigating the possibility to combine different approaches might be beneficial for solving combinatorial problems. This dissertation exploits this research theme at two different levels. The first part of this dissertation exploits the relationships between solving paradigms at a general level. We investigate the combination of two sub-domains of Operations Research and Artificial Intelligence, namely Local Search and Knowledge Representation. We propose "declarative local search", which allows for specifying local search heuristics declaratively. Declarative local search is built on top of IDP, a Knowledge Base System. IDP consists of a set of inference methods for solving different tasks around a center knowledge base described in the formal language FO(·), an extension of first-order logic. Declarative local search enables local search heuristics to be synthesized from their formal descriptions. The framework has been proven empirically to be able to serve as a fast prototype tool for local search heuristics and also to function as an alternative back-end for some combinatorial problems that are traditionally difficult for formal systems such as IDP. In the second part, we study two particular combinatorial problems and how different solving methods are utilized to solve them. The first case study, namely the Intermittent Travelling Salesman Problem, presented in chapter 4, is a new variant of the Travelling Salesman Problem. The problem is inspired by real-world drilling/texturing applications where the temperature of the work-piece is taken into account. An exact branch-and-bound approach and four Variable Neighbourhood Search metaheuristics are proposed. The problem's characteristics are analyzed and an instance library is created and made publicly available for future research. The second case study, namely the Radiotherapy Scheduling Problem, presented in chapter 5, is a real scheduling problem at CHUM, a large cancer center in Montréal, Canada. We propose a two-phase approach where Mixed Integer Programming and Constraint Programming models are proposed for each phase. The algorithm is tested on a realistic dataset generated from real data provided by CHUM. The results show the dominance of a non-conventional Constraint Programming approach over the conventional Mathematical Programming for the problem. Summarized, the two parts of this dissertation investigate the relationships between solving paradigms at two complementary levels. We investigate the combined use of and the interaction between very different methodologies in a common domain of application.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.002 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".