Branch-and-bound methods for combinatorial optimization rely critically on the efficient computation of strong bounds during search. Decision diagram–based optimization provides such bounds via restricted and relaxed multi-valued decision diagrams (MDDs), but compiling relaxed diagrams can become a computational bottleneck for existing solvers. We present a GPU-accelerated implementation of decision diagram–based branch-and-bound using a decoupled architecture. It separates the compilation of relaxed and restricted diagrams and coordinates them through two queues of search states. This design enables heterogeneous parallelization: restricted diagrams are compiled concurrently on CPU threads while relaxed diagrams are constructed in parallel on a GPU. The GPU implementation exploits the layered structure of decision diagrams by expanding states in parallel and performing successor generation, dominance filtering, and state merging on the GPU. Computational experiments on knapsack, maximum independent set, and Golomb ruler benchmarks demonstrate substantial performance improvements over CPU-based decision diagram solvers, including speedups of up to an order of magnitude on hard instances and the ability to solve Golomb ruler instances up to size 16.

We show the security risk associated with using machine learning classifiers in United States election tabulators. The central classification task in election tabulation is deciding whether a mark does or does not appear on a bubble associated to an alternative in a contest on the ballot. Barretto et al. (E-Vote-ID 2021) reported that convolutional neural networks are a viable option in this field, as they outperform simple feature-based classifiers.

The Bin Packing Problem is one of the most important problems in discrete optimization, as it captures the requirements of many real-world problems. Because of its importance, it has been approached with the main theoretical and practical tools. Resolution approaches based on Linear Programming are the most effective, while Constraint Programming proves valuable when the Bin Packing Problem is a component of a larger problem. This work focuses on the Bin Packing constraint and explores how GPUs can be used to enhance its propagation algorithm. Two approaches are motivated and discussed, one based on knapsack reasoning and one using alternative lower bounds. The implementations are evaluated in comparison with state-of-the-art approaches on different benchmarks from the literature. The results indicate that the GPU-accelerated lower bounds offers a desirable alternative to tackle large instances.

We introduce CODD, a system for solving combinatorial optimization problems using decision diagram technology. Problems are represented as state-based dynamic programming models using the CODD language specification. The model specification is used to automatically compile relaxed and restricted decision diagrams that are embedded inside a branch-and-bound search process. We introduce abstractions that allow us to generically implement the solver components while maintaining overall execution efficiency. We demonstrate the functionality of CODD on a variety of combinatorial optimization problems and compare its performance to other state-based solvers as well as integer programming and constraint programming solvers. CODD provides competitive results and can outperform the other solvers, sometimes by orders of magnitude.

Abstract The AllDifferent constraint is a fundamental tool in Constraint Programming. It naturally arises in many problems, from puzzles to scheduling and routing applications. Such popularity has prompted an extensive literature on filtering and propagation for this constraint. This paper investigates the use of General Processing Units (GPUs) to accelerate filtering and propagation. In particular, the paper presents an efficient parallelization of the AllDifferent constraint on GPU, along with an analysis of different design and implementation choices and evaluation of the performance of the resulting system on several benchmarks.

Maintaining a resilient computer network is a delicate task with conflicting priorities. Flows should be served while controlling risk due to attackers. Upon publication of a vulnerability, administrators scramble to manually mitigate risk while waiting for a patch. We introduce$\textsc {Fashion}$: a linear optimizer that balances routing flows with the security risk posed by these flows.$\textsc {Fashion}$formalizes routing as a multi-commodity flow problem with side-constraints.$\textsc {Fashion}$formulates security using two approximations of risk in a probabilistic attack graph (Frigault et al. Network Security Metrics 2017).$\textsc {Fashion}$'s output is a set of software-defined networking rules consumable by Frenetic (Foster et al. ICFP 2011). We introduce a topology generation tool that creates data center network instances including flows and vulnerabilities.$\textsc {Fashion}$is executed on instances of up to 600 devices, thousands of flows, and million edge attack graphs. Solve time averages 30 minutes on the largest instances (seconds on the smallest instances). To ensure the security objective is accurate, the output solution is assessed using risk as defined by Frigault et al.$\textsc {Fashion}$allows enterprises to reconfigure their network in response to changes in functionality or security requirements.

We study the behavior of the A* search algorithm when coupled with a heuristic h satisfying (1-epsilon1)h*

The availability of commodity multicore and multiprocessor machines and the inherent parallelism in constraint programming search offer significant opportunities for constraint programming. These opportunities also present a fundamental challenge: how to exploit parallelism transparently to speed up constraint programs. This paper shows how to parallelize constraint programs transparently without changes to the sequential code. The main technical idea consists of automatically lifting a sequential exploration strategy into its parallel counterpart, allowing workers to share and steal subproblems. Experimental results show that the parallel implementation may produce significant speedups on multicore machines.

