自然约束语言（英文版） 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

The NCL Natural Constraint Language presents the NCL Language which is a de*ion language in conventional mathematical logic for modeling and solving constraint satisfaction problems.NCL differs from other declarative languages:It models problems naturally in a simplified form of first-order logic with quantifiers,Boolean logic,numeric constraints,set operations and logical functions;it solves problems by mixed set programming over the mixed domain of real numbers,integers,Booleans,dates/times,references,and in particular sets.The book uses plenty of examples and tutorials to illustrate NCL and its applications.It is intended for researchers and developers in the fields of logic programming,constraint programming,optimization,modeling,operations research and artificial intelligence,who will learn from a new programming language and theoretical foundations for industrial applications.

Dr.Jianyang Zhou is the inventor of NCL and has worked for its industrialization for more than 10 years.

1 Introduction

1.1 Modeling and Solving

1.1.1 Programming Framework and Algorithm

1.1.2 Formal Grammar and Parser

1.2 The NCL Language

1.2.1 Natural Modeling in Mathematical Logic

1.2.2 Cooperative Solving

1.2.3 Comparison with Some Other Systems

1.3 The POEM Platform

1.3.1 Development Toolkit

1.3.2 Component and Server

References

2 Data Types and Lexical Conventions

2.1 Data Types

2.1.1 Generality

2.1.2 Set

2.1.3 Date/Time

2.1.4 Numeric

2.2 Lexical Tokens

2.2.1 Characters

2.2.2 Identifiers

2.2.3 Predefined Identifiers

2.2.4 Constants

2.2.5 Non-Instantiated Values

2.2.6 Comments

2.3 Mathematical Notations

2.3.1 Mathematical Symbols

2.3.2 Predefined Functions

2.3.3 Delimiters of TeX

References

3 Grammar and Semantics

3.1 Context-Free Rules

3.1.1 Overall Structure

3.1.2 Expression

3.1.3 Constraint

3.1.4 Declaration

3.1.5 Declarative Control

3.1.6 Temporal Control

3.1.7 Search and Optimization

3.2 Context-Sensitivity of NCL

3.2.1 Constant

3.2.2 Variable

3.2.3 Function

3.2.4 Sub-Model

References

4 Tutorial Programs

4.1 Getting Started

4.1.1 Input and Output

4.1.2 Default Value

4.1.3 Data Buffer

4.2 Boolean Logic

4.3 Numerical Reasoning

4.3.1 Integer Equation

4.3.2 Infinity

4.4 Date/Time

4.5 String

4.5.1 String Input

4.5.2 Concatenation

4.6 Referencing

4.6.1 Reference in a Subscript

4.6.2 Referenced Operator

4.6.3 Subscript Leak

4.7 Set Reasoning

4.7.1 A General Example

4.7.2 Attributes of a Set

4.7.3 Piecewise Intervals from a Set

4.8 Special Variable

4.8.1 Anonymous Variable

4.8.2 System Variable

4.9 Predefined Function

4.9.1 Float Function

4.9.2 Aggregate Function

4.9.3 Transformation

4.9.4 Substring

4.9.5 Elements of a Set

4.9.6 Date/Time Attribute

4.9.7 Extraction

4.9.8 Assignment

4.10 User-Defined Function

4.10.1 Cotangent

4.10.2 Global Variable in a Function

4.10.3 Query and Objective in a Function

4.10.4 Predicate

4.10.5 Recursive Function

4.10.6 Termination of a Recursion

4.10.7 Tree

4.11 Selection Statement

4.11.1 Switch

4.11.2 If-Then-Else

4.12 Quantification

4.12.1 Existential Quantification

4.12.2 Universal Quantification

4.13 Jump

4.13.1 Exit from a Universally Quantified Statement

4.13.2 Exit from an Infinite Loop

4.14 Query and Search

4.14.1 Approximate Solution

4.14.2 Search over a Float Domain

4.15 Optimization Objective

4.15.1 Single-Objective Optimization

4.15.2 Multiple-Objective Optimization

4.16 Custom Message

4.17 Soft Constraint

4.18 Sub-Model

4.18.1 Sub-Model in a File

4.18.2 Sub-Model in a Buffer

4.18.3 Return Values of a Sub-Model

4.18.4 Recursive Sub-Model

4.18.5 Overflow in Calling a Sub-Model

4.19 SQL Query

4.20 OS Command

4.21 Expectation and Debugging

5 The POEM Software Platform

5.1 Main Interface

