Return to Index
Operations Research Models and Methods
Models Section
Site Selection

More Logical Constraints

Again, suppose the builder looks at the solution just obtained and finds it unacceptable. First, he will allow design A to be specified at sites 1, 2, and/or 3 only if it is also used at site 4. Second, he wants the solution to use all three designs. To impose these logical constraints, we must find linear algebraic constraints that are satisfied only if the logical conditions are true and are violated when they are false.

The first condition is imposed by forming an implication constraint. The decision to use design A at sites 1, 2 or 3 must imply that the design A is chosen for site 4.

  • Design A: A1 + A2 +A3 3*A4 or A1 + A2 +A3 - 3*A4 0.

If any one of A1, A2 or A3 is set to 1, then A4 must be 1 for feasibility. The constraint does not imply that if A4 is selected, one of the others must also be selected, because the inequality is satisfied if A4 is 1 and all others are 0. We use the coefficient 3 for A4 so as not to restrict the selection of design A for the other sites.

The second condition requires that all three designs must be used. There are several ways to accomplish this, but here we define three new variables.

  • WA = 1 if design A is used and 0 otherwise
  • WB = 1 if design B is used and 0 otherwise
  • WC = 1 if design C is used and 0 otherwise

Now we add constraints that link the design decisions at the sites to the new variables. These are implication constraints.

  • Design A: A1 + A2 + A3 + A 4 4*WA
  • Design B: B1 + B2 + B3 + B 4 4*WB
  • Design C: C1 + C2 + C3 + C 4 4*WC

Now we add a constraint that requires all three designs to be 1.

  • Design Limit: WA + WB + WC = 3.

We solve the IP with the added constraints with the result shown below. Summarizing:

z = 38, A1 = 1, A4 = 1, B3 = 1, C2 = 1.

This solution has the same objective value as the solution obtained without the new constraints, so this is an alternative optimum solution. It is frequently the case with IP models that there are alternative optimum solutions. Although there is no easy way to find them all, adding constraints that better define the decision maker's goals may result in more acceptable solutions.


Note that we could have imposed the requirement that all three designs must be used by the constraint:

  • WA*WB*WC = 1.

Although this does accomplish the purpose, it is unacceptable because it is nonlinear. It is possible to solve nonlinear-integer problems, but it is usually much more difficult. Since every practical IP solution algorithm uses a linear programming algorithm as its base, the model must include only linear expressions.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved