Pascal Van Hentenryck

Pascal Van Hentenryck is Professor in the Department of Computer Science at Brown University. He is the author or editor of several MIT Press books.

  • Online Stochastic Combinatorial Optimization

    Online Stochastic Combinatorial Optimization

    Russell Bent and Pascal Van Hentenryck

    A framework for online decision making under uncertainty and time constraints, with online stochastic algorithms for implementing the framework, performance guarantees, and demonstrations of a variety of applications.

    Online decision making under uncertainty and time constraints represents one of the most challenging problems for robust intelligent agents. In an increasingly dynamic, interconnected, and real-time world, intelligent systems must adapt dynamically to uncertainties, update existing plans to accommodate new requests and events, and produce high-quality decisions under severe time constraints. Such online decision-making applications are becoming increasingly common: ambulance dispatching and emergency city-evacuation routing, for example, are inherently online decision-making problems; other applications include packet scheduling for Internet communications and reservation systems. This book presents a novel framework, online stochastic optimization, to address this challenge. This framework assumes that the distribution of future requests, or an approximation thereof, is available for sampling, as is the case in many applications that make either historical data or predictive models available. It assumes additionally that the distribution of future requests is independent of current decisions, which is also the case in a variety of applications and holds significant computational advantages. The book presents several online stochastic algorithms implementing the framework, provides performance guarantees, and demonstrates a variety of applications. It discusses how to relax some of the assumptions in using historical sampling and machine learning and analyzes different underlying algorithmic problems. And finally, the book discusses the framework's possible limitations and suggests directions for future research.

    • Hardcover $35.00
    • Paperback $25.00
  • Constraint-Based Local Search

    Constraint-Based Local Search

    Laurent Michel and Pascal Van Hentenryck

    Introducing a method for solving combinatorial optimization problems that combines the techniques of constraint programming and local search.

    The ubiquity of combinatorial optimization problems in our society is illustrated by the novel application areas for optimization technology, which range from supply chain management to sports tournament scheduling. Over the last two decades, constraint programming has emerged as a fundamental methodology to solve a variety of combinatorial problems, and rich constraint programming languages have been developed for expressing and combining constraints and specifying search procedures at a high level of abstraction. Local search approaches to combinatorial optimization are able to isolate optimal or near-optimal solutions within reasonable time constraints.

    This book introduces a method for solving combinatorial optimization problems that combines constraint programming and local search, using constraints to describe and control local search, and a programming language, COMET, that supports both modeling and search abstractions in the spirit of constraint programming.

    After an overview of local search including neighborhoods, heuristics, and metaheuristics, the book presents the architecture and modeling and search components of constraint-based local search and describes how constraint-based local search is supported in COMET. The book describes a variety of applications, arranged by meta-heuristics. It presents scheduling applications, along with the background necessary to understand these challenging problems. The book also includes a number of satisfiability problems, illustrating the ability of constraint-based local search approaches to cope with both satisfiability and optimization problems in a uniform fashion.

    • Hardcover $42.00
    • Paperback $22.00
  • Numerica


    A Modeling Language for Global Optimization

    Pascal Van Hentenryck, Laurent Michel, and Yves Deville

    Many science and engineering applications require the user to find solutions to systems of nonlinear constraints or to optimize a nonlinear function subject to nonlinear constraints. The field of global optimization is the study of methods to find all solutions to systems of nonlinear constraints and all global optima to optimization problems. Numerica is modeling language for global optimization that makes it possible to state nonlinear problems in a form close to the statements traditionally found in textbooks and scientific papers. The constraint-solving algorithm of Numerica is based on a combination of traditional numerical methods such as interval and local methods, and constraint satisfaction techniques. This comprehensive presentation of Numerica describes its design, functions, and implementation. It also discusses how to use Numerica effectively to solve practical problems and reports a number of experimental results. A commercial implementation of Numerica is available from ILOG under the name ILOG Numerica.

    • Paperback $30.00
  • Principles and Practice of Constraint Programming

    Principles and Practice of Constraint Programming

    Vijay A. Saraswat and Pascal Van Hentenryck

    This collection of twenty-three original papers represents the first effort to bring together the work of constraint programming researchers scattered across multiple disciplines and across the world.

    This collection of twenty-three original papers represents the first effort to bring together the work of constraint programming researchers scattered across multiple disciplines and across the world. The collection contributes to the understanding of the common principles of this emerging general paradigm, the investigation of its theoretical foundations as well as applications to real-world computing problems. It is organized around themes of concurrency and reactive systems, languages and environments, algorithms, computer graphics, and artificial intelligence.

    Constraint programming aims at supporting a wide range of complex applications which are often modeled naturally in terms of constraints. Early work, in the 1960s and 1970s, made use of constraints in computer graphics, user interfaces, and artificial intelligence. Such work introduced a declarative component in otherwise-procedural systems to reduce the development effort. The mid-1980s have witnessed the emergence of general-purpose programming languages based on constraints, such as constraint logic programming and concurrent constraint programming, with significant applications in academia and industry. Today, an increasing number of researchers from all over the map of computing are looking at different aspects of this new computational paradigm.

    • Hardcover $75.00
    • Paperback $40.00
  • Constraint Satisfaction in Logic Programming

    Pascal Van Hentenryck

    This book tackles classic problems from operations research and circuit design using a logic programming language embedding consistency techniques, a paradigm emerging from artificial intelligence research. Van Hentenryck proposes a new approach to solving discrete combinatorial problems using these techniques. Logic programming serves as a convenient language for stating combinatorial problems, but its "generate and test" paradigm leads to inefficient programs. Van Hentenryck's approach preserves one of the most useful features of logic programming - the duality of its semantics - yet allows a short development time for the programs while preserving most of the efficiency of special purpose programs written in a procedural language. Embedding consistency techniques in logic programming allows for ease and flexibility of programming and short development time because constraint propagation and tree-search programming are abstracted away from the user. It also enables logic programs to be executed efficiently as consistency techniques permit an active use of constraints to remove combinations of values that cannot appear in a solution Van Hentenryck presents a comprehensive overview of this new approach from its theoretical foundations to its design and implementation, including applications to real life combinatorial problems.The ideas introduced in Constraint Satisfaction in Logic Programming have been used successfully to solve more than a dozen practical problems in operations research and circuit design, including disjunctive scheduling, warehouse location, cutting stock car sequencing, and microcode labeling problems.

    Pascal Van Hentenryck is a member of the research staff at the European Computer Industry Research Centre. Constraint Satisfaction in Logic Programming is based on research for the Centre's CHIP project. As an outgrowth of this project, a new language (CHIP) that will include consistency techniques has been developed for commercial use. The book is included in the Logic Programming series edited by Ehud Shapiro.

    • Hardcover $40.00