A Combinatorial Optimization Problem (COP) consists in the search for a solution in a discrete set (the feasible set) such that a (possibly multidimensional) function is optimized, the team contributions can be labeled according to the considered specification of the feasible set. One of the team objectives is to study the problems belonging to the categories below so as to, in fine, provide efficient tools to solve them optimally. In practice, the problems encountered often integrate two or more subproblems, such as integrated production scheduling and transportation problems. The ROC team carries out researches in the following COP:

Scheduling energy consuming jobs on parallel machines

Scheduling Problems

The feasible set is a set of schedules given by the ad-hoc specification of how a set of tasks can be positioned in time under temporal constraints (precedences, release dates, deadlines) and, possibly, using limited resources. The team considers various scheduling contexts (machine scheduling, resource-constrained project scheduling) and objectives (makespan, maximum lateness, fairness, total completion times). The team proposes resource constraint propagation algorithms, compact and extended MILP formulations, metaheuristics as well as complexity studies and dedicated solution algorithms. A special focus is also given on robust and multi-agent problems.

Some publications on scheduling problems

Reflector allocation and beam positionning for telecom satellites

Resource allocation problems

The feasible set is an assignment of resources to tasks without the scheduling part of the task, or with an already fixed scheduling. The objective is to minimize an assignment cost function subject to various constraints. This includes frequency assignment problems, employee timetabling, production planning, energy assignment, knapsack-like problems... The team mainly considers solution approaches based on CSPs and/or MILP formulations. Hybrid methods are also developed for solving complex integrated resource allocation and scheduling problems.

Some publications on resource allocation problems

An m-peripatetic vehicle routing problem

Vehicle routing and transportation problems

The feasible set is a set of vehicle routes satisfying different constraints on capacity, length, shape, time windows, etc. Besides time/distance classical objectives, the team considers other objectives, possibly in a multiobjective context, for example linked to multimodality, equity, energy consumption. The team considers MILP approaches, branch-and-cut-and-price techniques and metaheuristics, with a special focus given on multi-objective vehicle routing problems.

Some publications on vehicle routing problems

A graph coloring problem

Combinatorial optimization problems on graphs

The feasible set is a substructure of a possibly labeled graph (set of nodes, path) or an assignment of numerical values to the graph components (colors, potentials). Typical problems in this area (other than scheduling and routing problems) involve graph coloring problems, constrained shortest path problems, partition problems. The team proposes labeling algorithms for multi-objective multi-modal shortest paths problems, complexity studies and structural properties for identifying codes in graphs, partition and coloring problems.

Some publications on graph problems