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.
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
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.
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.