TL;DR
This paper introduces the Deliberation Decision Support System (DDSS), a tool designed to help users make informed decisions about constrained optimization models after an initial solution has been found. By leveraging genetic algorithms to explore a broader range of feasible and infeasible solutions, DDSS provides insights beyond just the optimal solution, enabling better understanding of trade-offs and potential model revisions.
What Problem Does This Paper Address?
When working with constrained optimization models (COModels), finding an optimal solution is only the first step. A critical, yet often overlooked, challenge is the "deliberation problem": once a solution is found, how should a decision-maker interpret it? Should the model be implemented as is, or are there opportunities to improve the solution by relaxing constraints, acquiring more resources, or accepting a slightly worse objective value in exchange for significant resource savings? Traditional methods for post-solution analysis are often model-specific and don't readily apply when heuristic solvers, like genetic algorithms, are used to find solutions for complex COModels. This paper addresses the need for a more general and practical approach to support this post-solution deliberation process.
Methods
The core of the DDSS is its use of a genetic algorithm (GA) to heuristically solve COModels. Crucially, instead of just focusing on the single best solution, the DDSS collects a diverse set of "solutions of interest" (SoIs) generated during the GA's exploration of the solution space. These SoIs include:
- Feasible Solutions of Interest (FoIs): These are feasible solutions that have high objective values and often significant "slack" (unused capacity) in certain constraints. They represent good alternatives to the optimal solution, potentially offering different resource utilization profiles.
- Infeasible Solutions of Interest (IoIs): These are infeasible solutions that are "close" to being feasible (i.e., have minimal constraint violations) and also possess high objective values. They highlight the trade-offs at the boundary of feasibility and can inform decisions about how much it might "cost" (in terms of objective value) to satisfy certain constraints.
The DDSS provides a graphical user interface (GUI) to visualize these SoIs, offering tools for sensitivity analysis, "what-if" scenarios, and exploring the distribution of slacks across different constraints. The paper also outlines a "prioritized solutions" algorithm using heaps (priority queues) to efficiently manage and store these FoIs and IoIs during the GA run.
Datasets
The paper uses a Generalized Assignment Problem (GAP) as its primary example. It references "GAP12.1 from [1]" as a standard test problem, implying the use of publicly available benchmark instances for the Generalized Assignment Problem. No new datasets are introduced.
Key Insights and Ideas
- Beyond Optimality: The most valuable insights for decision-making often lie not just in the single optimal solution, but in a collection of "good" feasible and "near-feasible" infeasible solutions.
- The Value of Slack: Understanding slack in constraints is crucial for deliberation. High slack indicates potential for resource reallocation or relaxation, while low slack points to critical bottlenecks.
- Infeasibles as Information: Infeasible solutions near the feasibility boundary are not just "errors" but valuable data points that reveal the cost of satisfying constraints and the potential for improvement.
- GA as a Deliberation Tool: Population-based metaheuristics like GAs are well-suited for generating the diverse set of solutions needed for post-solution deliberation, as they naturally explore regions of the solution space beyond the absolute optimum.
Key Results
The paper demonstrates the DDSS's functionality through examples of a Generalized Assignment Problem. While specific quantitative results are not the primary focus, the paper illustrates how the DDSS can:
- Display multiple feasible solutions with high objective values and varying slack characteristics (Figure 2, Figure 8).
- Show the trade-offs between objective value and slack for specific resources (Table 1).
- Allow users to explore "what-if" scenarios, such as adding a unit of resource, and observe the impact on the solution pool (Figure 7, Figure 8).
- Identify infeasible solutions that offer high objective values with minimal constraint violations (Figure 3, Figure 4, Figure 6).
Limitations and Future Work
- Model Specificity: Currently, the DDSS primarily supports Generalized Assignment Problems (GAPs). The authors plan extensions to other types of COModels.
- Heuristic Choice: The paper uses a genetic algorithm but suggests that other solution heuristics should be investigated for their effectiveness in supporting deliberation.
- Generalization: While the paper presents a general framework, the specific implementation details and the effectiveness of the "prioritized solutions" algorithm for other problem types and metaheuristics would require further study.
- User Interface: The paper focuses on the conceptual design and functionality of the DDSS GUI, but further research into optimal visualization and interaction methods for decision-makers could be beneficial.
Summary updated