Operations Research: How to allow users to tune model when an instance causes unsolvable result

Goal Programming: Balancing Multiple Objectives with Flexibility

In the field of operations research, decision-makers often face complex problems involving multiple, sometimes conflicting, objectives. Traditional optimization techniques, like linear programming, focus on optimizing a single objective function subject to a set of rigid constraints. However, real-world scenarios rarely adhere to such simplicity. Constraints can be flexible, and goals may need to be balanced rather than strictly optimized. Goal programming emerges as a powerful tool in these situations, enabling decision-makers to accommodate multiple objectives and find feasible solutions even when traditional models indicate infeasibility.

The Importance of Goal Programming

In practice, not all constraints are absolute; many represent soft constraints or goals that we aim to achieve if possible. Traditional linear programming treats constraints as rigid requirements that must be strictly satisfied for a solution to be feasible. If these constraints are conflicting or overly restrictive, the model may become infeasible, offering no solution.

Goal programming addresses this issue by introducing flexibility into the model without altering the original problem instance. It allows decision-makers to prioritize and balance multiple objectives, accommodating the inherent "softness" of real-world constraints. By permitting controlled deviations from certain constraints, goal programming transforms an unsolvable problem into a solvable one, enabling users to fine-tune their models effectively.

Benefits of Goal Programming

• Flexibility: Accommodates soft constraints, reflecting real-world conditions where not all requirements are absolute.
• Feasibility: Transforms infeasible models into solvable ones by allowing deviations from less critical constraints.
• Prioritization: Enables ranking objectives according to their importance, ensuring critical goals are addressed first.
• Tunability: Allows users to adjust goal priorities without changing the original problem instance, providing a powerful tool for model refinement.

How to Formulate Goal Constraints

Formulating goal constraints involves converting soft constraints and objectives into a form that allows for deviations, measured by deviational variables. This process introduces flexibility into the model, enabling the accommodation of conflicting objectives and the balancing of multiple goals.

Steps to Formulate Goal Constraints

1. Identify the Goals: List all desired outcomes and soft constraints.

2. Write the Requirement as a Regular Constraint: Formulate each goal as a standard constraint (equality or inequality).

3. Reformulate as a Goal Constraint: Introduce deviational variables to measure underachievement and overachievement.

The general method for formulating goal constraints is summarized in the table below:

   | Desired Situation         | Formulation of Goal Constraint           | Contribution to Objective Function |
   |---------------------------|------------------------------------------|------------------------------------|
   | $\text{LHS} \leq \text{RHS}$   | $\text{LHS} + d^- - d^+ = \text{RHS}$ | Minimize $d^+$                 |
   | $\text{LHS} = \text{RHS}$      | $\text{LHS} + d^- - d^+ = \text{RHS}$ | Minimize $d^- + d^+$           |
   | $\text{LHS} \geq \text{RHS}$   | $\text{LHS} + d^- - d^+ = \text{RHS}$ | Minimize $d^-$                 |

1. Establish the Objective Function: Create an objective function that minimizes the weighted sum of the deviational variables, reflecting the priorities of each goal.

Explanation of Deviational Variables

• Negative Deviational Variable ($d^-$): Measures the amount by which a goal is underachieved.
• Positive Deviational Variable ($d^+$): Measures the amount by which a goal is overachieved.

Note: For any particular goal, only one of the deviational variables ($d^-$ or $d^+$) will be positive in the optimal solution, as a goal cannot be both underachieved and overachieved simultaneously.

Example: Allocating Diamonds to Stores

Problem Statement

The owner of a chain of jewelry stores has to decide how to distribute parts of a new shipment of diamonds to five stores in a region. The first three stores are located in shopping malls. The following conditions have to be observed:

Absolutely Necessary (Hard Constraints):

• (a) Allocate between 1,000 and 1,200 carats in total to the five stores.
• (b) Store 5 must receive at least 300 carats of diamonds.

Desired Properties of the Allocation (Soft Constraints and Objectives):

