Abstract In the last decade, numerous algorithms for single-objective Boolean optimization have been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers in Multi-Objective Combinatorial Optimization (MOCO) algorithms is scarce. Due to the shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are cast as single-objective, using either a linear combination or by setting a preference order among the objectives. In this paper, we extend the state of the art of MOCO solvers with three novel unsatisfiability-based algorithms. The first two are core-guided MOCO solvers. The third is a hitting set MOCO solver. Experimental results in several sets of benchmark instances show that our new unsatisfiability-based algorithms can outperform and complement other SAT-based, state-of-the-art algorithms for MOCO.

Automated Program Repair (APR) for introductory programming assignments (IPAs) is motivated by the large number of student enrollments in programming courses each year. Since providing feedback on programming assignments requires substantial time and effort from faculty, personalized automated feedback often involves suggesting repairs to students' programs. Symbolic semantic repair approaches, which rely on Formal Methods (FM), check a program's execution against a test suite or reference solution, are effective but limited. These tools excel at identifying buggy parts but can only fix programs if the correct implementation and the faulty one share the same control flow graph. Conversely, Large Language Models (LLMs) are used for program repair but often make extensive rewrites instead of minimal adjustments. This tends to lead to more invasive fixes, making it harder for students to learn from their mistakes. In summary, LLMs excel at completing strings, while FM-based fault localization excel at identifying buggy parts of a program. In this paper, we propose a novel approach that combines the strengths of both FM-based fault localization and LLMs, via zero-shot learning, to enhance APR for IPAs. Our method uses MaxSAT-based fault localization to identify buggy parts of a program, then presents the LLM with a program sketch devoid of these buggy statements. This hybrid approach follows a Counterexample Guided Inductive Synthesis (CEGIS) loop to iteratively refine the program. We ask the LLM to synthesize the missing parts, which are then checked against a test suite. If the suggested program is incorrect, a counterexample from the test suite is fed back to the LLM for revised synthesis. Our experiments on 1,431 incorrect student programs show that our counterexample guided approach, using MaxSAT-based bug-free program sketches, significantly improves the repair capabilities of all six evaluated LLMs. This method allows LLMs to repair more programs and produce smaller fixes, outperforming other configurations and state-of-the-art symbolic program repair tools.

Logic programs are a powerful approach for solving NP-Hard problems. However, their declarative nature poses significant challenges in debugging. Unlike procedural paradigms, which allow for step-by-step inspection of program state, logic programs require reasoning about logical statements for fault localization. This complexity is especially significant in learning environments due to students' inexperience. We introduce FormHe, a novel tool that integrates logic-based techniques with Large Language Models (LLMs) to detect and correct issues in Answer Set Programming submissions. FormHe consists of two main components: a fault localization module and a program repair module. First, the fault localization module identifies specific faulty statements in need of modification. Next, FormHe applies program mutation techniques and leverages LLMs to repair the flawed code. The resulting repairs are then used to generate hints that guide students in correcting their programs. Our experiments with real buggy programs submitted by students show that FormHe accurately detects faults in 94% of cases and successfully repairs 58% of incorrect submissions.

Due to the vast number of students enrolled in programming courses , there has been an increasing number of automated program repair techniques focused on introductory programming assignments ( IPAs ). Typically, such techniques use program clustering to take advantage of previous correct student implementations to repair a new incorrect submission. These repair techniques use clustering methods since analyzing all available correct submissions to repair a program is not feasible. However, conventional clustering methods rely on program representations based on features such as abstract syntax trees ( ASTs ), syntax, control flow, and data flow. This paper proposes InvAASTCluster , a novel approach for program clustering that uses dynamically generated program invariants to cluster semantically equivalent IPAs . InvAASTCluster ’s program representation uses a combination of the program’s semantics, through its invariants, and its structure through its anonymized abstract syntax tree ( AASTs ). Invariants denote conditions that must remain true during program execution, while AASTs are ASTs devoid of variable and function names, retaining only their types. Our experiments show that the proposed program representation outperforms syntax-based representations when clustering a set of correct IPAs . Furthermore, we integrate InvAASTCluster into a state-of-the-art clustering-based program repair tool. Our results show that InvAASTCluster advances the current state-of-the-art when used by clustering-based repair tools by repairing around 13% more students’ programs, in a shorter amount of time.

