The feature selection problem (FS) consists of determining a subset of features representing a dataset, that concentrate only the most relevant information the dataset contains. FS can be cast as a nonlinear, mixed-integer mathematical program with on-off constraints. Because of the presence of so-called big-M constraints, the continuous relaxation of FS is usually very weak, making the Branch & Bound process remarkably slow on real-world instances. In order to strengthen the model, we present new relaxations for FS that keep the integrality of a reasonably small subset of variables, and show an efficient algorithmical framework to separate a fractional incumbent from them. Preliminary results on small instances are presented to show the efficiency of the cutting planes generated.

In the directed circular facility layout problem (DCFLP) one has given a set of departments, their lengths and pairwise weights between the departments. In contrast to the single row facility layout problem (SRFLP), where departments are arranged along one side of a path without overlapping, the DCFLP looks for an arrangement on a circle such that the sum of the weighted center-to-center distances measured in clockwise direction is minimized.

In this talk, we present a new facility layout problem, the undirected circular facility layout problem (UDCFLP). For each pair of departments we consider here the shortest distance along the circle, either travelling in clockwise or in counter-clockwise direction.

We present two new mixed-integer linear programming models for the UDCFLP, whereby one model is an adaptation of a well-known model for the DCFLP and the other model is based on the well-known betweenness model for the SRFLP. We develop symmetry-breaking constraints and study the structure of the associated polytopes. Our models, which are strengthened by our new cutting planes, allow us to solve instances with up to 13 departments to optimality within a time limit of one hour. For larger instances we derive strong lower bounds exploiting the connections to some parallel machine scheduling problem.

Flow Decomposition is the problem of decomposing a flow network into a set of paths that can perfectly replicate it. As a minimization problem (Minimal Flow Decomposition—MFD), it consists of finding the smallest set of paths that justify such conditions. Such a problem is very common in Computer Science and Bioinformatics, where many of its variants are present in multi-assembly tools. This problem, even in its most primordial form, is an NP-hard problem, hindering larger-scale applications due to the lack of an efficient polynomial solver. In practical applications, several heuristics and approximations have been attempted, as well as different ILP formulations, all with different levels of success.

In simple terms, multiple genomic sequences are reconstructed from a set of reads, and a weighted graph (known as a splicing graph) is generated. Then, the multi-assembly can be described as the problem where a set of weighted paths, each path equivalent to a genomic sequence in a sequencing sample, whose superposition perfectly explains the weight of the graph. Because such graphs are obtained from real data, their weights do not always form a flow.

In this work, we provide an ILP formulation for IMFD (Irregular Minimum Flow Decomposition). In this problem, we assume that each edge has, besides its weight, a confidence rate relative to its presence in the splicing graph, such that a higher confidence rate means that such an edge is more likely to have been correctly predicted as part of such a graph. Our goal is to provide an efficient flow decomposition method that can simultaneously obtain the minimal set of paths with their respective weights and the highest combined confidence rate among selected edges. In this way, the decomposition is minimal and most accurate based on the initial conditions.

Our approach has shown potential for solving instances with up to 200 nodes within 30 seconds on real flow and simulated data. We also show that our ILP formulation is flexible and adaptable enough to incorporate many practical variants (such as subpath constraints). We hope our results can contribute to better methods to mitigate the complexity of the multi-assembly problem and improve the efficiency of future practical tools.

In this article, we address the open pit mine production scheduling problem (OPMPSP) by considering the discretized ore body representation known as the block model. The objective is to strategically determine the block sequence, extraction timing, quantity, and processing decisions over a predefined planning horizon while adhering to the operational constraints and maximizing the net present value of the profit. We explore OPMPSP, accounting for capacity, blending, production, and material flow constraints. It is generally modeled with mixed-integer linear programming, but the sheer volume of blocks, and complexity results in high computation time for large instances. Hence, this article proposes incorporating new cutting planes into the model to strengthen the formulation through the addition of user-defined cuts developed through a combination of production capacity constraints and precedence relationships amongst the blocks. The inclusion of these cuts substantially reduces the computational demands for achieving the optimal integer solution resulting in lower computation time. The effectiveness of the developed new cuts is evaluated over real mine problem datasets. These computational results are compared with cuts present in the existing academic literature for comparative analysis. The combination of cuts is later integrated into the model supplemented with a sliding window heuristic to assess the overall impact. Thus the article contributes valuable insights and practical approaches to address the complexities inherent in large-scale open-pit mining production scheduling problems.