How to use conflict analysis

Conflict analysis is a way to automatically use the information obtained from infeasible nodes in the branch-and-bound tree.

Once a node is declared infeasible, SCIP automatically tries to infer a constraint that explains the reason for the infeasibility, in order to avoid similar situations later in the search. This explanation essentially consists of a constraint stating that at least one of its variables should have a bound different from the current infeasible node, because the current setting led to infeasibility. Clearly, all variables that are fixed in the current infeasible node would yield such a constraint (since this leads to infeasibility). The key point rather is to infer a "small" constraint that does the same job. SCIP handles this by several heuristics. For this, SCIP sets up a so-called (directed) conflict graph. The nodes in this graph correspond to bound changes of variables and an arc (u, v) means that the bound change corresponding to v is based on the bound change of u. In general, a node will have several ingoing arcs which represent all bound changes that have been used to infer (propagate) the bound change in question. The graph also contains source nodes for each bound that has been changed during branching and an artificial target node representing the conflict, i.e., the infeasibility. Essentially, SCIP heuristically constructs a cut in this graph that involves few "branching nodes". For details on the techniques that SCIP uses, we refer to the paper

Tobias Achterberg, Conflict Analysis in Mixed Integer Programming
Discrete Optimization, 4, 4-20 (2007)

For conflict analysis to work well, the author of a Constraint Handler or a Propagator has to implement three kinds of functionality:

1. If one detects infeasibility, one should initiate conflict analysis, see below.
2. During propagation, one should call the right functions to fix variables.
3. One should implement the so-called reverse propagation.

If this functionality is not implemented, SCIP will still work correctly, but cannot use the information of the constraint handler or the propagator for conflict analysis. In this case, each bound reduction performed by the constraint handler/propagator will be treated as if it had been a branching decision.

Initiating Conflict Analysis

If one detects infeasibility within propagation, one should do the following:

1. Call SCIPinitConflictAnalysis().
2. Inform SCIP about the variable bounds that are the reason for the detection of infeasibility via the functions SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), or SCIPaddConflictBinvar(). If there is more than one valid explanation of infeasibility, either one can be used. Typically, smaller explanations tend to be better.
3. Call SCIPanalyzeConflict() from a propagator or SCIPanalyzeConflictCons() from a constraint handler.

This functionality allows SCIP to set up the conflict graph and perform a conflict analysis.

Propagation

When propagating variable domains, SCIP needs to be informed that the deduced variable bounds should be used in conflict analysis. This can be done by the functions SCIPinferVarLbCons(), SCIPinferVarUbCons(), and SCIPinferBinvarCons() for constraint handlers and SCIPinferVarLbProp(), SCIPinferVarUbProp(), and SCIPinferBinvarProp() for propagators. You can pass one integer of information that should indicate the reason of the propagation and can be used in reverse propagation, see the next section.

Reverse Propagation

Reverse Propagation is used to build up the conflict graph. Essentially, it provides an algorithm to detect the arcs leading to a node in the conflict graph, i.e., the bound changes responsible for the new bound change deduced during propagation. Reverse Propagation needs to be implemented in the RESPROP callback functions of constraint handlers or propagators. These callbacks receive the following information: the variable which is under investigation (infervar), the corresponding bound change (bdchgidx, boundtype), and the integer (inferinfo) that has been supplied during propagation.

One can use SCIPvarGetUbAtIndex() or SCIPvarGetLbAtIndex() to detect the bounds before or after the propagation that should be investigated. Then the bounds that were involved should be passed to SCIP via SCIPaddConflictLb() and SCIPaddConflictUb(). If there is more than one valid explanation of infeasibility, either one can be used. Typically, smaller explanations tend to be better.

Details and (more) examples are given in Sections CONSRESPROP and PROPRESPROP.

Example

Consider the constraint handler cons_linearordering.c in the linear ordering example (see example/LOP directory). This constraint handler propagates the equations \(x_{ij} + x_{ji} = 1\) and triangle inequalities \(x_{ij} + x_{jk} + x_{ki} \leq 2\).

When propagating the equation and vars[i][j] is fixed to 1, the constraint handler uses

SCIP_CALL( SCIPinferBinvarCons(scip, vars[j][i], FALSE, cons, i*n + j, &infeasible, &tightened) );

Thus, variable vars[j][i] is fixed to 0 (FALSE), and it passes i*n + j as inferinfo.

When it propagates the triangle inequality and both vars[i][j] and vars[j][k] are fixed to 1, the constraint handler uses

SCIP_CALL( SCIPinferBinvarCons(scip, vars[k][i], FALSE, cons, n*n + i*n*n + j*n + k, &infeasible, &tightened) );

Thus, in this case, variable vars[k][i] is fixed to 0 and n*n + i*n*n + j*n + k is passed as inferinfo.

In reverse propagation, the two cases can be distinguished by inferinfo: if it is less than n*n, we deal with an equation, otherwise with a triangle inequality. The constraint handler can then extract the indices i, j (and k in the second case) from inferinfo.

In the first case, it has to distinguish whether vars[i][j] is fixed to 0 or 1 – by calling SCIPaddConflictLb() or SCIPaddConflictUb(), respectively, with variable vars[j][i]. In the second case, it is clear that the only possible propagation is to fix vars[i][j] to 0 when both vars[k][i] and vars[j][k] are fixed to 1. It then calls SCIPaddConflictLb() for both vars[k][i] and vars[j][k].