Predict+optimize for combinatorial optimization with uncertainty in the constraints

In this work, it is investigated whether the predict+optimize framework could be utilized for combinatorial optimization problems with a linear objective that have uncertainty in the constraint parameters, such that it outperforms prediction-error-based training. To this end, a predict+optimize formulation of the 0-1 knapsack problem is used,...

Models and heuristics for hard routing and knapsack problems

One of the world’s biggest challenges is that living beings have to share a limited amount of resources. As people of science, we strive to find innovative ways to better use these resources, to reach and positively affect more and more people. In the field of optimization, we aim at finding an optimal allocation of limited sets of resources to...

A combined forecasting and packing model for air cargo loading: A risk-averse framework

In this paper, we present a combined forecasting and optimization decision-support tool to assist air cargo revenue management departments in the acceptance/rejection process of incoming cargo bookings. We consider the case of a combination airline and focus on the passenger aircraft belly capacity. The process is dynamic (bookings are received...

Breaking the knapsack cryptosystem

We live in an online world: we date online, we do business online and we communicate online. To make sure this happens securely, almost all transferred data is encrypted by cryptosystems. This paper focuses on one of these: the knapsack cryptosystem of Merkle and Hellman, which relies on the hardness of solving the knapsack problem (1978). In...

Reinforcement Learning for the Knapsack Problem

Combinatorial optimization (CO) problems are at the heart of both practical and theoretical research. Due to their complexity, many problems cannot be solved via exact methods in reasonable time; hence, we resort to heuristic solution methods. In recent years, machine learning (ML) has brought immense benefits in many research areas,...

Strengthening the integrality gap for the capacitated facility location problem with LP-based rounding algorithms

This thesis studies the capacitated facility location problem, in which all clients have unit demand and all facilities have integral capacity. A linear relaxation is researched, with corresponding integrality gap bounded by a constant. Recently, such a linear relaxation has been found and proven using an LP-bounding algorithm. The formulation...