Variable fixing for 0/1 variables is a well known technique to reduce the search space Integer Linear Programming. It is also referred to as reduced cost strengthening or reduced cost filtering in Constraint Programming. The reduced costs given by an optimal dual solution of the linear relaxation can be used for filtering inconsistent or suboptimal values. This filtering is incomplete as reduced costs only represent lower bounds of the increase of the objective (in a minimization context).

We are interested in achieving Arc-Consistency, i.e. a complete filtering, of global constraints with a cost variable and an assignment cost for each value. We assume that an ideal Integer Linear Programming formulation is available i.e the convex hull of the characteristic vectors of the supports is known. Under this assumption, we give a necessary and sufficient condition for a single dual solution to provide two reduced costs simultaneously giving the exact increase of the objective.

The presentation will illustrate a complete filtering algorithm based on reduced costs for the maximum weighted stable set problem in a chordal graph. The necessary and sufficient condition proposed will be applied and discussed on this example.