Following the successful use of Propositional Satisfiability (SAT) algorithms in Boolean optimization (e.g., Maximum Satisfiability), several SAT-based algorithms have been proposed for Multi-Objective Combinatorial Optimization (MOCO). However, these new algorithms either provide a small subset of the Pareto front or follow a more exploratory search procedure and the solutions found are usually distant from the Pareto front. We extend the state of the art with a new SAT-based MOCO solver, Slide and Drill (Slide&Drill), that hones an upper bound set of the exact solution. Moreover, we show that Slide&Drill neatly complements proposed UNSAT-SAT algorithms for MOCO. These algorithms can work in tandem over the same shared "blackboard" formula, in order to enable a faster convergence. Experimental results in several sets of benchmark instances show that Slide&Drill can outperform other SAT-based algorithms for MOCO, in particular when paired with previously proposed UNSAT-SAT algorithms.

Abstract In recent years, more people have seen their work depend on data manipulation tasks. However, many of these users do not have the background in programming required to write complex programs, particularly SQL queries. One way of helping these users is automatically synthesizing the SQL query given a small set of examples. Several program synthesizers for SQL have been recently proposed, but they do not leverage multicore architectures. This paper proposes Cubes, a parallel program synthesizer for the domain of SQL queries using input-output examples. Since input-output examples are an under-specification of the desired SQL query, sometimes, the synthesized query does not match the user’s intent. Cubes incorporates a new disambiguation procedure based on fuzzing techniques that interacts with the user and increases the confidence that the returned query matches the user intent. We perform an extensive evaluation on around 4000 SQL queries from different domains. Experimental results show that our parallel approach can scale up to 16 processes with super-linear speedups for many hard instances, and that our disambiguation approach is critical to achieving an accuracy of around 60%, significantly larger than other SQL synthesizers.

Abstract Debugging is one of the most time-consuming and expensive tasks in software development. Several formula-based fault localization (FBFL) methods have been proposed, but they fail to guarantee a set of diagnoses across all failing tests or may produce redundant diagnoses that are not subset-minimal, particularly for programs with multiple faults. This paper introduces a novel fault localization approach for C programs with multiple faults. CFaults leverages Model-Based Diagnosis (MBD) with multiple observations and aggregates all failing test cases into a unified MaxSAT formula. Consequently, our method guarantees consistency across observations and simplifies the fault localization procedure. Experimental results on two benchmark sets of C programs, TCAS and C-Pack-IPAs, show that CFaults is faster than other FBFL approaches like BugAssist and SNIPER. Moreover, CFaults only generates subset-minimal diagnoses of faulty statements, whereas the other approaches tend to enumerate redundant diagnoses.

Low-code platforms enable rapid development of complex mission critical software applications. Nevertheless, these applications still must adhere to software principles. In particular, the developers need to create tests as part of their development cycle. However, this process involves significant effort from manual testing to manually coding tests. This process can be time-consuming and error-prone, especially for large and complex applications. In this paper, we propose using symbolic execution to generate tests for low-code applications. Symbolic execution is a technique that allows the exploration of all possible paths of a program, without requiring it to be executed with concrete values. Although symbolic execution has scalability issues due to path explosion, we mitigate the problem by exploring the properties of the low-code framework. We evaluate our approach using a set of real-world low-code applications and compare it to equivalent testing techniques for text-based programming languages. Our results show that symbolic execution can produce high quality results in a short amount of time when applied to visual programming languages. We believe that our approach has the potential to improve the quality and reliability of low-code applications while reducing the time and effort required for testing.

Abstract Individual and societal systems are open systems continuously affected by their situational context. In recent years, context sources have been increasingly considered in different domains to aid short and long-term forecasts of systems’ behavior. Nevertheless, available research generally disregards the role of prospective context, such as calendrical planning or weather forecasts. This work proposes a multiple-input neural architecture consisting of a sequential composition of long short-term memory units or temporal convolutional networks able to incorporate both historical and prospective sources of situational context to aid time series forecasting tasks. Considering urban case studies, we further assess the impact that different sources of external context have on medical emergency and mobility forecasts. Results show that the incorporation of external context variables, including calendrical and weather variables, can significantly reduce forecasting errors against state-of-the-art forecasters. In particular, the incorporation of prospective context, generally neglected in related work, mitigates error increases along the forecasting horizon.

To keep up with changes in requirements, frameworks, and coding practices, software organizations might need to migrate code from one language to another. Source-to-source migration, or transpilation, is often a complex, manual process. Transpilation requires expertise both in the source and target language, making it highly laborious and costly. Languages models for code generation and transpilation are becoming increasingly popular. However, despite capturing code-structure well, code generated by language models is often spurious and contains subtle problems. We propose BatFix , a novel approach that augments language models for transpilation by leveraging program repair and synthesis to fix the code generated by these models. BatFix takes as input both the original program, the target program generated by the machine translation model, and a set of test cases and outputs a repaired program that passes all test cases. Experimental results show that our approach is agnostic to language models and programming languages. BatFix can locate bugs spawning multiple lines and synthesize patches for syntax and semantic bugs for programs migrated from Java to C++ and Python to C++ from multiple language models, including, OpenAI’s Codex .

Automated program analysis is a pivotal research domain in many areas of Computer Science — Formal Methods and Artificial Intelligence, in particular. Due to the undecidability of the problem of program equivalence, comparing two programs is highly challenging. Typically, in order to compare two programs, a relation between both programs’ sets of variables is required. Thus, mapping variables between two programs is useful for a panoply of tasks such as program equivalence, program analysis, program repair, and clone detection. In this work, we propose using graph neural networks (GNNs) to map the set of variables between two programs based on both programs’ abstract syntax trees (ASTs). To demonstrate the strength of variable mappings, we present three use-cases of these mappings on the task of program repair to fix well-studied and recurrent bugs among novice programmers in introductory programming assignments (IPAs). Experimental results on a dataset of 4166 pairs of incorrect/correct programs show that our approach correctly maps 83% of the evaluation dataset. Moreover, our experiments show that the current state-of-the-art on program repair, greatly dependent on the programs’ structure, can only repair about 72% of the incorrect programs. In contrast, our approach, which is solely based on variable mappings, can repair around 88.5%.

Software developers often struggle to update APIs, leading to manual, time-consuming, and error-prone processes. We introduce Melt, a new approach that generates lightweight API migration rules directly from pull requests in popular library repositories. Our key insight is that pull requests merged into open-source libraries are a rich source of information sufficient to mine API migration rules. By leveraging code examples mined from the library source and automatically generated code examples based on the pull requests, we infer transformation rules in Comby, a language for structural code search and replace. Since inferred rules from single code examples may be too specific, we propose a generalization procedure to make the rules more applicable to client projects. Melt rules are syntax-driven, interpretable, and easily adaptable. Moreover, unlike previous work, our approach enables rule inference to seamlessly integrate into the library workflow, removing the need to wait for client code migrations. We evaluated Melt on pull requests from four popular libraries, successfully mining 461 migration rules from code examples in pull requests and 114 rules from auto-generated code examples. Our generalization procedure increases the number of matches for mined rules by 9×. We applied these rules to client projects and ran their tests, which led to an overall decrease in the number of warnings and fixing some test cases demonstrating MELT's effectiveness in real-world scenarios.

It has been shown that Maximum Satisfiability (MaxSAT) problem instances can be effectively solved by partitioning the set of soft clauses into several disjoint sets. The partitioning methods can be based on clause weights (e.g., stratification) or based on graph representations of the formula. Afterwards, a merge procedure is applied to guarantee that an optimal solution is found. This paper proposes a new framework called UpMax that decouples the partitioning procedure from the MaxSAT solving algorithms. As a result, new partitioning procedures can be defined independently of the MaxSAT algorithm to be used. Moreover, this decoupling also allows users that build new MaxSAT formulas to propose partition schemes based on knowledge of the problem to be solved. We illustrate this approach using several problems and show that partitioning has a large impact on the performance of unsatisfiability-based MaxSAT algorithms.

