Two-Stage Optimization: Primal-based Column-and-constraint Generation Algorithm
This invention is a fast primal-based column-and-constraint generation (C&CG) method designed to solve two-stage decision-making problems, which are common in many industries. Its significant advantage lies in its ability to drastically outperform previous algorithms, handling complex problems with decision-dependent uncertainty.
Description
This technology introduces a fast primal-based column-and-constraint generation (C&CG) algorithm to solve distributionally robust optimization (DRO) problems, which often arise in two-stage decision-making. A key innovation is its ability to handle decision-dependent uncertainty (DDU), where the sample spaces themselves change based on decisions. To address this, the innovators developed a novel parametric C&CG (P-C&CG) algorithm and modified it to incorporate specific structural properties. The technology also includes theoretical analyses on the algorithm's strength, convergence, and iteration complexity.Applications
- Power and energy industries: Optimizing power grid operations and resource allocation.- Logistics and supply chain management: Solving complex routing and transportation problems.
- Healthcare: Improving decision-making processes in medical and administrative operations.
- Optimization software companies: The algorithm could be incorporated into commercial solvers like Gurobi and IBM CPLEX.
- General-purpose optimization: Applicable to any two-stage decision-making problem across various industries.
Advantages
- Drastically improved performance: The new algorithm significantly outperforms the original C&CG algorithm.- Handles complex uncertainty: It can solve problems with decision-dependent uncertainty, a challenge that existing methods have not addressed effectively.
- Broad applicability: The algorithms are generally applicable to a wide range of two-stage decision-making problems.
- Strong theoretical foundation: The algorithm is supported by theoretical analyses of its strength, convergence, and complexity.
- Flexible solver compatibility: It can be used with any commercially available or open-source mixed integer programming solver.