Abstract:
This is a joint Slovenian-Hungarian project where the work is clearly divided between both partners. The partners meet 2-3 times a year and work together remotely in the meantime.
In this project, we have developed new solution methods for multilinear optimization problems and apply them to solve some important real-life, industrial optimization problems, such as economic equilibrium problems (EEP), pooling problems (PP), and non-negative matrix factorization problems (NMFP). All of these optimization problems fall into the class of NP -complete problems, so algorithms with polynomial complexity are not expected unless P = NP holds.
We developed fast, albeit inexact, methods for large instances of the problems, combined with parallel implementations for efficient running on supercomputers. We used Matlab and C for the implementation.
Common features of these problems are that their nonconvexity arises from multiplying different decision variables. Similarly, the feasible solution sets of these optimization problems are nonconvex and even not connected. These are the causes of the major difficulties we have to overcome. To solve small instances of these problems, available general purpose nonlinear programming (NLP) solvers were used to perform reference (small scale) computations.
The methods we have implemented are hybrid computational methods (HCM). They combine exact algorithms (first- and second-order algorithms) with different types of local search techniques, meta-heuristics, and heuristics based on the structural properties of the problems. Parallelization of HCMs allowed us to test different combinations of algorithms and techniques using the supercomputer at the University of Ljubljana, Faculty of Mechanical Engineering.
The phases of the project and their realization:
The project was divided into 5 work packages with many tasks.
WP1: Project management: this was a set of activities to manage the project over the time and guaranty the results. It was coordinated operation of both parts of the project team and was aligned with both funding agencies.
WP2: The Problem of Economic Equilibrium (PER): This work package was led by the Hungarian part of the team. The work included:
- research on the the properties of different matrix classes, especially those that generate the so-called P matrices and sufficient matrices.
- development and implementation of new interior point methods (IPM) for linear complementarity problems and for problems of identifying sufficient matrices.
- application of global optimization methods for solving general linear complementarity problems (GLCP)
The most important results were published in
- SIAM journal on optimization: https://epubs.siam.org/doi/abs/10.1137/19M1248972
- CEJOR: https://link.springer.com/article/10.1007/s10100-021-00747-4
WP3: Blending and pooling problem and generalizations
ULFME was included in
- solving the blending problems
- introducing dual problems for bilinear optimization
As part of this work, we developed a generalized Petfod Welsh clustering algorithm that works as a dual graph coloring algorithm. The results were published in Computational and applied mathematics https://link.springer.com/article/10.1007/s40314-022-01835-0
WP4: Solving non-negative matrix factorization problems
This work package was led by the ULFS team: As part of this WP we did:
- we have developed new algorithms for solving the two-factor non-negative matrix factorization problem. The results are published in MDPI Mathematics https://www.mdpi.com/2227-7390/9/5/540
- we have developed new algorithms for solving the three-factor non-negative matrix factorization problem. The results are published in the Journal on Global Optimization at https://link.springer.com/article/10.1007/s10898-021-01074-3.
- we developed special algorithms for symmetric three-factor nnegative matrix factorization and used them in advanced cancer data analysis. Results published in Nature Communications: https://www.nature.com/articles/s41467-019-08797-8
WP5: Dissemination
In addition to published articles, we presented the results at various international conferences, such as ISMP, EURO, SOR, KOI, VOCAL
