Abstract The Weighted Safe Set Problem requires to partition an undirected graph into two families of connected components, respectively denoted as safe and unsafe, in such a way that each safe component dominates the unsafe adjacent components with respect to a weight function. We introduce a combinatorial branch and bound approach, whose main strength is a refined relaxation that combines graph manipulations and the solution of an auxiliary problem. We also propose fixing procedures to reduce the number of branching nodes. The algorithm solves all weighted instances available in the literature and most unweighted ones, up to 50 vertices, with computational times orders of magnitude smaller than the competing algorithms. In order to investigate the limits of the approach, we introduce a benchmark of graphs with 60 vertices, solving to optimality the denser instances.

We study a prize-collecting single-machine scheduling problem with hard deadlines, where the objective is to minimize the difference between the total tardiness and the total prize of the selected jobs. This problem is motivated by industrial applications, both as a stand-alone model and as a pricing subproblem in column-generation algorithms for parallel machine scheduling problems. A preprocessing rule is devised to identify jobs that cannot belong to any optimal schedule. The resulting reduced problem is solved to optimality by a branch-and-bound algorithm and two integer linear programming formulations. The algorithm and the formulations are experimentally compared on randomly generated benchmark instances.

Over the last years, many smart buildings applications, such as indoor localization or safety systems, have been subject of intense research. Smart environments usually rely on several hardware nodes equipped with sensors, actuators, and communication functionalities. The high level of heterogeneity and the lack of standardization across technologies make design of such environments a very challenging task, as each installation has to be designed manually and performed ad-hoc for the specific building. On the other hand, many different systems show common characteristics, like the strict dependency with the building floor plan, also sharing similar requirements such as a nodes allocation that provides sensing coverage and nodes connectivity. This paper provides a computer-aided design application for the design of smart building systems based on the installation of hardware nodes across the indoor space. The tool provides a site-specific algorithm for cost-effective deployment of wireless localization systems, with the aim to maximize the localization accuracy. Experimental results from real-world environment show that the proposed site-specific model can improve the positioning accuracy of general models from the state-of-the-art. The tool, available open-source, is modular and extensible through plug-ins allowing to model building systems with different requirements.

Recent developments in Big Data frameworks are moving towards reservation based approaches as a mean to manage the increasingly complex mix of computations, whereas preemption techniques are employed to meet strict jobs deadlines. Within this work we propose and evaluate a new planning algorithm in the context of reservation based scheduling. Our approach is able to achieve high cluster utilization while minimizing the need for preemption that causes system overheads and planning mispredictions.

Most approaches for deadlock prevention and liveness enforcement in Petri nets rely on siphon control methods or the theory of regions to derive monitor-based supervisors. These techniques raise methodological and computational issues, from the existence of feasible solutions to the hardness of guaranteeing maximal permissivity and optimality in the size and cost of the control subnet. Recently, the supervisor design problem has also been reformulated as a direct monitor optimization task based on integer linear programming, which can more effectively deal with the mentioned issues and objectives. This paper introduces an efficient branch-and-bound scheme for the exploration of the solution space of the direct monitor optimization problem. An extensive computational analysis on a set of benchmark instances demonstrates the efficiency of the approach.

This paper proposes a new model for the partitioning and scheduling of a specification on partially dynamically reconfigurable hardware. Although this problem can be solved optimally only by tackling its subproblems jointly, the exceeding complexity of such a task leads to a decomposition into two phases. The partitioning phase is based on a new graph-theoretic approach, which aims to obtain near optimality even if performed independently from the subsequent phase. For the scheduling phase, a new integer linear programming formulation and a heuristic approach are developed. Both take into account configuration prefetching and module reuse. The experimental results show that the proposed method compares favorably with existing solutions.

In Petri-net (PN) modeling of flexible manufacturing systems, deadlock prevention is often addressed by means of siphon-control methods. Constraints that avoid the emptying of siphons can be easily implemented using additional places suitably connected to the PN transitions. Efficient siphon-based techniques achieve highly permissive solutions using as few control places as possible. One such technique employs a set-covering approach to optimally match emptiable siphons to critical markings. In this paper, a modified version of the method is proposed that achieves the same results in terms of permissivity and size of the control subnet but avoids full siphon enumeration. This greatly reduces the overall computational time and memory requirements and allows the applicability of the method to large-size models.

