Decrease the number of variables

Decreasing the number of variables, and thus reducing the size of the search space, is one model design principle to consider.

The unknowns of a given problem are typically represented in the model by decision variables. There are practical ways of decreasing the number of variables and thus reducing the size of the model and its search space.

Problems best solved with constraint-based programming are generally subject to intrinsic combinatorial growth. Even if reducing the domains of variables by propagating constraints makes it possible to reduce the search space, the initial size of this search space still remains a weighty factor in the execution time.

Principle

Consequently, good practice in designing a model should attempt to minimize the size of the search space in the first place. This size increases exponentially with the number of variables. Thus, limiting the number of such variables (even at the expense of enlarging their domains) can reduce the combinatorial complexity.

Example

This principle of reducing the number of decision variables can often be applied advantageously to resource allocation problems. For example, assume that C consumers must choose among R resources where:

  • all the resources are available to every consumer;

  • if consumer i chooses resource j, he or she incurs cost[i,j];

  • each consumer uses at most one resource.

First model

This problem is often represented in the following way:

  • Create C*R constrained integer variables supplieri,j with domain [0, 1] such that supplieri,j = 1 if consumer i uses resource j.

  • The constraints stating that each consumer uses at most one resource are represented this way: for each i, The summation over j=0 to R-1 of supplier [i,j] is less than or equal to 1.

  • The goal is to maximize The summation over i=0 to C-1 of the summation over j=0 to R-1 of cost[i,j] times supplier [i,j]

To evaluate the combinatorial complexity of the problem, consider the maximum number of configurations, called the apparent complexity of the problem. This figure is the size of the search space, that is, the worst case complexity of a generate and test algorithm.

In this model, the apparent complexity is 2R*C, which is around 1030 if R=C=10.

Second model: using fewer variables

With CP Optimizer, a more efficient model can be represented. The alternate model can be written this way:

  • Create a fake resource numbered 0.

  • Create C constrained integer variables supplieri with domain [0..R] so that

supplieri = 0 if consumer i uses no resource,

supplieri = j if consumer i uses resource j.

The constraints stating that each consumer uses at most one resource are necessarily satisfied, since a constrained integer variable can be fixed with only one value.

  • The goal is to maximize Summation over i=0 to C-1 of cost indexed by i and supplier i.

The maximum number of solutions of this representation is (R+1)C, which is 1110 if R=C=10. This value is much smaller than 1030 from the first model.