Abstract In the last decade, numerous algorithms for single-objective Boolean optimization have been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers in Multi-Objective Combinatorial Optimization (MOCO) algorithms is still scarce. Due to this shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are simplified to single-objective, using either a linear combination or a lexicographic ordering of the objective functions to optimize. In this paper, we extend the state of the art of MOCO solvers with two novel unsatisfiability-based algorithms. The first is a core-guided MOCO solver. The second is a hitting set-based MOCO solver. Experimental results in several sets of benchmark instances show that our new unsatisfiability-based algorithms can outperform state-of-the-art SAT-based algorithms for MOCO.

There has been a growing interest, over the last few years, in the topic of automated program repair applied to fixing introductory programming assignments (IPAs). However, the datasets of IPAs publicly available tend to be small and with no valuable annotations about the defects of each program. Small datasets are not very useful for program repair tools that rely on machine learning models. Furthermore, a large diversity of correct implementations allows computing a smaller set of repairs to fix a given incorrect program rather than always using the same set of correct implementations for a given IPA. For these reasons, there has been an increasing demand for the task of augmenting IPAs benchmarks.

Based on environmental and species monitoring data, Species Distribution Modelling (SDM) tries to build a model to predict the distribution of a species across a geographic area. These models can then be used to manage the activities in the area in order to prevent negative economic and environmental impacts. In marine ecosystems, SDM can be used to regulate fishing practices or manage protected areas. This paper presents DeepData, a new no-code web-based machine learning platform to facilitate the work of marine biologists with SDM. The DeepData tool enables to automate SDM, by automating the creation and validation of the model by marine biologists. Biologists mostly use probabilistic algorithms, such as maximum entropy, generalized linear models and generalized additive models. The DeepData tool also allows the use of machine learning algorithms, such as classification and regression trees, random forests and support vector machines. Moreover, besides the usage of machine learning algorithms, other steps in SDM, such as data preparation and model evaluation, are also discussed in the paper. Furthermore, a concrete explanation of the use of the DeepData tool is presented, as well as the details of implementation and evaluation.

The paper introduces the Seesaw algorithm, which explores the Pareto frontier of two given functions. The algorithm is complete and generalizes the well-known implicit hitting set paradigm. The first given function determines a cost of a hitting set and is optimized by an exact solver. The second, called the oracle function, is treated as a black-box. This approach is particularly useful in the optimization of functions that are impossible to encode into an exact solver. We show the effectiveness of the algorithm in the context of static solver portfolio selection. The existing implicit hitting set paradigm is applied to cost function and an oracle predicate. Hence, the Seesaw algorithm generalizes this by enabling the oracle to be a function. The paper identifies two independent preconditions that guarantee the correctness of the algorithm. This opens a number of avenues for future research into the possible instantiations of the algorithm, depending on the cost and oracle functions used.

With the growth of the open-source data science community, both the number of data science libraries and the number of versions for the same library are increasing rapidly. To match the evolving APIs from those libraries, open-source organizations often have to exert manual effort to refactor the APIs used in the code base. Moreover, due to the abundance of similar open-source libraries, data scientists working on a certain application may have an abundance of libraries to choose, maintain and migrate between. The manual refactoring between APIs is a tedious and error-prone task. Although recent research efforts were made on performing automatic API refactoring between different languages, previous work relies on statistical learning with collected pairwise training data for the API matching and migration. Using large statistical data for refactoring is not ideal because such training data will not be available for a new library or a new version of the same library. We introduce Synthesis for Open-Source API Refactoring (SOAR), a novel technique that requires no training data to achieve API migration and refactoring. SOAR relies only on the documentation that is readily available at the release of the library to learn API representations and mapping between libraries. Using program synthesis, SOAR automatically computes the correct configuration of arguments to the APIs and any glue code required to invoke those APIs. SOAR also uses the interpreter's error messages when running refactored code to generate logical constraints that can be used to prune the search space. Our empirical evaluation shows that SOAR can successfully refactor 80% of our benchmarks corresponding to deep learning models with up to 44 layers with an average run time of 97.23 seconds, and 90% of the data wrangling benchmarks with an average run time of 17.31 seconds.