In recent years, two distinct electronic voting technologies have been introduced and extensively utilized in election procedures: direct recording electronic systems and optical scan (OS) systems. The latter are typically deemed safer, as they inherently provide a voter-verifiable paper trail that enables hand-counted audits and recounts that rely on direct voter input. For this reason, OS machines have been widely deployed in the United States. Despite the growing popularity of these machines, they are known to suffer from various security vulnerabilities that, if left unchecked, can compromise the integrity of elections in which the machines are used. This article studies general auditing procedures designed to enhance the integrity of elections conducted with optical scan equipment and, additionally, describes the specific auditing procedures currently in place in the State of Connecticut. We present an abstract view of a typical OS voting technology and its relationship to the general election process. With this in place, we lay down a ldquotemporal-resourcerdquo adversarial model, providing a simple language for describing the disruptive power of a potential adversary. Finally, we identify how audit procedures, injected at various critical stages before, during, and after an election, can frustrate such adversarial interference and so contribute to election integrity. We present the implementation of such auditing procedures for elections in the State of Connecticut utilizing the Premiere (Diebold) AccuVote OS; these audits were conducted by the UConn VoTeR Center, at the University of Connecticut, on request of the Office of the Secretary of the State. We discuss the effectiveness of such procedures in every stage of the process and we present results and observations gathered from the analysis of past election data.

Special purpose trusted computing devices are currently being deployed to offer many services for which the general purpose computing paradigm is unsuitable. The nature of the services offered by many of these devices demand high security and reliability, as well as low cost and low power consumption. Electronic Voting machines is a canonical example of this phenomenon. With electronic voting machines currently being used in much of the United States and several other countries, there is a strong need for thorough security evaluation of these devices and the procedures in place for their use. In this work, we first put forth a general framework for special purpose trusted computing devices. We then focus on Optical Scan (OS) electronic voting technology as a specific instance of this framework. OS terminals are a popular e-voting technology with the decided advantage of a user-verified paper trail: the ballot sheets themselves. Still election results are based on machine- generated totals as well as machine-generated audit reports to validate the voting process. In this paper we present a security assessment of the Diebold AccuVote Optical Scan voting terminal (AV-OS), a popular OS terminal currently in wide deployment anticipating the 2008 Presidential elections. The assessment is developed using exclusively reverse-engineering, without any technical specifications provided by the machine suppliers. We demonstrate a number of security issues that relate to the machine's proprietary language, called AccuBasic, that is used for reporting election results. While this language is thought to be benign, especially given that it is essentially sandboxed by the firmware to have only read access, we demonstrate that it is powerful enough to (i) strengthen known attacks against the AV-OS so that they become undetectable prior to elections (and thus significantly increasing their magnitude) or, (ii) to conditionally bias the election results to reach a desired outcome. Given the discovered vulnerabilities and attacks we proceed to discuss how random audits can be used to validate with high confidence that a procedure carried out by special purpose devices such as the AV-OS has not been manipulated. We end with a set of recommendations for the design and safe-use of OS voting systems.

Mathematical-modeling and constraint-programming languages have orthogonal strengths in stating combinatorial optimization problems. Modeling languages typically feature high-level set and algebraic notations, while constraint-programming languages provide a rich constraint language and the ability to specify search procedures. This paper shows that many of the functionalities typically found in modeling languages can be integrated elegantly in constraint-programming libraries without defining a specific language or preprocessor. In particular, it presents the design of Modeler, a C++ modeling layer for constraint programming which demonstrates how to enhance the expressiveness of constraint-programming libraries and to bridge much of the gap between libraries and modeling languages.

Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant improvements in efficiency over depth-first search for some classes of applications.This article reconsiders the implementation of discrepancy search, and of search strategies in general, for applications where the search procedure is dynamic, randomized, and/or generates global cuts (or nogoods) that apply to the remaining search. It illustrates that recomputation-based implementations of discrepancy search are not robust with respect to these extensions and require special care which may increase the memory requirements significantly and destroy the genericity of the implementation.To remedy these limitations, the article proposes a novel implementation scheme based on problem decomposition, which combines the efficiency of the recomputation-based implementations with the robustness of traditional iterative implementations. Experimental results on job-shop scheduling problems illustrate the potential of this new implementation scheme, which, surprisingly, may significantly outperform recomputation-based schemes.

Combinatorial optimization problems are ubiquitous in numerous practical applications. Yet most of them are challenging, both from computational complexity and programming standpoints. Local search is one of the main approaches to address these problems. However, it often requires sophisticated incremental algorithms and data structures, and considerable experimentation. This paper proposes a constraint-based, object-oriented, architecture to reduce the development time of local search algorithms significantly. The architecture consists of declarative and search components. The declarative component includes invariants, which maintain complex expressions incrementally, and differentiable objects, which maintain properties that can be queried to evaluate the effect of local moves. Differentiable objects are high-level modeling concepts, such as constraints and functions, that capture combinatorial substructures arising in many applications. The search component supports various abstractions to specify heuristics and meta-heuristics. We illustrate the architecture with the language Comet and several applications, such as car sequencing and the progressive party problem. The applications indicate that the architecture allows for very high-level modeling of local search algorithms, while preserving excellent performance.

Local search is a traditional technique to solve combinatorial search problems and has raised much interest in recent years. The design and implementation of local search algorithms is not an easy task in general and may require considerable experimentation and programming effort. However, contrary to global search, little support is available to assist the design and implementation of local search algorithms. This paper is an attempt to support the implementation of local search. It presents the preliminary design of LOCALIZER, a modeling language which makes it possible to express local search algorithms in a notation close to their informal descriptions in scientific papers. Experimental results on our first implementation show the feasibility of the approach.