Combinatorial Optimization Problems

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:

 

The Kakuro game as a CSP

Constraint satisfaction problems

The description of the feasible set follows the general CSP framework involving variables, domains, and constraints. The objectives are usually transformed in constraint(s). The team proposes efficient constraint propagation algorithms and intelligent tree search methods based on learning and SAT-inspired techniques.

Some publications on CSP

 

A 2-variable integer programming problem and a valid inequality

Mixed Integer linear programming problems

The feasible set and objective(s) involve only linear expressions on integer or fractional variables. The team carries out researches on valid inequalities and decomposition methods for special classes on MILPS, as well as generic solution methods for multiobjective MILPS.

Some publications on MILP

 

A flow-shop sheduling problem

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

 

An employee timetabing problem

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. Hyrbrid methods are also develop 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 routinf 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.