Time series anomaly detection is an active research area, combining dozens of state-of-the-art methods that place heterogeneous views on what is an anomaly.This diversity of views -local and global, point and segment, univariate and multivariate, context-free and context-aware anomalies -is associated with moderate-to-high output divergences between methods.As a result, the user is faced with the difficult and laborious task of selecting the most appropriate methods and identifying cross-method consensus in an attempt to optimize recall and precision.Despite the relevance of establishing agreement criteria, existing principles are scarce and suffer from major problems: 1) show biases towards methods with correlated/redundant anomaly profiles; 2) depend on anomaly score thresholding; 3) prevent online detection; and 4) offer consensus not subjected to sound statistical testing.This work proposes UNIANO (UNIfied ANOmaly), an approach that combines simple yet effective empirical multivariate distribution statistics to address these drawbacks, guaranteeing a parameter-free and statistically robust integration of heterogeneous anomaly views.In this context, anomalies detected by less prevalent and concordant anomaly profiles, such as context-aware profiles in the presence of complementary variables, are not undervalued.Given a n-length time series and m views, UNIANO is aided by adequate data structures to achieve O(n log m 2 n) training time and linear O(m) testing-and-updating time.The gathered results confirm the relevance of the proposed approach.

Alloy is a declarative modeling language based on a first-order relational logic. Its constraint-based analysis has enabled a wide range of applications in software engineering, including configuration synthesis, bug finding, test-case generation, and security analysis. Certain types of analysis tasks in these domains involve finding an optimal solution. For example, in a network configuration problem, instead of finding any valid configuration, it may be desirable to find one that is most permissive (i.e., it permits a maximum number of packets). Due to its dependence on SAT, however, Alloy cannot be used to specify and analyze these types of problems.

Charts are commonly used for data visualization. Generating a chart usually involves performing data transformations, including data pre-processing and aggregation. These tasks can be cumbersome and time-consuming, even for experienced data scientists. Reproducing existing charts can also be a challenging task when information about data transformations is no longer available.

Nowadays, many data analysts are domain experts, but they lack programming skills. As a result, many of them can provide examples of data transformations but are unable to produce the desired query. Hence, there is an increasing need for systems capable of solving the problem of Query Reverse Engineering (QRE). Given a database and output table, these systems have to find the query that generated this table. We present SQUARES, a program synthesis tool based on input-output examples that can help data analysts to extract and transform data by synthesizing SQL queries, and table manipulation programs using the R language.

Current Maximum Satisfiability (MaxSAT) algorithms based on successive calls to a powerful Satisfiability (SAT) solver are now able to solve real-world instances in many application domains. Moreover, replacing the SAT solver with a Satisfiability Modulo Theories (SMT) solver enables effective MaxSMT algorithms. However, MaxSMT has seldom been used in debugging multi-threaded software.Multi-threaded programs are usually non-deterministic due to the huge number of possible thread operation schedules, which makes them much harder to debug than sequential programs. A recent approach to isolate the root cause of concurrency bugs in multi-threaded software is to produce a report that shows the differences between a failing and a non-failing execution. However, since they rely solely on heuristics, these reports can be unnecessarily large. Hence, reports may contain operations that are not relevant to the bug’s occurrence.This paper proposes the use of MaxSMT for the generation of minimal reports for multi-threaded software with concurrency bugs. The proposed techniques report situations that the existing techniques are not able to identify. Experimental results show that using MaxSMT can significantly improve the accuracy of the generated reports and, consequently, their usefulness in debugging the root cause of concurrency bugs.

Constraint-based reasoning methods thrive in solving problem instances with a tight solution space. On the other hand, evolutionary algorithms are usually effective when it is not hard to satisfy the problem constraints. This dichotomy has been observed in many optimization problems. In the particular case of Multi-Objective Combinatorial Optimization (MOCO), new recently proposed constraint-based algorithms have been shown to outperform more established evolutionary approaches when a given problem instance is hard to satisfy. In this paper, we propose the integration of constraint-based procedures in evolutionary algorithms for solving MOCO. First, a new core-based smart mutation operator is applied to individuals that do not satisfy all problem constraints. Additionally, a new smart improvement operator based on Minimal Correction Subsets is used to improve the quality of the population. Experimental results clearly show that the integration of these operators greatly improves multi-objective evolutionary algorithms MOEA/D and NSGAII. Moreover, even on problem instances with a tight solution space, the newly proposed algorithms outperform the state-of-the-art constraint-based approaches for MOCO.