• (c) The stores in the malls (Stores 1, 2, and 3) should receive at least 80% of all the diamonds, if possible.
• (d) The allocations to the stores in the malls should be equal to each other, if possible.
• (e) The probabilities of theft in the stores have been estimated to be 0.1%, 0.1%, 9%, 2%, and 3% for Stores 1 to 5, respectively. The owner would like to minimize the expected loss due to theft.

Goal Priorities:

• Priority 1: requirement (e) is 25 times as important as requirement (d)
• Priority 2: requirement (d) is 2 times as important as requirement (c)
• Priority 3: requirement (c) as a basline of priority. Ensure mall stores receive at least 80% of the diamonds.

Traditional Linear Programming Model

In the traditional model, all constraints, including the soft constraints and objectives, are treated as hard constraints.

Decision Variables

• $x_i$ : Number of carats allocated to Store $i$ (for $i = 1, 2, 3, 4, 5$).

Objective Function

• Minimize Expected Loss (e):
  $$\text{Minimize } Z = 0.001 x_1 + 0.001 x_2 + 0.09 x_3 + 0.02 x_4 + 0.03 x_5$$

Constraints

1. Hard Constraints (Absolutely Necessary):

• Total Allocation Bounds: $$ 1000 \leq x_1 + x_2 + x_3 + x_4 + x_5 \leq 1200 $$
• Minimum Allocation to Store 5: $$ x_5 \geq 300 $$

1. Soft Constraints (Treated as Hard Constraints):

• Mall Stores Allocation (c):
  $$
  x_1 + x_2 + x_3 \geq 0.8(x_1 + x_2 + x_3 + x_4 + x_5)
  $$

• Equal Allocation Among Mall Stores (d):
  $$
  x_1 = x_2 = x_3
  $$

Shortcomings of the Traditional Model

• Infeasibility: Due to the rigidity of hard constraints and conflicting objectives, the model may become infeasible, offering no solution.
• Lack of Flexibility: Cannot prioritize goals or allow for deviations, leaving the decision-maker without actionable solutions.

Goal Programming Approach

Goal programming introduces flexibility by converting objectives and soft constraints into goal constraints with deviational variables, allowing for prioritization and balancing of goals.

Step 1: Convert Soft Constraints and Objectives into Goal Constraints

(c) Mall Stores Allocation Goal

• Original Constraint: $$ x_1 + x_2 + x_3 \geq 0.8(x_1 + x_2 + x_3 + x_4 + x_5) $$
• Rewriting as Goal Constraint: $$ x_1 + x_2 + x_3 + d_1^- - d_1^+ = 0.8(x_1 + x_2 + x_3 + x_4 + x_5) $$
• Simplify: $$ 0.2(x_1 + x_2 + x_3) - 0.8 x_4 - 0.8 x_5 + d_1^- - d_1^+ = 0 $$
• Contribution to Objective Function: Minimize $d_1^-$ (underachievement).

(d) Equal Allocation Among Mall Stores

For Store 1 and Store 2:

• Original Constraint: $$ x_1 = x_2 $$
• Rewriting as Goal Constraint: $$ x_1 - x_2 + d_2^- - d_2^+ = 0 $$
• Contribution to Objective Function: Minimize $d_2^- + d_2^+$ (total deviation).

For Store 1 and Store 3:

• Original Constraint: $$ x_1 = x_3 $$
• Rewriting as Goal Constraint: $$ x_1 - x_3 + d_3^- - d_3^+ = 0 $$
• Contribution to Objective Function: Minimize $d_3^- + d_3^+$.

(e) Minimize Expected Loss Due to Theft

• Original Objective Function: $$ \text{Minimize } Z = 0.001 x_1 + 0.001 x_2 + 0.09 x_3 + 0.02 x_4 + 0.03 x_5 $$
• Setting a Target (Aspiration Level): Aim for minimal expected loss (e.g., $Z = 0$, recognizing it may not be attainable).
• Rewriting as Goal Constraint: $$ 0.001 x_1 + 0.001 x_2 + 0.09 x_3 + 0.02 x_4 + 0.03 x_5 + d_5^- - d_5^+ = 0 $$
• Contribution to Objective Function: Minimize $d_5^+$ (overachievement).