5.1.1 Tool Bar

5.1.2 TeX Bar

5.1.3 Workspace

5.1.4 Edit Window

5.1.5 Trace Window

5.2 Configuration of a Project

5.2.1 Data Pools for a Project

5.2.2 NCL Parameters

5.2.3 Project Settings

5.3 Model Management

5.3.1 Model Folder

5.3.2 Model Library

5.4 Information Tables

5.4.1 Running Models

5.4.2 Constants

5.4.3 Variables

5.4.4 Constraints

5.5 Visualization and Debugging

5.5.1 Quick Watch

5.5.2 Browser

5.5.3 Constraint Debugger

5.5.4 Visual Debugger

5.5.5 Solution Viewer

5.6 Trace Window and Working Modes

5.6.1 Debug Mode

5.6.2 Timer Mode

5.6.3 Trace Level

5.6.4 Options for Diagnosis

5.6.5 Options for Statistics

5.6.6 Recommended Diagnosis Mode

5.6.7 Recommended Working Mode

5.7 Message Management

5.7.1 Message Levels

5.7.2 Message Types

5.7.3 Message Codes

5.7.4 Message Handler

5.7.5 Termination Status

5.8 Help on Line

5.9 Component and Server

6 Modeling and Solving

6.1 Development Principles

6.1.1 Generality

6.1.2 Data Modeling

6.1.3 Modeling Constraints and Objectives

6.1.4 Modeling Queries

6.1.5 Test and Benchmarking

6.1.6 Diagnosing a Model

6.2 Modeling Abstraction

6.2.1 Distinct Integers

6.2.2 Disjoint Sets

6.2.3 Sorting

6.2.4 Set Covering

6.2.5 Packing

6.2.6 Sum

6.2.7 Cumulation

6.3 Solving Puzzles

6.3.1 Send More Money

6.3.2 Primes

6.3.3 Integer Sorting

6.3.4 Queens

6.3.5 Magic Square

6.3.6 Sudoku

6.3.7 Magic Sequence

6.3.8 Einstein恠 Quiz

6.3.9 Calculs d怑nfer

6.3.10 Square Packing

6.3.11 Knight

6.4 Solving Hard Problems

6.4.1 Set Partitioning

6.4.2 Golf Tournament

6.4.3 Progressive Party

6.4.4 Ship Loading

6.4.5 Job-Shop Scheduling

6.4.6 Minimizing the Cost of a Heat Exchanger

6.4.7 Pick-up and Delivery

6.4.8 Exercises

References

7 Industrial Applications

7.1 Complexity of Industrial Problems

7.2 Production Scheduling

7.2.1 Problem Definition

7.2.2 Data Model

7.2.3 Simplified Optimization Model

7.2.4 Visualizing Time: Gantt Chart

7.2.5 Questions

7.3 Personnel Planning

7.3.1 Problem Definition

7.3.2 Data Model

7.3.3 Simplified Optimization Model

7.3.4 Visualizing Statistics: Histogram

7.3.5 Questions

7.4 Multi-Modal Transportation Planning

7.4.1 Problem Definition

7.4.2 Data Model

7.4.3 Simplified Optimization Model

7.4.4 Visualizing Geographical Information: Map

7.4.5 Questions

References

8 Relaxation and Decomposition

8.1 Local Optimization by Relaxation

8.1.1 Relaxation and Interaction

8.1.2 Local Optimization

8.1.3 Iterative Optimization for TSP

8.2 Solving by Decomposition

8.2.1 Solving by Model Decomposition

8.2.2 Model Decomposition for Vehicle Routing

8.2.3 Solving by Data Decomposition

8.2.4 Data Decomposition for Production Scheduling

References

Appendix 1 The Grammar in TeX

Overall Structure

Declaration

Explicit Typing

Function Definition

Label

Elementary Statement

Constraint

Assignment

Optimization Objective

Query and Search

Enumeration Mode

Query Criterion

Output

Data Format

Expectation

Control

Compound Statement

Grouped Statement

Included File

Soft Statement

Custom Message

Selection

Switch

If-Then-Else

Quantification

Existential Quantification

Universal Quantification

Indexing

Jump

Data Connection

Expression

Boolean

Float

Integer

Date/Time

String

Grouped String

Concatenation

Reference

Set

Constant

Variable

System Variable

Input

Extraction

Function

Data Pool

Sub-Model

SQL Query

OS Command

Appendix 2 The ComPoem Component

Description

Properties

Functions

Events

Index

暂无相关内容，正在全力查找中