Minimal Correction Subsets (MCSs) have been successfully applied to find approximate solutions to several real-world single-objective optimization problems. However, only recently have MCSs been used to solve Multi-Objective Combinatorial Optimization (MOCO) problems. In particular, it has been shown that all optimal solutions of MOCO problems with linear objective functions can be found by an MCS enumeration procedure. In this paper, we show that the approach of MCS enumeration can also be applied to MOCO problems where objective functions are divisions of linear expressions. Hence, it is not necessary to use a linear approximation of these objective functions. Additionally, we also propose the integration of diversification techniques on the MCS enumeration process in order to find better approximations of the Pareto front of MOCO problems. Finally, experimental results on the Virtual Machine Consolidation (VMC) problem show the effectiveness of the proposed techniques.

New constraint-based algorithms have been recently proposed to solve Multi-Objective Combinatorial Optimization (MOCO) problems. These new methods are based on Minimal Correction Subsets (MCSs) or P-minimal models and have shown to be successful at solving MOCO instances when the constraint set is hard to satisfy. However, if the constraints are easy to satisfy, constraint-based tools usually do not perform as well as stochastic methods. For solving such instances, algorithms should focus on dealing with the objective functions. This paper proposes the integration of stratification techniques in constraint-based algorithms for MOCO. Moreover, it also shows how to diversify the stratification among the several objective criteria in order to better approximate the Pareto front of MOCO problems. An extensive experimental evaluation on publicly available MOCO instances shows that the new algorithm is competitive with stochastic methods and it is much more effective than existing constraint-based methods.

A Minimal Correction Subset (MCS) of an unsatisfiable constraint set is a minimal subset of constraints that, if removed, makes the constraint set satisfiable. MCSs enjoy a wide range of applications, such as finding approximate solutions to constrained optimization problems. However, existing work on applying MCS enumeration to optimization problems focuses on the single-objective case. In this work, Pareto Minimal Correction Subsets (Pareto-MCSs) are proposed for approximating the Pareto-optimal solution set of multi-objective constrained optimization problems. We formalize and prove an equivalence relationship between Pareto-optimal solutions and Pareto-MCSs. Moreover, Pareto-MCSs and MCSs can be connected in such a way that existing state-of-the-art MCS enumeration algorithms can be used to enumerate Pareto-MCSs. Finally, experimental results on the multi-objective virtual machine consolidation problem show that the Pareto-MCS approach is competitive with state-of-the-art algorithms.

The most successful parallel SAT and MaxSAT solvers follow a portfolio approach, where each thread applies a different algorithm (or the same algorithm configured differently) to solve a given problem instance. The main goal of building a portfolio is to diversify the search process being carried out by each thread. As soon as one thread finishes, the instance can be deemed solved. In this paper we present a new open source distributed solver for MaxSAT solving that addresses two issues commonly found in multicore parallel solvers, namely memory contention and scalability. Preliminary results show that our nonportfolio distributed MaxSAT solver outperforms its sequential version and is able to solve more instances in several instance sets as the number of processes increases.

Linear search algorithms have been shown to be particularly effective for solving partial Maximum Satisfiability (MaxSAT) problem instances. These algorithms start by adding a new relaxation variable to each soft clause and solving the resulting formula with a SAT solver. Whenever a Model is found, a new constraint on the relaxation variables is added such that Models with a greater or equal value are excluded. However, if the problem instance has a large number of relaxation variables, then adding a new constraint over these variables can lead to the exploration of a much larger search space. This article proposes new algorithms to improve the performance of linear search algorithms for MaxSAT by using Models found by the SAT solver to partition the relaxation variables. These algorithms add a new constraint on a subset of relaxation variables, thus intensifying the search on that subspace. In addition, the proposed algorithms are further enhanced by using incremental approaches where learned clauses are kept between calls to the SAT solver. Experimental results show that Model-based algorithms can outperform a classic linear search algorithm in several problem instances. Moreover, incremental approaches further improve the performance of linear search and Model-based algorithms for MaxSAT. Overall, Model-based algorithms are competitive with state-of-the-art MaxSAT solvers, and can improve their performance when solving problem instances with a large number of soft clauses.

