Constraint Models for the Covering Test Problem

Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.     

Logic programs with stable model semantics as a constraint programming paradigm

Logic programming with the stable model semantics is put forward as a novel constraint programming paradigm. This paradigm is interesting because it bring advantages of logic programming based knowledge representation techniques to constraint programming and because implementation methods for the stable model semantics for ground (variable‐free) programs have advanced significantly in recent years. For a program with variables these methods need a grounding procedure for generating a variable‐free program. As a practical approach to handling the grounding problem a subclass of logic programs, domain restricted programs, is proposed. This subclass enables efficient grounding procedures and serves as a basis for integrating built‐in predicates and functions often needed in applications. It is shown that the novel paradigm embeds classical logical satisfiability and standard (finite domain) constraint satisfaction problems but seems to provide a more expressive framework from a knowledge representation point of view. The first steps towards a programming methodology for the new paradigm are taken by presenting solutions to standard constraint satisfaction problems, combinatorial graph problems and planning problems. An efficient implementation of the paradigm based on domain restricted programs has been developed. This is an extension of a previous implementation of the stable model semantics, the Smodels system, and is publicly available. It contains, e.g., built‐in integer arithmetic integrated to stable model computation. The implementation is described briefly and some test results illustrating the current level of performance are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Programming mechanical simulations

This paper examines the control of complex physical objects in simulation. We introduce a programming paradigm that allows a simulation to be treated as a multi-level constraint solver. The control programmer is given the ability to specify constraints on the controlled response of mechanisms and to conditionally change these constraints dependent on the state of system. The approach facilitates the development of model-based, event-driven control programs. The usefulness of the paradigm is demonstrated through the simulation of a hopping robot.     

A Hybrid Method for the Planning and Scheduling

We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.     

Constraints and AI planning

Tackling real-world planning problems often requires considering various types of constraints, which can range from simple numerical comparators to complex resources. This article provides an overview of techniques to deal with such constraints by expressing planning within general constraint-solving frameworks. Our goal here is to explore the interplay of constraints and planning, highlighting the differences between propositional satisfiability (SAT), integer programming (IP), and constraint programming (CP), and discuss their potential in expressing and solving AI planning problems.     

Symbolic constraints for meta-logic programming

Logic programming, with its declarative bias as well as unification and the direct representation of linguistic structures, is well qualified for meta-programming, i.e., programs working with representations of other programs as their data. However, constraint techniques seem necessary in order to fully exploit this paradigm. In the DEMOII system, the language of constraint handling rules (CHRs) has been used in order to provide a functionality that appears difficult to obtain without such means. For example, reversibility of a meta-interpreter, which can be obtained by means of constraints, turns it into a powerful program generator; in the same way, negation-as-failure implemented by means of constraints provides an incremental evaluation of integrity constraints. This paper focuses on the design of such constraints and their implementation by means of CHR.     

Array bounds check elimination in the context of deoptimization

Whenever an array element is accessed, Java virtual machines execute a compare instruction to ensure that the index value is within the valid bounds. This reduces the execution speed of Java programs. Array bounds check elimination identifies situations in which such checks are redundant and can be removed. We present an array bounds check elimination algorithm for the Java HotSpot? VM based on static analysis in the just-in-time compiler.The algorithm works on an intermediate representation in static single assignment form and maintains conditions for index expressions. It fully removes bounds checks if it can be proven that they never fail. Whenever possible, it moves bounds checks out of loops. The static number of checks remains the same, but a check inside a loop is likely to be executed more often. If such a check fails, the executing program falls back to interpreted mode, avoiding the problem that an exception is thrown at the wrong place.The evaluation shows a speedup near to the theoretical maximum for the scientific SciMark benchmark suite and also significant improvements for some Java Grande benchmarks. The algorithm slightly increases the execution speed for the SPECjvm98 benchmark suite. The evaluation of the DaCapo benchmarks shows that array bounds checks do not have a significant impact on the performance of object-oriented applications.     

An Analysis of Arithmetic Constraints on Integer Intervals