暂无出版社相关信息，正在全力查找中！

1 Introduction

This introduction is a brief presentation of NCL (Natural Constraint Language)

and its software platform POEM? (Programming in Operational and Expressive

Models). After reading this chapter, readers will have a clear idea about the main

features of NCL.

Section 1.1 gives a quick overview of some systems for modeling and solving.

At the solver level, a new algorithmic framework called “Mixed Set

Programming” is proposed. At the parser level, “Semantic Parser” based on

context analysis and implicit typing is presented.

Section 1.2 presents the NCL language and its main features in terms of

“Natural Modeling”, “Mixed Set Programming” and “Search Rules”. The basic

differences between NCL and some other systems are discussed.

Section 1.3 presents the software platform POEM, which integrates NCL and

visualization facilities for developing industrial solutions.

1.1 Modeling and Solving

Constraint Satisfaction Problems (CSP) are ubiquitous in the real world. Being

usually NP-hard, they are in general very difficult to solve. Computational complexity

theory suggests that if a problem is NP-complete (or NP-hard), then there

does not exist any algorithm to solve it in polynomial time unless P equals NP

(Garey and Johnson 1979).

In an informal manner, this section studies critical subjects on dealing with

constraint satisfaction problems: “programming framework and algorithm” and

“formal grammar and parser”, respectively for problem solving and mathematical

modeling.

1.1.1 Programming Framework and Algorithm

In this section, some programming frameworks for problem solving will be

studied to show the nature of the NCL solver.

Linear Programming

Operations Research (OR) is a scientific discipline which studies management and

decision problems in various fields.

In OR, a particularly successful technique is Linear Programming which tackles

the optimization of a linear objective function subject to linear equality and/or

inequality constraints (Kantorovich 1939). In 1947, George Dantzig invented the

simplex method (Dantzig 1990) for solving linear programming problems. Based

on Linear Programming and linear relaxation, the OR community has created step

by step a mathematical programming paradigm: Linear Programming, Integer

Programming, 0-1 Programming, Mixed Integer Programming, etc. There exists a

modeling language AMPL for mathematical programming (Fourer et al. 1993).

Although originally it is not related to computer programming, compared to

other programming frameworks, linear programming is viewed in this book as

computer programming in linear models.

Logic Programming

Generally speaking, logic programming is the use of mathematical logic for

computer programming. As one of the first logic programming languages, Prolog

was invented by Alain Colmerauer and his team in Marseille in the early 1970s

(Colmerauer et al. 1973). Prolog allows programmers to write programs in a

declarative style. For a programmer, with Prolog in mind, declarative programming

becomes clearly distinguished from imperative programming of procedural

languages such as the C programming language (Kernighan and Ritchie 1988).

Regarding logic programming, this book concentrates on the study of firstorder

logic (Barwise 1977). First-order logic is mainly distinguished from propositional

logic by its use of quantifiers; compared to second-order logic, first-order

logic uses only variables that range over the domains of discourse.

Constraint Programming

Constraint Programming (CP) is a programming paradigm where relations

between variables are expressed in the form of constraints. Compared to Logic

Programming, CP concentrates more on problem-solving algorithms by reasoning

over variable domains.

Research work on Constraint Programming was started in the 1980s (Jaffar and

Lassez 1987; Dincbas et al. 1988; Colmerauer 1990; Smolka 1995). Principally,

its idea is to incorporate “solvers” into declarative programming frameworks such

as logic programming and functional programming for solving constraint satisfaction

problems. In this sense, Prolog II (Colmerauer 1982) is the first CP system if

disequations as well as equations are constraints. Different from linear programming

methods, CP breaks through the limitation of linear modeling; it studies

problem-solving algorithms in a more general way.

Mixed Set Programming

Linear solvers are efficient in solving problems of linear models. However,

algorithms of a linear solver may have the following limitation: Linear

programming handles a system of linear constraints with a linear objective

function. This means that it necessitates transforming non-linear constraints into

linear form, which may be difficult and may pose the problem of readability and

clarity to models.

Constraint Programming is a flexible programming paradigm. However, with a

short development history, its performance seems not yet satisfactory enough

compared to mathematical programming, for example, in solving problems such

as Set Partitioning (Hoffman and Padberg 1993) and Vehicle Routing (Solomon

1987).

Based on the above observation, this book proposes an algorithmic framework

called Mixed Set Programming (MSP) (Zhou 2008) which deals with constraint

satisfaction problems over the mixed domain of real numbers, integers, Booleans,