This paper introduces a new bounded multi-level algebraic form, called projected sum of products (P-SOP), based on projections of minimal SOP forms onto subsets of the Boolean space. After a standard two-level logic minimization, this technique can be used as a very fast postprocessing step for further minimizing the circuit area, increasing the depth of the network by only a constant value. The proposed synthesis algorithms have been implemented and tested with interesting results, which show how about 75% of standard Espresso benchmarks benefit from this postprocessing phase.

We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NP NP -hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis.

Deadlock prevention is a crucial step in the modeling of flexible manufacturing systems. In the Petri net framework, deadlock prevention policies based on siphon control are often employed, since it is easy to specify generalized mutual exclusion constraints that avoid the emptying of siphons. However, such policies may require an excessive computational load and result in impractical oversized control subnets. This is often a consequence of the redundancy in the control conditions derived from siphons. In this paper, a novel method is proposed that provides small size controllers, based on a set covering approach that conveniently relates siphons and markings. Some examples are provided to demonstrate the feasibility of the approach and to compare it with other methods proposed in the literature.

Multi-level logic synthesis yields much more compact expressions of a given Boolean function with respect to standard two-level sum of products (SOP) forms. On the other hand, minimizing an expression with more than two-levels can take a large time. In this paper we introduce a novel algebraic four-level expression, named k-EXOR-projected sum of products (kEP-SOP) form, whose synthesis can be performed in polynomial time with an approximation algorithm starting from a minimal SOP. Our experiments show that the resulting networks can be obtained in very short computational time and often exhibit a high quality. We also study the testability of these networks under the Stuck-at-fault model, and show how fully testable circuits can be generated from them by adding at most a constant number of multiplexer gates.

Recent research results have seen the application of parallelizing techniques to high-level synthesis. In particular, the effect of speculative code transformations on mixed control-data flow designs has demonstrated effective results on schedule lengths. In this paper we first analyze the use of the control and data dependence graph as an intermediate representation that provides the possibility of extracting the maximum parallelism. Then we analyze the scheduling problem by formulating an approach based on Integer Linear Programming (ILP) to minimize the number of control steps given the amount of resources. We improve the already proposed ILP scheduling approaches by introducing a new conditional resource sharing constraint which is then extended to the case of speculative computation. The ILP formulation has been solved by using a Branch and Cut framework which provides better results than standard branch and bound techniques.

In this paper, the authors introduce a new algebraic form for Boolean function representation, called EXOR-projected sum of products (EP-SOP), resulting in a four level network that can be easily implemented in practice. The authors prove that deriving an optimal EP-SOP from an optimal sum of products (SOP) form is a hard problem (NPNP-hard); nevertheless the authors propose a very efficient approximation algorithm, which returns in polynomial time an EP-SOP form whose cost is guaranteed to be near the optimum. Experimental evidence shows that for about 35% of the classical synthesis benchmarks the EP-SOP networks have a smaller area and delay with respect to the optimal SOPs (sometimes gaining even 40-50% of the area). Since the computational times required are extremely short, the authors recommend the use of the proposed approach as a postprocessing step after SOP minimization

The paper addresses the problem of enumerating minimal siphons in an ordinary Petri net. The algorithms developed in this work recursively use a problem partitioning procedure to reduce the original search problem to multiple simpler search subproblems. Each subproblem has specific additional place constraints with respect to the original problem. Some results on algorithm correctness, convergence, and computational complexity are provided, as well as an experimental evaluation of performance. The algorithms can be applied to enumerate minimal, place-minimal siphons, or even siphons that are minimal with respect to given subsets of places.

The paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, cost-related reductions of the problem, and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum and in most cases proves it to be such. On the problems whose optimum is actually unknown, the best known result is strongly improved.

The classical solving approach for two-level logic minimisation reduces the problem to a special case of unate covering and attacks the latter with a (possibly limited) branch-and-bound algorithm. We adopt this approach, but we propose a constructive heuristic algorithm that combines the use of Binary Decision Diagrams (BDDs) with the Lagrangian relaxation. This technique permits us to achieve an effective choice of the elements to include in the solution, as well as cost-related reductions of the problem and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum, and in most cases proves it to be so. On the problems whose optimum is actually unknown, the best known result is strongly improved.