SOLVING SYSTEMS OF DIFFERENCE CONSTRAINTS

In this paper we use the problem of determining the feasibility of system of difference constraints. A difference constraints is of the form x - y ≤ b, where x and y are numeric variables and b is a constant. Systems of difference constraints occur in many economic applications. For example, the unknowns x and y may represent the moment of times at which events are to occur. Each constraint can be viewed as stating that one event cannot occur too much later than another event. In the end, an experimental analysis of two heuristics is presented for the problem of the negative cycle’s detection.