Step 2: Assign Weights Based on Goal Priorities

• Priority 1 (Minimize Expected Loss): Weight $W_5 = 50$ (25 times more important than Goal 2).
• Priority 2 (Equal Allocation): Weight $W_2 = W_3 = 2$ (2 times more important than Goal 3).
• Priority 3 (Mall Stores Allocation): Weight $W_1 = 1$.

Step 3: Formulate the Goal Programming Mathematical Model

Decision Variables

• $x_i \geq 0$: Allocation to Store $i$.
• $d_j^- \geq 0, \quad d_j^+ \geq 0$: Deviational variables for Goal $j$.

Objective Function

Minimize the weighted sum of deviational variables:

$$
\text{Minimize } Z = 50 d_5^+ + 2 (d_2^- + d_2^+ + d_3^- + d_3^+) + d_1^-
$$

Constraints

1. Hard Constraints (Absolutely Necessary):

• Total Allocation Bounds: $$ 1000 \leq x_1 + x_2 + x_3 + x_4 + x_5 \leq 1200 $$
• Minimum Allocation to Store 5: $$ x_5 \geq 300 $$

1. Goal Constraints:

• Mall Stores Allocation (c): $$ 0.2 x_1 + 0.2 x_2 + 0.2 x_3 - 0.8 x_4 - 0.8 x_5 + d_1^- - d_1^+ = 0 $$
• Equal Allocation Between Stores 1 and 2 (d): $$ x_1 - x_2 + d_2^- - d_2^+ = 0 $$
• Equal Allocation Between Stores 1 and 3 (d): $$ x_1 - x_3 + d_3^- - d_3^+ = 0 $$
• Expected Loss Minimization (e): $$ 0.001 x_1 + 0.001 x_2 + 0.09 x_3 + 0.02 x_4 + 0.03 x_5 + d_5^- - d_5^+ = 0 $$

1. Non-Negativity Constraints:

$$
x_i \geq 0, \qquad d_j^- \geq 0, \qquad d_j^+ \geq 0
$$

Step 4: Solve the Goal Programming Model

Using an appropriate optimization solver, we find the values of $x_i$ and $d_j^\pm$ that minimize $Z$.

Interpretation of Results

Assuming the optimal solution is:

• Allocations:

  • $x_1 = 466.69$ carats
  • $x_2 = 233.31$ carats
  • $x_3 = 0$ carats
  • $x_4 = 0$ carats
  • $x_5 = 300$ carats

• Total Allocation:
  
  $$
  
  x_1 + x_2 + x_3 + x_4 + x_5 = 1000 \text{ carats (meeting the minimum requirement)}
  
  $$

• Deviational Variables:

  • $d_1^- = \text{Positive value}$: Indicating underachievement of the mall stores allocation goal.
  • $d_1^+ = 0$.
  • $d_2^-, d_2^+, d_3^-, d_3^+ = \text{Positive values}$: Indicating deviations from equal allocation among mall stores.
  • $d_5^+ = 9.7$: Overachievement of expected loss.
  • $d_5^- = 0$.

Advantages of Goal Programming in This Example

• Feasibility: Provides a solution where the traditional model may be infeasible due to conflicting constraints.
• Prioritization: Allows the decision-maker to focus on the most critical objectives.
• Flexibility: Accommodates deviations from less critical goals to achieve the most important ones.
• Tunability: Users can adjust weights to explore different trade-offs without altering the problem instance.

Conclusion

Goal programming is a valuable method for addressing complex decision-making problems involving multiple objectives and soft constraints. By incorporating deviational variables and prioritizing goals, it allows decision-makers to find feasible solutions without altering the original problem instance.

Key Takeaways:

• Translates Soft Constraints into Goal Constraints: Allows for controlled deviations, reflecting real-world flexibility.
• Balances Conflicting Objectives: Prioritizes goals according to their importance.
• Maintains Feasibility: Provides solutions even when traditional models fail due to infeasibility.
• Adjustable: Enables fine-tuning of models through weight adjustments without changing the problem itself.

Goal programming empowers