A multi-level approach to ubiquitous modeling and solving constraints in combinatorial optimization problems in production and distribution

Constraints, although ubiquitous in production and distribution planning, scheduling and control, often lead to inconsistencies in the decision-making process. The constraint-based modeling helps circumvent many organization-impacting issues. To address this, we developed a multi-level approach to the modeling and solving of combinatorial optimization problems. It is versatile and effective owing to the use of multi-level presolving and multiple paradigms, such as constraint programming, logic programming, mathematical programming and fuzzy logic, for their complementary strengths. The capability of this framework and its advantage over mathematical programming alone or over hybrid frameworks is shown in the illustrative example, in which combinatorial optimization is used as a benchmark to prove the effectiveness of the proposed approach. Knowledge of the problem is stored in the form of facts.     

A first exploration of PrologIII's capabilities

This paper explores PrologIII's capabilities through the study of two short but non-trivial applications that are chosen to show the advantages of constraint logic programming languages over conventional Prologs, especially for tackling combinatorial problems. The first application (manipulation of causal graphs) highlights the expressive power of the constraints on booleans and shows that constraint logic programming techniques provide great flexibility for the exploration of the domain of an application, and therefore significantly improve Prolog's prototyping capabilities. The second application (map colouring) demonstrates that a combined use of numerical constraints and constraints on trees of PrologIII enables one to improve solutions based on standard backtracking, through the use of simple heuristics. Such heuristics allow drastic reduction of the search space and yield good performance even for quite complex problems. The adaptability of the approach to other combinatorial problems is shown on several examples.     

Integrating constraint logic programming and operations research techniques for the Crew Rostering Problem

In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved by OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of logic programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated. © 1998 John Wiley & Sons, Ltd.     

Constraint Lingo: towards high‐level constraint programming

Logic programming requires that the programmer convert a problem into a set of constraints based on predicates. Choosing the predicates and introducing appropriate constraints can be intricate and error prone. If the problem domain is structured enough, we can let the programmer express the problem in terms of more abstract, higher‐level constraints. A compiler can then convert the higher‐level program into a logic‐programming formalism. The compiler writer can experiment with alternative low‐level representations of the higher‐level constraints in order to achieve a high‐quality translation. The programmer can then take advantage of both a reduction in complexity and an improvement in runtime speed for all problems within the domain. We apply this analysis to the domain of tabular constraint‐satisfaction problems. Examples of such problems include logic puzzles solvable on a hatch grid and combinatorial problems such as graph coloring and independent sets. The proper abstractions for these problems are rows, columns, entries, and their interactions. We present a higher‐level language, Constraint Lingo, dedicated to problems in this domain. We also describe how we translate programs from Constraint Lingo into lower‐level logic formalisms such as the logic of propositional schemata. These translations require that we choose among competing lower‐level representations in order to produce efficient results. The overall effectiveness of our approach depends on the appropriateness of Constraint Lingo, our ability to translate Constraint Lingo programs into high‐quality representations in logic formalisms, and the efficiency with which logic engines can compute answer sets. We comment on our computational experience with these tools in solving both graph problems and logic puzzles. Copyright © 2004 John Wiley & Sons, Ltd.     

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.     

一种可扩展型CLP系统的统一建模方法

约束推理是人工智能中主要组成部分之一,可以解决实际优化调度和规划过程中的约束求解问题。这里在解释了约束逻辑程序设计的原理和过程基础上,打破封闭式约束逻辑程序设计系统,从软件工程上采用统一建模语言,提出一种新的开放的可扩展型约束逻辑程序设计结构系统。为实现可扩展的约束推理搜索系统,引进UML建模语言中用例图、类图和协作图。在建模基础上详细说明了可扩展约束逻辑程序设计中数学模型,搜索引擎和搜索驱动三者间的关系以及它们内部的工作内容。最后在描述系统结构后,提出了可扩展的内容。根据扩展因素,外界为满足更多的需要可扩展本系统的约束过滤器。     

Modelling protein side-chain conformations using constraint logic programming.

Side-chain placement is an important sub-task in protein modelling. Selecting conformations for side-chains is a difficult problem because of the large search space to be explored. This problem can be addressed using constraint logic programming (CLP), which is an artificial intelligence technique developed to solve large combinatorial search problems. The side-chain placement problem can be expressed as a CLP program in which rotamer conformations are used as values for finite domain variables, and bad steric contacts involving rotamers are represented as constraints. This paper introduces the concept of null rotamers, and shows how these can be used in implementing a novel iterative approach. We present results that compare the accuracy of models constructed using different rotamer libraries and different domain variable enumeration heuristics. The results obtained using this CLP-based approach compare favourably with those obtained by other methods.     

Solving constraint optimization problems from CLP-stylespecifications using heuristic search techniques

Presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower-bound and upper-bound specifications with conventional logic programming languages, we augment a constraint logic programming (CLP) language with embedded constructs for specifying the cost function and with a few higher-order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP* and we show that CSLDNF (Constraint SLD resolution with Negation as Failure) resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP* can be converted into an implicit AND/OR graph, and present an algorithm called GenSolve which can branch-and-bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP* programs     

Binary partitioning, perceptual grouping, and restoration with semidefinite programming

We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds.     

Solving nesting problems with non-convex polygons by constraint logic programming

In this paper an application of constraint logic programming (CLP) to the resolution of nesting problems is presented. Nesting problems are a special case of the cutting and packing problems, in which the pieces generally have non‐convex shapes. Because of their combinatorial optimization nature, nesting problems have traditionally been tackled by heuristics and in the recent past by meta‐heuristics. When trying to formulate nesting problems as linear programming models, to achieve global optimal solutions, the difficulty of dealing with the disjunction of constraints arises. On the contrary, CLP deals easily with this type of relationships among constraints. A CLP implementation for the nesting problem is described for convex and non‐convex shapes. The concept of nofit polygon is used to deal with the geometric constraints inherent to all cutting and packing problems. Computational results are presented.     

On the performance of the LP-guided Hopfield network-genetic algorithm

This paper proposes a linear programming (LP)-guided Hopfield-genetic algorithm for a class of combinatorial optimization problems which admit a 0–1 integer linear programming. The algorithm modifies the updating order of the binary Hopfield network in order to obtain better performance of the complete hybrid approach. We theoretically analyze several different updating orders proposed. We also include in the paper a novel proposal to guide the Hopfield network using the crossover and mutation operators of the genetic algorithm. Experimental evidences that show the good performance of the proposed approach in two different combinatorial optimization problems are also included in the paper.     

约束逻辑程序设计的变量压缩事件分析

该文涉及的约束逻辑程序设计(CLP)是一在二叉树上进行搜索的过程,提高搜索效率是CLP的主要研究方向之一。在CLP中约束推理机是核心,由变量组、约束过滤器、临时容器、推理引擎组成。在介绍了约束推理机激活过滤器,对变量进行区间压缩后,提出引入变量事件,总结为三种类型:SINGLE、BOUND和DOMCHG,用于减少过滤器的激发次数。实验结果表明,变量事件能够促进约束推理机的搜索效率,缩短二叉树搜索的时间,可以更快寻找到答案。     

Logic modeling: A tool for management science

Developments in logic and in information technology (especially the advent of logic programming) have converged to the point at which logic is, for a broad variety of problems, a useful tool to employ for modeling in areas of interest to management scientists. This paper presents the concept of logic modeling (model building with symbolic logic) and reviews several lines of research having in common a logic modeling approach to problems of interest in management scientist.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

Application of 0-1 integer programming to multitarget tracking problems

This paper presents a new approach to the solution of multi-target tracking problems. 0-1 integer programming methods are used to alleviate the combinatorial computing difficulties that accompany any but the smallest of such problems. Multitarget tracking is approached as an unsupervised pattern recognition problem. A multiple-hypothesis test is performed to determine which particular combination of the many feasible tracks is most likely to represent actual targets. This multiple hypothesis test is shown to have the computational structure of the set packing and set partitioning problems of 0-1 integer programming. Multitarget tracking problems that are translated into this form can be rapidly solved, using well-known discrete optimization techniques such as implicit enumeration.     

Scaling Up Inductive Logic Programming: An Evolutionary Wrapper Approach

Inductive logic programming (ILP) algorithms are classification algorithms that construct classifiers represented as logic programs. ILP algorithms have a number of attractive features, notably the ability to make use of declarative background (user-supplied) knowledge. However, ILP algorithms deal poorly with large data sets (>10⁴ examples) and their widespread use of the greedy set-covering algorithm renders them susceptible to local maxima in the space of logic programs.This paper presents a novel approach to address these problems based on combining the local search properties of an inductive logic programming algorithm with the global search properties of an evolutionary algorithm. The proposed algorithm may be viewed as an evolutionary wrapper around a population of ILP algorithms.The evolutionary wrapper approach is evaluated on two domains. The chess-endgame (KRK) problem is an artificial domain that is a widely used benchmark in inductive logic programming, and Part-of-Speech Tagging is a real-world problem from the field of Natural Language Processing. In the latter domain, data originates from excerpts of the Wall Street Journal. Results indicate that significant improvements in predictive accuracy can be achieved over a conventional ILP approach when data is plentiful and noisy.     

Specifying Real-Time Finite-State Systems in Linear Logic (Extended Abstract)

Abstract

Real-time finite-state systems may be specified in linear logic by means of linear implications between conjunctions of fixed finite length. In this setting, where time is treated as a dense linear ordering, safety properties may be expressed as certain provability problems. These provability problems are shown to be in pspace. They are solvable, with some guidance, by finite proof search in concurrent logic programming environments based on linear logic and acting as sort of model-checkers. One advantage of our approach is that either it provides unsafe runs or it actually establishes safety.     

对象式逻辑程序设计

本文首先对逻辑程序设计与对象式程序设计进行一些比较，然后介绍对象式逻辑程序设计的基本原理、新进展、应用及目前存在的主要问题。     

Aggregated Fuzzy Answer Set Programming

Fuzzy Answer Set Programming (FASP) is an extension of answer set programming (ASP), based on fuzzy logic. It allows to encode continuous optimization problems in the same concise manner as ASP allows to model combinatorial problems. As a result of its inherent continuity, rules in FASP may be satisfied or violated to certain degrees. Rather than insisting that all rules are fully satisfied, we may only require that they are satisfied partially, to the best extent possible. However, most approaches that feature partial rule satisfaction limit themselves to attaching predefined weights to rules, which is not sufficiently flexible for most real-life applications. In this paper, we develop an alternative, based on aggregator functions that specify which (combination of) rules are most important to satisfy. We extend upon previous work by allowing aggregator expressions to define partially ordered preferences, and by the use of a fixpoint semantics.     

Subdefinite Models and Logic Programming: Implementation of Constraints

Subdefinite models, described in [11], are a common approach to representation and processing of partial specifications. This approach is closely related to constraint programming, and, actually, is a method for constructing constraint satisfaction algorithms. The paper describes subdefinite models themselves, the method of their integration into logic programming, and two calculators created on the basis of this method. Results of a comparison of these calculators with the best available calculators designed for the same purpose are given. Applications are listed that were developed on the base of these calculators for solving problems of SAPR and computational geometry.