Precedence constraint

From Glossary

Jump to: navigation, search

When ordering objects, like jobs to to be performed, this is a constraint that restricts the order: i must precede j, denoted LaTeX: \textstyle i << j. If order really means time, and if the model has decision variables LaTeX: t_i and LaTeX: t_j to denote the start times of LaTeX: i and LaTeX: j, resp., this precedence constraint can be written as LaTeX: \textstyle t_j \ge t_i + T_i, where LaTeX: T_i is the time job LaTeX: i takes. On the other hand, a precedence constraint need not correspond to real time. For example, LaTeX: i << j could mean if project LaTeX: j is not selected, we cannot select project LaTeX: i. In that case, suppose the model has binary variables LaTeX: x_i and LaTeX: x_j, where LaTeX: x_i=1 means project LaTeX: i is selected, and LaTeX: x_i=0 means it is not selected. Then, the precedence constraint LaTeX: i << j is represented as: LaTeX: x_i \le x_j.

Personal tools