Functionality

The library redefines the basic finite-domain constraints and the search primitives minimize/2, min_max/2, indomain/1 and labeling/1 with versions that setup and trigger the simplex solver (on a relaxed continuous problem) in appropriate places. In more detail:

1.

During constraint setup, the constraints are posted literally to the fd-library and their relaxed form is posted to the eplex-library.

2.

At the beginning of the refedined minimize/2 or min_max/2, a corresponding LP-solver-demon is set up and the relaxation is solved once.

3.

Then the normal FD branch-and-bound procedure is started, using the user-supplied labeling routine.

4.

The modified version of indomain/1 employs a value-selection strategy based on the solution of the LP-relaxation: The variable is first labeled with the integer which is closest to the floating-point solution. On backtracking, the rest of the domain is tried.

5.

Variable instantiation (or, optionally, interval narrowing) can trigger the LP-solver: When a variable takes a value that is not close enough to the solution of the relaxation (or, optionally, when the narrowed interval excludes the solution of the relaxation), the solver is re-invoked. It computes a new solution, taking into account the current variable values and bounds.

The benefits from solver cooperation are:

• Infeasibility of the relaxed problem can prune the search.
• The cost of the relaxed solution is a lower bound to the cost of every integer solution. This cost bound is imposed as an additional constraint, and can thus cause FD-propagation and prune the search.
• The solution to the relaxed problem can be used as a labeling heuristics, hopefully leading to solution earlier.

FDPLEX Constraints

Several integer arithmetic constraints common to both eplex and fd can be passed to these two solvers via fdplex. The relaxed constraint is passed to the eplex solver.

fdplex: (?Vars :: ++Lo..++Hi)

Set Vars to the integer range Lo..Hi for both the range and fd attributes.

fdplex: (?Vars #:: ++Lo..++Hi)

Set Vars to the integer range Lo..Hi for both the range and fd attributes.

fdplex: (?T1 #= ?T2)

Constrains the linear term T1 to be equal to the linear term T2. The constraint is given to both the fd solver (in its complete form) and to th eplex solver (in relaxed form).

fdplex: (?T1 #>= ?T2)

Constrains the linear term T1 to be greater than or equal to the linear term T2. The constraint is given to both the fd solver (in its complete form) and to th eplex solver (in relaxed form).

fdplex: (?T1 #=< ?T2)

Constrains the linear term T1 to be less than or equal to the linear term T2. The constraint is given to both the fd solver (in its complete form) and to th eplex solver (in relaxed form).

fdplex: (?T1 #> ?T2)

Constrains the linear term T1 to be greater than the linear term T2. The constraint is given to both the fd solver (in its complete form) and to th eplex solver (in relaxed form).

fdplex: (?T1 #< ?T2)

Constrains the linear term T1 to be less than than the linear term T2. The constraint is given to both the fd solver (in its complete form) and to th eplex solver (in relaxed form).