In eplex, constraints added to a problem are removed on backtracking. However, it is sometimes possible to discover constraints that are valid for the whole problem, which the user wish to apply even after backtracking – such constraints are referred to as ‘global cuts’.
In addition, the user may want to remove some constraints from the problem being solved, because they do not help to constrain the problem, but they slow down the solving of the problem.
To support this, eplex allow constraints to be added to a cutpool associated with a problem, instead of directly to the problem. The main differences from the normal problem constraints are:
Logically, cutpool constraints are always valid for the problem, and so should be considered when the problem is solved. Unlike normal constraints, cutpool constraints are not necessarily added to the solver’s problem matrix, and if they are added, they are added only for the solving, and removed from the problem matrix after the solving.
When the external solver solves the problem, eplex ensures that the cutpool constraints are consistent with the problem, i.e. none of the constraints are violated. The cutpool constraints can either be added to the problem matrix immediately, or they can be checked for violation after the solver solves the problem. Any violated constraints are then added to the problem, and the problem resolved. This is repeated until either a fix-point is reached, where no constraints are violated, or if the external solver is unable to solve the problem.
If the external solver does not produce a solution, then:
This multiple invocation of the solver occurs within an eplex’s call to the external solver to solve a problem, and so the process should be transparent to the user, except that the setting of the timeout applies to each solver invocation, rather than to the whole solving process.
The user can specify how the cutpool constraints are treated: they can be either added to the problem matrix before invoking the solver, or only added if violated. In addition, cutpool constraints can be made inactive, in which case they are not considered for adding to the problem matrix at all (and are not checked for violations). This is provided for efficiency reason – if the user knows for certain constraints would not be violated by the solution, they can be made inactive. It is the user’s responsibility to ensure the correctness in this case.
Unlike normal problem constraints, cutpool constraints cannot add new variables to the problem, i.e. the constraint must only involve problem variables that are present in the problem during solver set up. This is because cutpool constraints are globally valid, and so cannot involve variables that may not exist after backtracking. Variables can be added to a problem before solver set up by posting constraints involving them, including reals/1, which simply declares variables as problem variables.
Additionally, each cutpool constraint belongs to a named group, specified when the constraint is added. This allows the user to classify the cutpool constraints into different groups, and then manipulate a groups of constraints as a whole, e.g. making them all inactive. A default group is predefined, to which cutpool constraints belongs unless specified otherwise. To add cutpool constraints to other groups, the group name must first be created with the cutpool_group option of lp_get/3.
Constraints are added to the cutpool using:
Add the constraints to the cut-pool associated with the problem specified by the handle. By default, the constraints belong to the default group, and are active and have the ‘add initially’ status set. These can be over-ridden by the Options argument. The predicate returns a list of indices for these constraints in Idxs.
Information on cutpool constraints can be obtained using the cutpool_info option of lp_get/3. The status of a cutpool constraint, such as its active status, can be set using the cutpool_option option of lp_set/3 – the change is non-logical, i.e. it is not undone on backtracking.
Using lp_get/3 and lp_set/3, the user can program their own algorithms to control how the cutpool constraints are treated when the problem is solved. For example, the user may want to make a whole group of constraints inactive because they seem to slow the solver down but do not produce better solutions. In this case, the user can use lp_get/3 to obtain all the current constraints in the group, and then use lp_set/3 to set these constraints to inactive.
As cutpool constraints are not added directly to the problem matrix, this affects the library predicates that deals with the problem state: