Archives of Control Sciences

Last issue
2017 (vol. 27) - Number 2

W. Bozejko, M. Wodecki:

Discrete Systems: Theory and Applications. Special issue.

G. Bocewicz, Z. Banaszak, I. Nielsen:

Delivery-flow routing and scheduling subject to constraints imposed by vehicle flows in fractal-like networks

W. Bozejko, A. Gnatowski, R. Idzikowski, M. Wodecki:

Cyclic flow shop scheduling problem with two-machine cells

W. Bozejko, M. Uchronski,, Z. Chaczko, M. Wodecki:

Parallel patterns determination in solving cyclic flow shop problem with setups

J. Brodny, S. Alszer, J. Krystek, M. Tutak:

Availability analysis of selected mining machinery

K. Chmielewska, D. Formanowicz, P. Formanowicz:

The effect of cigarette smoking on endothelial damage and atherosclerosis development - modeled and analyzed using Petri nets

A. Galuszka, J. Krystek, A. Swierniak, T. Grzejszczak, C. Lungoci:

Information management in passenger traffic supporting system design as a multi-criteria discrete optimization task

M. Kardynska, J. Smieja:

Sensitivity analysis of signaling pathway models based on discrete-time measurements

J. Kasprzyk, P. Krauze, S. Budzan, J. Rzepecki:

Vibration control in semi-active suspension of the experimental off-road vehicle using information about suspension deflection

M. Koryl, D. Mazur:

Towards emergence phenomenon in business process management

M. Koryl:

Active resources concept of computation for enterprise software

H. Krawczyk, M. Nykiel:

Mobile devices and computing cloud resources allocation for interactive applications

W. Mitkowski, W. Bauer, M. Zagórowska:

Discrete-time feedback stabilization

J. Pempera:

An exact block algorithm for no-idle RPQ problem

K. Rzosinska, D. Formanowicz, P. Formanowicz:

The study of the influence of micro-environmental signals on macrophage differentiation using a quantitative Petri net based model

K. Skrzypczyk , M. Mellado:

Vehicle navigation in populated areas using predictive control with environmental uncertainty handling

W. Bozejko, J. Pempera, M. Wodecki:

A fine-grained parallel algorithm for the cyclic flexible job shop problem

ACS Abstract:

2006 (Volume 16)
Number 2

1.	Principles of constraint systems and constraint solvers
2.	An introduction to interval-based constraint processing
3.	Filtering algorithms for the Same and UsedBy constraints
4.	Message delay and asynchronous DisCSP search

Principles of constraint systems and constraint solvers Download full PDF article

Thom Frühwirth
(Faculty of Computer Science, University of Ulm, Germany)

Slim Abdennadher
(Department of Computer Science, German University Cairo, Egypt)

In this compact overview, we introduce the most common constraint systems used in constraint programming languages and algorithms to solve them. Constraint systems are the result of taking a data type together with its operations and interpreting the resulting expressions as constraints. These constraint systems use the universal data types of numbers (integers or reals) to represent scalar data or terms to represent structured data. Algorithms are presented as logical inference rules that are directly executable in the Constraint Handling Rules language.

keywords: computational logic, executable specifications, rule-based programming, program analysis, algorithms

^top

An introduction to interval-based constraint processing Download full PDF article

Gerrit Renker, Hatem Ahriz
(School of Computing, The Robert Gordon University, Aberdeen, UK)

Constraint programming is often associated with solving problems over finite domains. Many applications in engineering, cad and design, however, require solving problems over continuous (real-valued) domains. While simple constraint solvers can solve linear constraints with the inaccuracy of floating-point arithmetic, methods based on interval arithmetic allow exact (interval) solutions over a much wider range of problems. Applications of interval-based programming extend the range of solvable problems from non-linear polynomials up to those involving ordinary differential equations.

In this text, we give an introduction to current approaches, methods and implementations of interval-based constraint programming and solving. Special care is taken to provide a uniform and consistent notation, since the literature in this field employs many seemingly different, but yet conceptually related, notations and terminology.

keywords: constraint programming, interval-based computation, interval consistency techniques

^top

Filtering algorithms for the Same and UsedBy constraints Download full PDF article

Nicolas Beldiceanu
(Ecole des Mines de Nantes, Nantes Cedex, France)

Irit Katriel, Sven Thiel
(Max-Planck-Institut fur Informatik, Saarbrucken, Germany)

We define the Same and UsedBy constraints. UsedBy takes two sets of variables X and Z such that |X| > |Z| and assigns values to them such that the multiset of values assigned to the variables in Z is contained in the multiset of values assigned to the variables in X. Same is the special case of UsedBy in which |X|=|Z|. We show algorithms that achieve arc-consistency and bound-consistency for these constraints.

keywords: arc-consistency, bound-consistency, constraint programming, filtering algorithm, global constraint, network flow, strongly connected component

^top

Message delay and asynchronous DisCSP search Download full PDF article

Roie Zivan, Amnon Meisels
(Department of Computer Science, Ben-Gurion University of the Negev, Israel)

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been shown in experimental studies of asynchronous backtracking algorithms. To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the number of non-concurrent steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. The performance of two asynchronous search algorithms is measured on randomly generated instances of DisCSPs with delayed messages. The Asynchronous Weak Commitment (AWC) algorithm and Asynchronous Backtracking (ABT). The intrinsic reordering process of AWC dictates a need for a more complex count of non-concurrent steps of computation. The improved counting algorithm is also needed for Dynamic ordered ABT. The delay of messages is found to have a strong negative effect on AWC and a smaller effect on dynamically ordered ABT.

keywords: distributed constraint satisfaction, search, distributed AI

^top

<< Back