Vladimir Voloshinov

This paper presents a method for adapting parallel versions of the SCIP global and discrete optimization solver to AMPL formats for input data (problem formulation) and output data (obtained solution). A workaround approach using a bash script wrapper was developed to integrate Fiber/ParaSCIP with the popular Pyomo package for solving mixed-integer nonlinear programming (MINLP) problems. The proposed solution provides a good balance between the complexity of implementation and the ease of use for users.

There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.

ParaSCIP is rather advanced open-source solver for discrete and global optimization problems. Thissolver is distinguished by that it can run on distributed memory systems and use up to 80,000 cores,solving open problems from the MIPLIB test libraries. Earlier, using this solver, we confirmed theconjecture on optimal packing of nine congruent circles on a square flat torus. The goal of the studywas to increase computing performance by utilizing resources of multiple clusters to solve hardoptimization problem. To do this, we use the previously developed DDBNB application, which allowsto speed up the solution of optimization problems by using coarse-grained parallelization based on astatic decomposition of feasible domain made before solving starts. DDBNB is an application for theEverest distributed computing platform which is responsible for running jobs on heterogeneouscomputing resources (servers, cloud instances, clusters, etc.). As a result, DDBNB, Everest, andParaSCIP had to be modified to make it possible to exchange incumbents (feasible solutions found bythe solver) between several ParaSCIP instances running on different supercomputers. The resultingsystem was benchmarked using three different instances of Traveling Salesman Problem. Thesupercomputers HPC5 of the NRC “Kurchatov Institute” and cHARISMa of the HSE University wereused as computing resources. As a result, for two problem instances, there is an effect, and thespeedup is especially noticeable for a more complex problem. However, for a simpler problem, theexchange of incumbents does not seem to affect the amount of speedup. For the third instance, there isno particular effect, at least no slowdown is observed.

The accuracy of approximate automodel solutions for the Green’s function of the Biberman-Holstein equation for the Stark broadening of spectral lines is analyzed using the distributed computing. The high accuracy of automodel solutions in a wide range of parameters of the problem is shown.

In computations related to mathematical programming problems, one often has to consider approximate, rather than exact, solutions satisfying the constraints of the problem and the optimality...