dates/times, references, and in particular sets of integers. Reasoning over sets of

integers in the sense of naive set theory (Halmos 1960) is the strongest feature of

MSP.

Mixed Set Programming incorporates and combines a simplified form of firstorder

logic, numeric constraints over integers (Dincbas et al. 1988) and over real

numbers (Colmerauer 1990; Benhamou 1994; Colmerauer 1995), set reasoning

(Zhou 1998) and date/time management (Zhou 2009). Here, set theoretical

formulation is fundamental in problem modeling and set theoretical reasoning is

crucial in problem solving. Mixed Set Programming leads to an enhanced

expressive and algorithmic power for modeling and solving constraint satisfaction

problems.

Search Rules

NP-hard problems pose computational challenges to algorithms. Unless P equals

NP, no algorithm can guarantee a solution to an NP-hard problem in satisfactory

time; no matter how powerful a solver is, it is always “fragile” facing “NP-hard”.

Due to this consideration, to introduce search rules into a problem-solving

system becomes a natural idea. Search rules allow a programmer to exploit the

specific structure of a problem to well solve it. On one hand, search rules based on

the problem logic of a specific field can help to construct a feasible solution

rapidly. On the other hand, search rules can help to contain combinatorial

explosion by “regulating” the search in the solution space. The combination of

search rules and a solver makes a problem-solving system more robust.

1.1.2 Formal Grammar and Parser

A formal language is a set of strings defined over an alphabet. A formal grammar

is a set of rules for rewriting strings in a formal language. To the rules a finite set

of terminal symbols and a finite set of non-terminal symbols are associated.

Among the symbols, a special non-terminal is chosen to be the start symbol

(Chomsky 1956).

The rules describe how to produce strings according to the language’s syntax.

A string in the language is generated by applying the rules in some order, initially

on the start symbol, until all non-terminal symbols are removed. The formal language

of the grammar amounts to the set of all distinct strings generated in such a

way. In this sense, the rules are called production rules.

For the application of production rules, there is a strategy called “leftmost derivation”

which means “always rewrite the leftmost non-terminal first”. Analogously,

“rightmost derivation” means “always rewrite the rightmost non-terminal

first”.

In this book, context-free and context-sensitive grammars are used to study the

NCL language.

Context-Free Grammar

A context-free grammar is a grammar in which every production rule is of the

form “A → w” where A is a single non-terminal symbol and w is a (possibly

empty) string of terminals and/or non-terminals.

Backus-Naur Form (BNF) is a meta-syntax used to express context-free grammars

(Knuth 1964). Programming languages tend to be specified in terms of a

context-free grammar because efficient parsers can be written for them. Almost all

modern languages are context free and can be described in BNF (Wikipedia

2010).

