Landscape optimization for NP-complete problems arising in applied domains

Given a set of constraints and criteria over a set of variables, a decision problem asks whether there exists a set of specific values for all variables which is able to satisfy both constraints and criteria. Classical problems of this category include for example the Subset-Sum problem (“given a set S of integer numbers and a target value, is there any subset of S whose element sum corresponds to the target?), which, in spite of its abstract nature, has several real-life applications [1].

Decision problems such as the Subset-Sum belong to the so-called NP-complete complexity class: problems in this class are considered to be computationally equivalent, meaning that any algorithm for any of the known NP-complete problems would imply the existence of an algorithm, exhibiting an equivalent complexity, for all other problems. However, since the NP-complete class is a subset of the NP-hard class, it is expected that no polynomial time complexity algorithms exist for such problems (unless P = NP, which is unlikely) [2]. As a consequence, many research efforts are devoted to the conception and development of heuristic approaches specifically designed for these problems.

In line with our ongoing CNRS IRP project [A] in collaboration with Taiwanese partners, the PhD candidate will study the relationships between classical decision problems and real-life applications, and mainly the applications arising in the context of structural biology. In spite of the large gap one may see between the formal definition of a problem such as the Subset-Sum and problems concerning biological molecules such as proteins, there actually exist several common points that allow for a deeper understanding of both domains, hence providing valuable insights into the design and the optimization of dedicated methods [3,4].

In line with our ongoing ANR project EVARISTE [B], the PhD candidate will work on novel heuristic approaches for the solution of the proposed decision problems. These heuristics are generally conceived for exploring tree-like search spaces, where the order of the explored variables (normally associated with the tree layers) is likely to have a strong impact on the overall tree structure [5]. Orders can in fact lead to the construction of search spaces having a more or less smooth landscape, implying, respectively, a larger or smaller time complexity for their exploration [6]. The study of alternative landscapes will be performed at different levels, on the basis of variable reordering techniques, as well as by exploring full or partial permutations on sets of variable values.

The PhD candidate is supposed to begin his/her work by performing a large literature review on the existing methods and algorithms for the above-mentioned problems, while keeping the focus on landscape optimization techniques. In order to drive the research activities toward a common direction of interest, the PhD works will be guided in cooperation with the partners of both EVARISTE and IRP projects. From one side, there will be an important guidance for what concerns the conception and development of new ad-hoc algorithms; from the other side, the collaboration with biologists and bio-physicists will ensure that the research will remain grounded in the realities of real-life applications, providing valuable feedback and guidance throughout the research process.

The PhD candidate will implement the newly designed algorithms in high and low-level programming languages, chosen on the basis of the particular needs (high-level for object/class design, low-level for efficiency, with the possibility of direct interoperability between the chosen languages). Since many algorithms in this domain require high computational resources, it is likely that the PhD candidate will also work on implementations specifically designed for parallel computing environments (general purpose GPU, as well as clusters of). As another alternative approach, in collaboration with our IRP’s Taiwanese partner, we can mention the possible use of quantum technologies, or of new technologies inspired by quantum mechanical processes, such as the novel GPU-based quantum-inspired annealing machine developed by Compal [C], a private company in Taiwan.