Hadrien Cambazard

AIJ Journal 2025 Journal Article

Arc-consistency with linear programming reduced costs (applied to stable set in chordal graphs)

• Guillaume Claus
• Hadrien Cambazard
• Hugo Apeloig
• Pierre Hoppenot

A well known technique to reduce the search space in integer programming is known as variable fixing or reduced cost strengthening. The reduced costs given by an optimal dual solution of the linear relaxation can be used to strengthen the bounds of the variables but this filtering is incomplete. We show how reduced costs can be used to achieve Arc-Consistency (AC), i. e. a complete filtering, of a global constraint with a cost variable and an assignment cost for each value. We assume that an ideal Integer Linear Programming (ILP) formulation is available i. e. the convex hull of the characteristic vectors of the supports is known. A detailed analysis of reduced cost based filtering is proposed. We characterize arc-consistency based on complementary slackness i. e. completeness of reasoning as opposed to only optimality. We also give a simple sufficient condition allowing a set of dual solutions to ensure arc-consistency through reduced costs. In practice, when the constraint has a such an ideal ILP, n dual solutions are always enough to achieve AC (where n is the number of variables of the global constraint). It extends the work presented in [26] for satisfaction problems and in [17] for the specific case of the minimum weighted alldifferent constraint. Our analysis is illustrated on constraints related to the assignment and shortest path problem and also demonstrated on the weighted stable set problem in chordal graphs. A novel AC algorithm is proposed in this latter case based on reduced costs.

ECAI Conference 2020 Conference Paper

Analysis of Reduced Costs Filtering for Alldifferent and Minimum Weight Alldifferent Global Constraints

• Guillaume Claus
• Hadrien Cambazard
• Vincent Jost

An incomplete filtering technique known as variable fixing has been used in integer programming for a long time. It relies on the reduced costs of the variables given by an optimal dual solution of the linear relaxation. Reduced-costs are used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known. Reduced cost based filtering was introduced in CP for a global constraint referred to as MINIMUM WEIGHT ALLDIFFERENT and to the best of our knowledge, no analysis of this filtering technique has ever been performed. We therefore propose an analysis of reduced costs filtering for this constraint, showing that arc-consistency can be achieved with reduced-costs of n dual solutions and that this bound is sharp. For ALLDIFFERENT, a single dual solution is enough. From a practical side, our end goal is the design of incomplete but anytime primal-dual filtering approaches. We illustrate this idea on the MINIMUM WEIGHT ALLDIFFERENT where a near-complete filtering can be done in shorter times.

ECAI Conference 2020 Conference Paper

New Randomized Strategies for the Color Coding Algorithm

• Lucie Pansart
• Hadrien Cambazard
• Nicolas Catusse

The color coding technique is used to solve subgraph isomorphism problems, in particular path problems. One color among C is randomly assigned to each vertex of the graph and if distinct colors are given to the vertices of the desired subgraph, it can be found efficiently by dynamic programming. These two phases are repeated until the subgraph is found with a high probability, which can require a large number of iterations. We propose new coloring strategies that take advantage of the graph structure to increase this probability and thus reduce the number of iterations. They provide a guaranteed improvement over the original color coding technique based on a particular structural parameter related to the bandwidth. When this parameter is smaller than the number C of colors, we prove that only C calls to the dynamic program are needed to find the subgraph.

ECAI Conference 2020 Conference Paper

Tree Search for the Sequential Ordering Problem

• Luc Libralesso
• Abdel-Malik Bouhassoun
• Hadrien Cambazard
• Vincent Jost

We study several generic tree search techniques applied to the Sequential Ordering Problem. This study enables us to propose a simple yet competitive tree search. It consists of an iterative beam search that favors search over inference and integrates prunings that are inspired by dynamic programming. The resulting method proves optimality on half of the SOPLIB instances, 10 to 100 times faster than other existing methods. Furthermore, it finds new best-known solutions on 6 among 7 open instances of the benchmark in a small amount of time. These results highlight that there is a category of problems (containing at least SOP) where an anytime tree search is extremely efficient (compared to classical meta-heuristics) but was underestimated.

ICAPS Conference 2019 Conference Paper

Lagrangian Decomposition for Optimal Cost Partitioning

• Florian Pommerening
• Gabriele Röger
• Malte Helmert
• Hadrien Cambazard
• Louis-Martin Rousseau
• Domenico Salvagnin

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an anytime algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions.

IJCAI Conference 2016 Conference Paper

A Branch-and-Price Algorithm for Scheduling Observations on a Telescope

• Nicolas Catusse
• Hadrien Cambazard
• Nadia Brauner
• Pierre Lemaire
• Bernard Penz
• Anne-Marie Lagrange
• Pascal Rubini

We address a parallel machine scheduling problem for which the objective is to maximize the weighted number of scheduled tasks, and with the special constraint that each task has a mandatory processing instant. This problem arises, in our case, to schedule a set of astronomical observations on a telescope. We prove that the problem is NP-complete, and we propose a constraint- programming-based branch-and-price algorithm to solve it. Experiments on real and realistic datasets show that the method provides optimal solutions very efficiently.

AAAI Conference 2016 Conference Paper

Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW

• Sylvain Ducomman
• Hadrien Cambazard
• Bernard Penz

ICAPS Conference 2013 Conference Paper

An Optimal Constraint Programming Approach to the Open-Shop Problem

• Arnaud Malapert
• Hadrien Cambazard
• Christelle Guéret
• Narendra Jussien
• André Langevin
• Louis-Martin Rousseau

This is a summary of the journal article published by Journal on Computing entitled "An Optimal Constraint Programming Approach to the Open-Shop Problem. " The article presents an optimal constraint programming approach for the Open-Shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and shows better results on a wide range of benchmark instances.

ECAI Conference 2010 Conference Paper

Knowledge Compilation for Itemset Mining

• Hadrien Cambazard
• Tarik Hadzic
• Barry O'Sullivan

We present a novel approach to itemset mining whereby the set of all itemsets are compiled into a compact form, closely related to binary decision diagrams. While there were previous attempts to utilize decision diagrams for storing the set of frequent itemsets this is the first approach that does not rely on backtrack search to generate such a set. Our empirical evaluation demonstrates that our approach is complementary to current approaches.

AAAI Conference 2008 System Paper

A Hybrid Approach to Domino Portrait Generation

• Hadrien Cambazard
• Eoin O’Mahony

A domino portrait is an approximation of an image using a given number of sets of dominoes. This problem was first stated in 1981. Domino portraits have been generated most often using integer linear programming techniques that provide optimal solutions, but these can be slow and do not scale well. We demonstrate a new approach that overcomes these limitations and provides high quality portraits. Our software combines techniques from operations research, artificial intelligence, and computer vision. Starting from a randomly generated template of blank domino shapes, a subsequent optimal placement of dominoes can be achieved in constant time when the problem is viewed as a minimum cost flow. The domino portraits one obtains are good, but not as visually attractive as optimal ones. Combining techniques from computer vision and local search we can improve our portraits to be visually indistinguishable from those generated optimally.