Overview of constraint programming

What is constraint programming technology?

Constraint programming technology is used to find solutions to scheduling and combinatorial optimization problems. It is based primarily on computer science fundamentals, such as logic programming and graph theory, in contrast to mathematical programming, which is based on numerical linear algebra.

Constraint programming is invaluable when dealing with the complexity of many real-world sequencing and scheduling problems.

Whether the problem at hand is to schedule people, machines, or jobs of processes, you need constraint programming when there are complex logical and arithmetic relationships between decision variables, activities, and resources. A constraint programming model is expressed in a declarative fashion, by using decision variables, constraints, and objectives that must be minimized or maximized, as in mathematical programming. Lexicographical multi-criteria objectives are possible in the CP Optimizer feature of IBM® ILOG® CPLEX® Optimizers.

For example, constraint programming can be used as a heuristic to find solutions for mixed integer programs.

Constraint programming works first to reduce the set of possible values of the decision variables that satisfy all the constraints by using logical, graph-theoretic, arithmetic, and other arguments. When the deduction that some values from the decision variable’s domain are not possible, this information is propagated through the constraints perhaps enabling further deductions. Various search strategies are also used until a value is assigned to every decision variable, that is, until a solution is found. After a first solution is found, the search proceeds to find further solutions with better objective values.

A major benefit of using CP Optimizer for scheduling is that it requires no enumeration of time, that is, time buckets or time periods. Therefore, models can be formulated and solved efficiently, regardless of whether the relevant time scale to describe a scheduling problem is in milliseconds, minutes, or hours.

What is constraint-based scheduling?

Given a set of resources with given capacities, a set of activities with given processing times and resource requirements, and a set of temporal constraints between activities, a “pure” scheduling problem consists of deciding when to perform each activity so that both temporal constraints and resource constraints are satisfied. Most scheduling problems can easily be represented as instances of the constraint satisfaction problem: given a set of variables, a set of possible values (domain) for each variable, and a set of constraints between the variables, assign a value to each variable so that all the constraints are satisfied.

Several types of scheduling problems can be distinguished:
  • In disjunctive scheduling, each resource can perform at most one activity at a time. In cumulative scheduling, a resource can run several activities in parallel, as long as the resource capacity is not exceeded.
  • In non-preemptive scheduling, activities cannot be interrupted. Each activity A must be performed without interruption from its start time to its end time. In preemptive scheduling, activities can be interrupted at any time, for example, to allow some other activities perform.

Many real-life scheduling problems are complex combinations of these basic problems.

The power of modeling in constraint programming

Modeling in constraint programming revolves around the details of what is possible. For example, if you need to schedule a large number of resources and activities that respect capacity limitations, operational sequencing requirements, and business policies while meeting individual customer service goals, these modeling features are available to you:

  • Optional tasks
    • Model activities or processes that may or may not be performed in the final schedule.
    • Tasks can be grouped to match the work breakdown structure of a problem.
  • Precedence constraints
    • Model dependencies between tasks.
    • Can include a delay.
    • Can be applied to group of intervals.
  • Expressions on interval properties
    • Express typical scheduling costs such as tardiness costs, completion costs or total duration.
    • The presence status of an optional interval can be used to express completion costs or resource costs.
    • Can be applied to group of intervals.
  • Finite capacity reservoirs and resources
    • Specify limits on the number of tasks that can be performed in parallel with a common resources.
    • Set constraints on inventory levels.
  • Set-up times and batches - Calendars
    • State that some tasks cannot start or end on some dates.
    • State that some tasks that cannot overlap some dates.
    • Define resource breaks.
    • State that resource productivity changes over time.
  • Resource states
    • These modeling features can be used for combinatorial optimization problems.
    • Arithmetic linear and non-linear constraints.
    • Logical constraints.
  • Specialized constraints and expressions.
    • The all-different constraint: Enforces uniqueness for each variable in an array.
    • The pack constraint: Packs items into containers with finite capacity in one dimension (time, weight, budget, and so on).
    • The lexicographic constraint: Enforces a lexical ordering between groups of decision variables and is convenient to break symmetries.
    • The count expression.
    • The standard deviation expression.
  • Compatibility and incompatibility constraints
    • Define possible assignments for arrays of decision variables. They can be used, for instance, to model allowed transitions in a sequencing problem.

The model-and-run constraint programming optimizer

Some concepts are fundamental to the way constraint programming generates workable schedules and solutions from such complexity:

  • Awareness of time. CP Optimizer algorithms can determine the best sequence of activities that satisfy capacity limitations, setup times, maintenance requirements, availability restrictions, individual delivery due dates, and more by exploiting the information in the specialized scheduling and combinatorial optimization modeling constructs.
  • Aggressive elimination of possibilities. Domain reduction is the internal mechanism that makes difficult allocation, sequencing, and scheduling problems manageable. Every resource or activity to be scheduled has a certain number of possible values that can be systematically reduced until a solution is reached. Every reduction makes the problem easier since the optimizer propagates the results of the decision throughout the model.
  • Rapidly traversing the decision tree. The concept of systematically exploring a decision tree for feasible and efficient solutions relates to domain reduction. One benefit of this structured approach is the ability to move flexibly throughout the search space and to backtrack when early choices turn out to be dead ends.
  • Adaptive Search. The default search consists of several search techniques that are dynamically changed during the search by adapting to the problem at hand. The different search techniques include but are not restricted to LNS (large neighborhood search) and GA (genetic algorithms).

These concepts are built into the model-and-run optimizer of CP Optimizer but are also available to build a customized search.

The optimizer

  • Solves a large range of problems with default settings
  • Automatically removes redundant constraints
  • Reformulates the model to use constraints that are more efficiently propagated
  • Identifies conflicting constraints
  • Quickly finds feasible solutions for use in multi-model architectures such as column generation

The optimizer is tested on an extensive library of models, and the search engine can be tuned by parameters or callbacks.