Arithmetic constraints on integer intervals are supported in many constraint programming systems. We study here a number of approaches to implement constraint propagation for these constraints. To describe them we introduce integer interval arithmetic. Each approach is explained using appropriate proof rules that reduce the variable domains. We compare these approaches using a set of benchmarks. For the most promising approach we provide results that characterize the effect of constraint propagation. The work of the second author was supported by NWO, The Netherlands Organization for Scientific Research, under project number 612.069.003.     

Dulmage-Mendelsohn Canonical Decomposition as a generic pruning technique

We introduce a new generic propagation mechanism for constraint programming. A first advantage of our pruning technique stems from the fact that it can be applied on various global constraints. In this work we describe a filtering scheme for such a family based on Dulmage-Mendelsohn Structure Theorem. Our method checks the feasibility in polynomial time and then ensures hyper-arc consistency in linear time. It is also applicable to any soft version of global constraint expressed in terms of a maximum matching in a bipartite graph and remains of linear complexity.     

Apla中泛型约束机制研究

泛型程序设计可大幅提高程序的可重用性、可靠性和开发效率.泛型约束机制是对泛型参数进行形式描述,并对其合法性进行检测及验证,从而保证泛型程序的可靠性和安全性.分析总结多种主流语言的泛型约束特性,存在难以描述及验证基于动态语义的复杂约束需求问题,与完整实现GP尚有距离;以抽象程序设计语言Apla为宿主语言,提出了基于代数结构及公理语义的泛型约束方法,给出了基本数据类型、自定义抽象数据类型和子程序的3类泛型约束机制,拓展了泛型程序设计约束的应用范围.同时,支持静态语法和动态语义层约束,提高了泛型约束的精确度;借助Isabelle定理证明器,设计了泛型约束匹配检测和验证算法;进一步设计了泛型约束机制在PAR平台的实现方案及其系统原型.实验部分给出了该泛型约束机制描述、检测及验证一系列复杂泛型约束问题的全过程,自动生成的C++模板程序的可靠性和安全性得到显著提高.     

Methods based on discrete optimization for finding road network rehabilitation strategies

We study a dynamic optimization problem arising in the (long-term) planning of road rehabilitation activities. In this area one seeks a pavement resurfacing plan for a road network under budget constraints. Our main approach is to model this as an integer programming problem with underlying dynamic programming structure. We investigate properties of this model and propose a solution method based on Lagrangian relaxation where one gets subproblems that are shortest path problems. Some computational experiences based on realistic data are reported.     

Array Management System (AMS)

The Array Management System (AMS) is an integrated set of array management tools designed to increase the productivity of technical programmers engaged in intensive matrix computational applications. These include analog circuit simulator, statistical analysis, dense or sparse equation solving, simulation, and in particular, the finite element program development. AMS is composed of a set of easy-to-use in-core and out-of-core data management subroutines written in FORTRAN 77. The in-core array management subroutines of AMS allow dynamic storage allocation to be accomplished with integer, real, and complex data with a minimum of programming effort. The out-of-core array management subroutines of AMS support simple operations to allow array transfer between in-core and out-of-core systems and allow different programs to access the same data. The out-of-core data management provides for a direct access database file to speed up the input/output operations. Multiple databases are allowed to be accessed by a program; this provides an easy way to share data and restart. This integrated database environment is suitable to be the kernel of a software project with several programmers and data communications among them.     

Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver

Piecewise polynomial constraint systems are common in numerous problems in computational geometry, such as constraint programming, modeling, and kinematics. We propose a framework that is capable of decomposing, and efficiently solving a wide variety of complex piecewise polynomial constraint systems, that include both zero constraints and inequality constraints, with zero-dimensional or univariate solution spaces. Our framework combines a subdivision-based polynomial solver with a decomposition algorithm in order to handle large and complex systems. We demonstrate the capabilities of our framework on several types of problems and show its performance improvement over a state-of-the-art solver.     

Compile-time analysis of nonlinear constraints in CLPR

