Conflict Resolution Module

This repository contains an implementation of a ConflictFinder module based on the publication of Olivier Guieu and John W. Chinneck (1998). It includes a ConflictRelaxer module that searches and relaxes infeasibilities based on a constraint hierarchy defined by the user.

Installation

To install the mip module, run the following command:

pip install mip>=1.9.0

Currently, the conflict.py module is separate from the main library. To use it, simply import it into your directory.

Usage

This module implements two classes: ConflictFinder and ConflictRelaxer. The former is an implementation of several IIS (Irreducible Infeasible Set) finder algorithms, while the latter is an implementation of a relaxation algorithm.

The ConflictFinder (The IIS finder)

TL;DR

cf = ConflictFinder(my_infeasible_model)
iis = cf.find_iis(method=conflict.IISFinderAlgorithm.DELETION_FILTER) # set of infeasible constraints

Long Explanation

An IIS is a set of infeasible constraints that cannot be reduced further. On an infeasible model, you can have one or many infeasible sets, and some of them can be linked between them. For example, let's define an infeasible linear model with four constraints:

• c1: x >= 3
• c2: x <= 1
• c3: y >= 3
• c4: y <= 1

We can see that there are two IIS in the upper set: IIS_1 = [c1,c2] and IIS_2 = [c3,c4]. However, if we add a fifth constraint:

• c5: y >= 4

We now have a third IIS: IIS_3 = [c4,c5]. Finding all the infeasibilities requires searching all the combinations, which is a hard problem. Usually, you only need to apply some relaxation algorithm once you are debugging, so this class will only provide you a way to find one IIS.

Currently, there are two methods implemented: DELETION_FILTER and ADDITIVE_ALGORITHM. These two methods only work for linear infeasibilities. MIP infeasibilities (when the feasible region does not contain integer solutions) are not supported yet.

The ConflictRelaxer (the hierarchy relaxation algorithm)

TL;DR

All the constraints have a _l{i} in the crt.name, where i is the level of importance in [1, ... , 7], where 1 is the lowest level, and 7 is the mandatory_level, which means that it is never to be relaxed.

cr = ConflictRelaxer(model=infeasible_model)
relaxed_model = cr.hierarchy_relaxer(relaxer_objective='min_abs_slack_val')

print(cr.iis_num_iterations)      # number of IIS iterations 
print(cr.iis_iterations)          # list of IIS iterations (constraintLists of each iteration)
print(cr.relax_slack_iterations)  # list of dicts with {crt:slack_value} on each IIS iteration 
print(cr.slack_by_crt)            # summary of all relaxation values (slacks) of all constraints when finished

Long Explanation

This algorithm is based on the feasOpt algorithm implemented on cplex. It receives an infeasible mip.Model and a mapper of all constraints with a certain level of ConstraintPriority (within 7 levels). Currently, the mapper automatically maps all the constraints based on the names with the suffix _l{i}. It starts looking for an IIS and will relax it by minimizing the absolute value of the deviation of the lowest level constraints s_{i}. The image below describes the function of the algorithm:

Currently, only the min_abs_slack_val is supported on the subproblem. In the future, we can add the min number of constraints relaxed or the sum of square value of the slack variables.

TODO

IIS algorithms

• Implement Deletion Filter Algorithm (LP)
• Implement Additive Algorithm (LP) !open issue #2
• Implement Deletion Filter Algorithm (IR-LC-BD) (MIPLP)
• Implement Deletion Filter Algorithm (LC-IR-BD) (MIPLP)

Relaxation module

• Implement a linear punishment relaxation algorithm abs value (based on a hierarchy structure)
• Implement relaxation based on the minimization of the square of slack var value
• Implement relaxation based on the minimization of the number of constraints relaxed
• Implement relaxation based on the minimization of the number of constraints relaxed

References

[1] http://www.sce.carleton.ca/faculty/chinneck/docs/GuieuChinneck.pdf