Luis Marques

We study arc-flow formulations obtained from transition graphs or transition hypergraphs of dynamic programs. These formulations are known for their generally strong linear relaxations and can be solved directly by a general purpose mixed integer linear programming (MILP) solver. An advantage of the MILP formulation is that one can include additional linear constraints in the form of resource constraints. In the absence of these, arc-flow formulations in graphs — resp. hypergraphs — form a totally unimodular — resp. totally dual integral — system, meaning the solution of the linear relaxation of the formulation is integer. A drawback of the MILP formulation is its size which can be pseudo-polynomial or exponential. We focus on cutting and packing problems with temporal constraints, i.e., temporal knapsack problem, temporal bin packing problem and their variants. We introduce preprocessing techniques and dominance rules to reduce the size of the transition graphs and hypergraphs: symmetries reduction, equivalent states aggregation using methods from the literature and detection of states that can be replaced by other states where some constraints are relaxed. Numerically, we confirm the strength of the linear relaxation of the arc-flow formulations, we observe that the sizes of the arc-flow formulations are significantly reduced by our techniques and show that these formulations are competitive and can outperform popular compact formulations from the literature.

Automated storage and retrieval systems have been studied for years in the context of warehouse optimization. The number of shelves and their height is generally determined in such a way that the number of retrieval operations per minute is maximized, i.e., response time is often more important than the space used by the device. In our specific study, we consider the case where capacity is highly constrained, and the efficiency of the system is not an issue. We call our problem the Automatic Storage Design (ASD) problem.

The goal of this course is to introduce second-year students to the C++ programming language. The concepts studied go from the most basic concepts to loops, functions, arrays, structured types and interaction with the user. Compilation and debugging mechanisms are also explained.

The goal of this course is to introduce first-year students to operational research using a popularization methodology. Divided in groups, the students present a subject related to operational research using a methodology such that people exterior to the domain can understand.

The goal of this course is to introduce fifth-year students to the basic concepts of constraint programming, a paradigm different from linear programming. Global constraints are introduced and domain filtering techniques relying on those constraints are explored. The course is based on the commercial solver OPL.

I animated a serious-game of the traveling salesman problem for children starting from 6 years old at the Data Party festival. During the first day of the festival we had classes of children to whom we introduced the concept of algorithms and how they can be used to solve problems. During the second day, we had a stand where people of any age could come and play the game.