Opportunity
Engineering Design Optimization Problems (EDOPs) are crucial in fields like engineering design and resource management, often formulated as polynomial optimization problems with integer variables. The widespread availability of multi-core processors has spurred the development of parallel solvers for these problems. However, existing parallel approaches, such as the branch-cut method and the enumeration method, face significant limitations that hinder their efficiency and effectiveness. The branch-cut method struggles with systematic program partitioning due to its random node generation process, leading to difficulties in controlling the number of subproblems and necessitating extensive inter-processor communication and waiting times, which consume most of the computational effort. Furthermore, it cannot guarantee that the obtained solution is globally optimal. Conversely, while the enumeration method can partition the main program, it results in subprograms containing a large number of overlapping product values. This overlap introduces unnecessary continuous variables and constraints when linearizing the polynomial terms, creating a heavy computational burden and degrading performance. These deficiencies highlight the need for a parallel solver that can efficiently partition EDOPs into truly independent subprograms with minimal value overlap, enabling simultaneous, communication-free processing and guaranteeing the identification of the global optimal solution.
Technology
This patent introduces "PARA235," a prime-number-based parallel solver designed to overcome the shortcomings of existing methods. The core innovation lies in its systematic partitioning mechanism based on the prime factorization of integer variables. The method begins by identifying the set of prime numbers that are the maximum prime factors for all possible values of each integer variable in the EDOP. These primes are then used to cluster the variable values. For a given number N of available processors, the main EDOP program is partitioned into N independent subprograms. Each subprogram is assigned a unique combination of these prime-based clusters for each variable, ensuring that the product value sets (e.g., for terms like x_i x_j) across different subprograms have minimal overlap. This is achieved because products formed from numbers with different maximum prime factors naturally fall into distinct sets. The partitioned subprograms are then solved simultaneously and independently by the N parallel processors without any inter-processor communication or central coordination during the computation phase. Each subprogram is reformulated as a linear mixed-integer program using a novel linearization technique that leverages the prime-based clustering to introduce fewer continuous variables and constraints compared to the enumeration method. After all processors complete their tasks, a central processor automatically selects the best solution from among the N unique results, which is guaranteed to be the global optimal solution for the original EDOP.
Advantages
- Enables systematic and efficient partitioning of the main EDOP into a predetermined number (N) of independent subprograms based on available processors.
- Significantly reduces overlapping product values among subprograms compared to the enumeration method, leading to more compact linearized formulations.
- Eliminates inter-processor communication and waiting time during the solution phase, a major bottleneck in branch-cut methods.
- Guarantees that the best solution found among the subprograms is the global optimal solution for the original EDOP.
- Achieves substantial speedup in solving EDOPs, as demonstrated in test cases (e.g., up to 27x faster than the enumeration method).
- Provides a deterministic partitioning strategy versus the non-deterministic branching in branch-cut methods.
- Applicable to polynomial terms of various orders (e.g., two-variable, three-variable, and higher-order cross terms).
Applications
- Structural engineering design optimization (e.g., truss design, pressure vessel design).
- Mechanical engineering component and system optimization.
- Reliability engineering and system redundancy design.
- Resource allocation and management problems formulated with integer variables.
- Any field requiring the solution of polynomial integer optimization problems on parallel computing architectures.
