Paula Amaral

Citation:

Amaral, P., and P. Barahona. "On Optimal Correction of Inconsistent Linear Constraints." Principles and Practice of Constraint Programming, CP'2002. Ed. Pascal Van Hentenryck. Vol. 2470. Lecture Notes in Computer Science, 2470. Springer, 2002. 33-46.

Abstract:

In practice one has often to deal with the problem of inconsistency between constraints, as the result, among others, of the comple\-xi\-ty of real models. To overcome these conflicts we can outline two major \mbox{actions}: removal of constraints or changes in the coefficients of the model. This last approach, that can be generically described as ``model corre\-ction" is the problem we address in this paper. The correction of the right hand side alone was one of the first approaches. The correction of both the matrix of coefficients and the right hand side introduces non linearity in the constraints. The degree of difficulty in solving the problem of the optimal correction depends on the objective function, whose purpose is to measure the closeness between the original and corrected model. Contrary to other norms, the optimization of the important Frobenius was still an open problem. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima, in terms of the solution of the Total Least Squares and the set of active constraints. These conditions justify a set of pruning rules, which proved, in preliminary experimental results, quite successful in a tree search procedure for determining the global minimizer.

Notes:

n/a