Maximum Satisfiability (MaxSAT) is a well-known optimization version of Propositional Satisfiability (SAT), that finds a wide range of relevant practical applications. Despite the significant progress made in MaxSAT solving in recent years, many practically relevant problem instances require prohibitively large run times, and many cannot simply be solved with existing algorithms. One approach for solving MaxSAT is based on iterative SAT solving, which may optionally be guided by unsatisfiable cores. A difficulty with this class of algorithms is the possibly large number of times a SAT solver is called, e.g. for instances with very large clause weights. This paper proposes the use of geometric progressions to tackle this issue, thus allowing, for the vast majority of problem instances, to reduce the number of calls to the SAT solver. The new approach is also shown to be applicable to core-guided MaxSAT algorithms. Experimental results, obtained on a large number of problem instances, show gains when compared to state-of-the-art implementations of MaxSAT algorithms.

Autarkies are partial truth assignments that satisfy all clauses having literals in the assigned variables. Autarkies provide important information in the analysis of unsatisfiable formulas. Indeed, clauses satisfied by autarkies cannot be included in minimal explanations or in minimal corrections of unsatisfiability. Computing the maximum autarky allows identifying all such clauses. In recent years, a number of alternative approaches have been proposed for computing a maximum autarky. This paper develops new models for representing autarkies, and proposes new algorithms for computing the maximum autarky. Experimental results, obtained on a large number of problem instances, show orders of magnitude performance improvements over existing approaches, and solving instances that could not otherwise be solved.

Cardinality constraints appear in many practical problems and have been well studied in the past. There are many CNF encodings for cardinality constraints, although it is not clear which encodings perform better. Indeed, different encodings can perform well over different problems. This paper examines a large number of cardinality encodings and evaluates their performance for solving the problem of Maximum Satisfiability (MaxSAT). Taking advantage of the diversification of cardinality encodings, we propose to exploit those encodings in parallel MaxSAT solving. Our parallel solver, pMAX, simultaneously searches in the lower and upper bound of the optimum value, and different cardinality encodings are used in each thread to increase the diversification of the search. Moreover, learned clauses are shared between threads during the search. Experimental results show that our parallel solver outperforms other sequential and parallel state-of-the-art MaxSAT solvers.

The last two decades progresses have led Propositional Satisfiability (SAT) to be a competitive practical approach to solve a wide range of industrial and academic problems. Thanks to these advances, the size and difficulty of the SAT instances have grown significantly. The demand for more computational power led to the creation of new computer architectures and paradigms composed by multiple machines connected by a network to act as one machine, like clusters and grids. However, extra computing power is not coming anymore from higher processor frequencies, but rather from a growing number of computing cores and processors. It becomes clear that exploiting this new architecture is essential for the evolution of SAT solvers. Search space splitting is probably the most commonly used strategy to explore the parallelism provided by the search space. However, it is not clear how to find the relevant set of variables to divide the search space. This paper extends a method based on the VSIDS heuristic to find the initial set of partition variables. A drawback of search space splitting is load balancing. To overcome this problem, we propose the use of a hybrid approach between search space splitting and portfolio. Preliminary results show that both these techniques improve the performance of the solver and reveal that combining search space splitting and portfolio approaches can lead to better results.

This paper presents a design for testability and minimum leakage pattern generation technique to reduce static power during test and burn-in for nanometer technologies. This technique transforms the minimum leakage pattern generation problem into a pseudo-Boolean optimization (PBO) problem. Nonlinear objective functions of leakage power are approximated by linear ones such that this problem can be solved efficiently by an existing PBO solver. A partitioning-based algorithm is applied for control point insertion and also CPU time reduction. Experimental results on the IEEE ISCAS'89 benchmark circuits using Taiwan Semiconductor Manufacturing Company 90-nm technology show that, for large circuits, the static power is reduced from 8.3% (without partition) to 17.47% (with 64 partitions). Besides, the overall CPU time is reduced from 3600 s (without partition) to 83 s (with 64 partitions). This technique reduces the static power without changing the manufacturing process or library cells.

