自然约束语言

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?s Quiz

6.3.9 Calculs d?Enfer

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

The NCL Natural Constraint Language presents the NCL Language which is a description 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.