Solving nonlinear constraints over real numbers is a complex problem. Hence constraint logic programming languages like CLPR or Prolog III solve only linear constraints and delay nonlinear constraints until they become linear. This efficient implementation method has the disadvantage that sometimes computed answers are unsatisfiable or infinite loops occur due to the unsatisfiability of delayed nonlinear constraint These problems could be solved by using a more powerful constraint solver which can deal with nonlinear constraints like in RISC-CLP(Real). Since such powerful constraint solvers are not very efficient, we propose a compromise between these two extremes. We characterize a class of CLPR programs for which all delayed nonlinear constraints become linear at run time. Programs belonging to this class can be safely executed with the efficient CLPR method while the remaining programs need a more powerful constraint solver. This paper is an extended and revised version of Ref. 12). The research described in this paper was made during the author’s stay at the Max-planck-Institut für Informatik in Saarbrücken, Germany. It was supported in part by the German Ministry for Research and Technology (BMFT) under grant ITS 9103 and by the ESPRIT Basic Research Working Group 6028 (Construction of Computational Logics). The responsibility for the contents of this publication lies with the author.     

Constraint-based deductive model checking

We show that constraint logic programming (CLP) can serve as a conceptual basis and as a practical implementation platform for the model checking of infinite-state systems. CLP programs are logical formulas (built up from constraints) that have both a logical interpretation and an operational semantics. Our contributions are: (1) a translation of concurrent systems (imperative programs) into CLP programs with the same operational semantics; and (2) a deductive method for verifying safety and liveness properties of the systems which is based on the logical interpretation of the CLP programs produced by the translation. We have implemented the method in a CLP system and verified well-known examples of infinite-state programs over integers, using linear constraints here as opposed to Presburger arithmetic as in previous solutions. Published online: 18 July 2001     

Interprocedural and Flow-Sensitive Type Analysis for Memory and Type Safety of C Code

The explicit memory management and type conversion endow the C language with flexibility and performance that render it the de facto language for system programming. However, these appealing features come at the cost of programs’ safety. Due to the C language permissiveness, highly skilled but inadvertent programmers often spawn insidious programming errors that yield exploitable code. In this paper, we present a novel type and effect analysis for detecting memory and type errors in C source code. We extend the standard C type system with effect, region, and host annotations that hold valuable safety information. We also define static safety checks to detect safety errors using the aforementioned annotations. Our analysis performs in an intraprocedural phase and an interprocedural phase. The flow-sensitive and alias-sensitive intraprocedural phase propagates type annotations and applies safety checks at each program point. The interprocedural phase generates and propagates unification constraints on type annotations across function boundaries. We present an inference algorithm that automatically infers type annotations and applies safety checks to programs without programmers’ interaction.     

Scalarization Using Loop Alignment and Loop Skewing

Array syntax, which is supported in many technical programming languages, adds expressive power by allowing operations on and assignments to whole arrays and array sections. To compile an array assignment statement to a uniprocessor, the language processor must convert the statement into a loop that has the same meaning. This process is called scalarization.Scalarization presents a significant technical problem because an array assignment needs to be implemented as if all inputs are fetched before any outputs are stored. Since a loop intermixes loads and stores, the compiler typically allocates a temporary array to hold the intermediate result. Because these extra temporary arrays can cause performance problems in cache, many techniques have been developed to avoid their use or minimize their size.In this paper, we present a novel application of two compiler strategies—loop alignment and loop skewing—to address this problem. We show that these strategies can achieve the asymptotically minimal memory allocation for stencil computations. Our experiments with loop alignment and loop skewing demonstrate that it is extremely effective in improving memory hierarchy performance of Fortran 90 array code on standard uniprocessors. The result should be applicable to other array languages, such as MATLAB.     

A set partitioning reformulation of a school bus scheduling problem

We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single-depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non-zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real-world instance are given and compared with results from a standard branch-and-cut approach.     

SkelCL: a high-level extension of OpenCL for multi-GPU systems

Application development for modern high-performance systems with graphics processing units (GPUs) currently relies on low-level programming approaches like CUDA and OpenCL, which leads to complex, lengthy and error-prone programs. We present SkelCL—a high-level programming approach for systems with multiple GPUs and its implementation as a library on top of OpenCL. SkelCL makes three main enhancements to the OpenCL standard: (1) memory management is simplified using parallel container data types (vectors and matrices); (2) an automatic data (re)distribution mechanism allows for implicit data movements between GPUs and ensures scalability when using multiple GPUs; (3) computations are conveniently expressed using parallel algorithmic patterns (skeletons). We demonstrate how SkelCL is used to implement parallel applications, and we report experimental evaluation of our approach in terms of programming effort and performance.