For example, the language {[n ]n : n ≥ 0}, where [n denotes a string of n

consecutive [’s, can be produced by the following grammar:

?? Non-terminals: S

?? Start symbol: S

?? Terminals: ?, [, ]

?? Production rules:

S → ? (1)

S → [S] (2)

Here ? is the empty string.

For example, the generation chain for [[]] is: S →2 [S] →2 [[S]] →1 [[]]

Note that in NCL, the square brackets [] are used to denote objects such as included

file, text file, buffer and database, etc.

To simplify the presentation, the two rules can be written as below with a vertical

bar (|) separating them:

S → ? (1)

| [S] (2)

Context-Sensitive Grammar

A formal grammar is context-sensitive if all production rules are of the form “α A

β → α w β” where A is a single non-terminal symbol, α and β are (possibly

empty) strings of non-terminals and terminals and w is a non-empty string of nonterminals

and terminals.

The term “context-sensitive” comes from the introduction of α and β as a

“context” for A, which determines whether A can be replaced by w or not.

The canonical non-context-free grammar for the language {anbncn : n > 0} is:

?? Non-terminals: A, B

?? Start symbol: A

?? Terminals: a, b, c

?? Production rules:

A → aBAc

| abc

Ba → aB

Bb → bb

The form of the rules requires that in “α A β → α w β” w is non-empty.

But in practice, rules of the form “A → ?” (with ? being the empty string) may

be very useful.

For more details, readers are referred to (Chomsky 1956).

Parser, LL Parser and LR Parser

With respect to a given formal grammar, parsing is to determine if and how an input

string can be derived from the start symbol of the grammar. A parser is a program

for parsing, which checks for correct syntax, builds a data structure, and recognizes

semantic information implicit in the input (Aho et al. 1986; Grune and

Jacobs 1990).

For a context-free grammar, leftmost derivation or rightmost derivation leads to

different types of parsing:

?? Top-down parsing: It attempts to find leftmost derivations of the input by using

a top-down expansion of the production rules. LL parsers (Left to right,

Leftmost derivation) are examples of top-down parsers;

?? Bottom-up parsing: It attempts to rewrite the input to the start symbol by applying

the production rules reversely. That is, instead of derivation it works

by creating a "leftmost reduction" of the input; the end result, after reversed,

will be a rightmost derivation. LR parsers (Left to right, Rightmost derivation)

are examples of bottom-up parsers. An efficient type of LR parser is

look-ahead LR parser (LALR).

Ambiguity of a Context-Free Grammar

A context-free grammar is said to be ambiguous if there exists a string which can

be generated by the grammar in more than one way by leftmost derivation. For

example, the context-free grammar

A → A + A (1)

| A ? A (2)

| a (3)

is ambiguous since there are two leftmost derivations for the string a+a?a (Figure

1.1):

?? A →1 A+A →3 a+A →2 a+A?A →3 a+a?A →3 a+a?a

?? A →2 A?A →1 A+A?A →3 a+A?A →3 a+a?A →3 a+a?a

However, for the above example there exist parser generators such as YACC

(Johnson 1979) that can disambiguate this kind of ambiguity by using the precedence

and associativity constraints.

Vagueness in Reduction

Besides ambiguity in derivation, for a LR parser there may be the problem of

vagueness in terms of leftmost reduction. In a bottom-up reduction, when more

than one rule have the same right-hand side, reduction conflicts may need to be

settled. One way to accommodate such conflicts is by introducing contextsensitive

rules; see Section 3.2.

Semantic Parser

The parsing for a description language like NCL is complex. It necessitates an

intelligent parsing system, referred to as “Semantic Parser” (Zhou 2000), to

understand natural problem formulation in mathematical logic and submits

abstract models to embedded algorithms for efficiently solving problems.

Semantic parser of NCL is different from that of an imperative programming

language such as C, logic programming languages such as Prolog and modeling

languages such as AMPL. Differences will be discussed in the next section.

1.2 The NCL Language

NCL is a description language in mathematical logic. It offers user a language,

which is fast to learn and easy to use, for modeling and solving constraint satisfaction

problems in a natural and concise way.

Designing the NCL language became its author’s idea around 1995 during his

PhD study. The idea is quite simple: Using TeX (Knuth 1984) as basic formalism

to express combinatorial problems and solving them by a constraint solver. A paper

on the first NCL prototype was submitted in December 1997 to The Third International

Conference on Systems Science and Systems Engineering (Zhou

1998). A formal paper (Zhou 2000) was submitted in March 1998 to The Journal

of Logic Programming, official journal of the Association for Logic Programming

at that time. The NCL language has greatly evolved in the past 10 years. Its main

features can be outlined as below:

?? Natural Modeling: Building models that are problem descriptions in

conventional mathematical logic;

?? Mixed Set Programming: Solving problems over a mixed domain of real

numbers, integers (generalized to dates/times, strings, references, etc.),

Booleans, and sets in a cooperative manner;

?? Search Rules: Supporting concise search specifications. This makes the

programming of search strategies simple and straightforward.

1.2.1 Natural Modeling in Mathematical Logic

NCL allows a programmer to describe problems naturally, within the conventions

of mathematical logic. Its semantic parser supports context-based analysis and

在线阅读地址：自然约束语言（英文版）在线阅读

在线听书地址：自然约束语言（英文版）在线收听

在线购买地址：自然约束语言（英文版）在线购买

暂无原文赏析，正在全力查找中！

编辑推荐

　　The NCL Natural Constraint Language presents the NCL languagewhich is a de*ion language in conventional mathematical logicfor modeling and solving constraint satisfaction problems．NCLdiffers from other declarative languages：It models problemsnaturally in a simplified form of first—order logic withquantifiers Boolean logic，numeric constraints，set operations andlogical functions；it solves problems by mixed set programming overthe mixed domain of real numbersIntegers，Booleans，dates／times，references，and in particular sets．Thebook uses plenty of examples and tutorials to illustrate NCL andits applications．It is intended for researchers and developers inthe fields of logic programmin9，constraintprogrammin9，optimization，modelin9，operations research andartificial intelligence．who will learn from a new programminglanguage and theoretical foundations for industrialapplications．