Linear pseudo-Boolean optimization (PBO) is a widely used modeling framework in electronic design automation (EDA). Due to significant advances in Boolean satisfiability (SAT), new algorithms for PBO have emerged, which are effective on highly constrained instances. However, these algorithms fail to handle effectively the information provided by the cost function of PBO. This paper addresses the integration of lower bound estimation methods with SAT-related techniques in PBO solvers. Moreover, the paper shows that the utilization of lower bound estimates can dramatically improve the overall performance of PBO solvers for most existing benchmarks from EDA.

Cutting planes are a well-known, widely used, and very effective technique for integer linear programming (ILP). In contrast, the utilization of cutting planes in pseudo-Boolean Optimization (PBO) is recent and results still preliminary. This paper addresses the utilization of cutting planes, namely Gomory mixed-integer cuts, in satisfiability-based algorithms for PBO, and shows how these cuts can be used for computing lower bounds and for learning new constraints. A side result of learning new constraints is that the utilization of cutting planes enables non-chronological backtracking. Besides cutting planes, the paper also proposes the utilization of search restarts in PBO. We show that search restarts can be effective in practice, allowing the computation of more aggressive lower bounds each time the search restarts. Experimental results show that the integration of cutting planes and search restarts in a SAT-based algorithm for PBO yields a very efficient and robust new solution for PBO

Linear pseudoBoolean optimization (PBO) has found applications in several areas, ranging from artificial intelligence to electronic design automation. Due to important advances in Boolean satisfiability (SAT), new algorithms for PBO have emerged, which are effective on highly constrained instances. However, those algorithms fail in dealing properly with the objective function of PBO. We propose an algorithm that uses lower bound estimation methods for pruning the search tree in integration with techniques from SAT algorithms. Moreover, we show that the utilization of lower bound estimates can dramatically improve the overall performance of PBO solvers for specific classes of instances. In addition, we describe how to apply nonchronological backtracking in the presence of conflicts that result from the bounding process, using different lower bound estimation methods.

Covering problems are widely used as a modeling tool in electronic design automation. Recent years have seen dramatic improvements in algorithms for the unate/binate covering problem (UCP/BCP). Despite these improvements, BCP is a well-known computationally hard problem with many existing real-world instances that currently are hard or even impossible to solve. In this paper we apply search pruning techniques from the Boolean satisfiability domain to branch-and-bound algorithms for BCP. Furthermore, we generalize these techniques, in particular the ability to infer and record new constraints from conflicts and the ability to backtrack nonchronologically, to situations where the branch-and-bound BCP algorithm backtracks due to bounding conditions. Experimental results, obtained on representative real-world instances of the UCP/BCP, indicate that the proposed techniques are effective and can provide significant performance gains for specific classes of instances.

Covering problems are widely used as a modeling tool in Electronic Design Automation (EDA). Recent years have seen dramatic improvements in algorithms for the Unate/Binate Covering Problem (UCP/BCP). Despite these improvements, BCP is a well-known computationally hard problem, with many existing real-world instances that currently are hard or even impossible to solve. In this paper we apply search pruning techniques from the Boolean Satisfiability (SAT) domain to BCP. Furthermore, we generalize these techniques, in particular the ability to backtrack non-chronologically to exploit the actual formulation of covering problems. Experimental results, obtained on representative instances of the unate and binate covering problems, indicate that the proposed techniques provide significant performance gains for different classes of instances.

The computation of prime implicants has several and significant applications in different areas, including automated reasoning, non-monotonic reasoning, electronic design automation, among others. The authors describe a new model and algorithm for computing minimum-size prime implicants of propositional formulas. The proposed approach is based on creating an integer linear program (ILP) formulation for computing the minimum-size prime implicant, which simplifies existing formulations. In addition, they introduce two new algorithms for solving ILPs, both of which are built on top of an algorithm for propositional satisfiability (SAT). Given the organization of the proposed SAT algorithm, the resulting ILP procedures implement powerful search pruning techniques, including a non-chronological backtracking search strategy, clause recording procedures and identification of necessary assignments. Experimental results, obtained on several benchmark examples, indicate that the proposed model and algorithms are significantly more efficient than other existing solutions.