Using Statistical Measures and Machine Learning for Graph Reduction to Solve Maximum Weight Clique Problems.

Area of Science:

• Computational Mathematics
• Operations Research
• Artificial Intelligence

Background:

• Large-scale optimization problems present significant computational challenges.
• Existing methods often struggle with scalability due to problem complexity.
• Heuristic approaches are needed to reduce problem size effectively.

Purpose of the Study:

• To investigate problem reduction techniques for large-scale optimization.
• To develop and evaluate statistical and machine learning-based methods for variable selection.
• To enhance the performance of optimization algorithms through problem simplification.

Main Methods:

• Utilized stochastic sampling to generate feasible solutions and compute statistical measures.
• Developed a ranking-based measure focusing on variable frequency in high-quality solutions.
• Developed a correlation-based measure assessing variable-objective function relationships.
• Introduced Machine Learning for Problem Reduction (MLPR), a supervised learning model trained on known optimal solutions.
• Applied these techniques to the maximum weight clique problem for evaluation.

Main Results:

• Statistical measures (ranking and correlation) effectively identified relevant decision variables.
• The MLPR approach demonstrated superior prediction of variables belonging to optimal solutions.
• Problem reduction techniques significantly boosted the performance of existing solution methods.
• Effectiveness validated on the maximum weight clique problem.

Conclusions:

• Stochastic sampling and machine learning offer powerful tools for problem reduction in optimization.
• The MLPR framework provides an effective way to predict crucial decision variables.
• These techniques are highly effective in improving the efficiency of solving complex optimization problems.