Building Decision Support Systems: using MiniZinc

Preface
	Scope of This Book
	Hands-on Learning
	Acknowledgements
Contents
1 Motivation for IDS
	1.1 History
		1.1.1 Menial Tasks
		1.1.2 Managerial Tasks
		1.1.3 Entrepreneurial Tasks
	1.2 ``Intelligent\'\' in IDS
		1.2.1 The Meaning of ``Intelligent\'\' in IDS
	1.3 Risks in ``Intelligent\'\' IDS
	1.4 IDS Scope
		1.4.1 Strategic IDS
		1.4.2 Tactical IDS
		1.4.3 Operational IDS
	1.5 Summary
2 Modelling and Choices
	2.1 Some Example Problems and Their Solutions
		2.1.1 Selecting Numbers from a Set
		2.1.2 The Knapsack Problem
		2.1.3 Breaking Chocolate
	2.2 The Basics of Problem Modelling
		2.2.1 Fundamental Concepts and Definitions
		2.2.2 Definitions of Modelling Concepts
		2.2.3 Modelling Some Example Problems
		2.2.4 Modelling with Arrays
	2.3 Summary
3 Examples of Industrial Decisions
	3.1 Strategic Optimisation Examples
		3.1.1 Case Histories
		3.1.2 Issues in Strategic Planning
	3.2 Tactical Decision Support
		3.2.1 Case Histories
		3.2.2 Issues in Tactical Scheduling
	3.3 Operational Control
		3.3.1 Case Histories
		3.3.2 Issues in Operational Control
	3.4 Intelligent Decision Support in Practice
	3.5 Summary
4 Problem Modelling in MiniZinc
	4.1 Variables, Constraints and Parameters
		4.1.1 A Model for a Simple Problem
	4.2 Modelling the Knapsack Problem
		4.2.1 Arrays
		4.2.2 Data
		4.2.3 Knapsack with Item Weights and Values
	4.3 Assignment and Travelling Ecologist
		4.3.1 Constraining All the Items in an Array with ``forall\'\'
		4.3.2 Assignment Problem
		4.3.3 Travelling Ecologist Problem
	4.4 Summary
	4.5 Exercises
		4.5.1 Worker Task Assignment Exercise
		4.5.2 Knapsack Exercise
5 Algorithms and Complexity
	5.1 Combinatorial Problems
		5.1.1 Chess
		5.1.2 The Number of Candidate Solutions for Larger Problem Instances
	5.2 Generate and Test
		5.2.1 A Method for Testing a Finite Number of Candidates
		5.2.2 Lazy and Eager Generate and Test
	5.3 The Concept of Algorithmic Complexity
		5.3.1 Can We Measure Problem Difficulty?
		5.3.2 Complexity Is a Measure of Scalability
		5.3.3 Complexity Is an Approximation
	5.4 Measuring Complexity
		5.4.1 Worst-Case Performance
		5.4.2 Constant Complexity
		5.4.3 Logarithmic Complexity
		5.4.4 Linear Complexity
		5.4.5 Exponential Complexity
		5.4.6 Polynomial Complexity
	5.5 P and NP
	5.6 Problem Complexity
		5.6.1 Algorithms for Solving IDSS Applications
		5.6.2 NP Complete Problems
		5.6.3 Complexity Class NP-hard
		5.6.4 Relating the Different Complexity Classes
	5.7 Summary
6 Constraint Classes
	6.1 Introduction
		6.1.1 Five Classes of Constraints
	6.2 Finite Domain Constraints
		6.2.1 Finitely Many Combinations to Check
		6.2.2 Logical Combinations of Constraints
	6.3 Propositional Constraints
	6.4 Linear Constraints
		6.4.1 Floating Point Expressions
		6.4.2 Expressive Power and Complexity of Floating Point Constraints
		6.4.3 Linear Expressions and Constraints
	6.5 Linear Constraints over Integers and Floats
	6.6 Nonlinear Constraints
		6.6.1 Nonlinear Functions and Expressions
		6.6.2 Nonlinear Problems
	6.7 Summary
7 Constraint Classes and Solvers
	7.1 Linear Programming Models
		7.1.1 Linear Expressions and Constraints
		7.1.2 Solving Linear Problems
	7.2 Propositional Models
		7.2.1 Proposition Expressions and Propositional Clauses
		7.2.2 Benchmark Results
		7.2.3 Converting a Propositional Model to Propositional Clauses
		7.2.4 Resolution for Solving Clausal Models
		7.2.5 Encoding Numbers in Propositional Models
		7.2.6 Lazy Clause Generation
	7.3 Finite Integer Models
		7.3.1 Finitely Many Combinations to Check
		7.3.2 Tables
		7.3.3 Minimising the Number of Rows in Intermediate Tables
		7.3.4 Minimising the Number of Columns
		7.3.5 Dynamic Programming
		7.3.6 Complexity of Finite Integer Models
		7.3.7 Answer to Minimising Intermediate Table Widths
	7.4 Linear Constraints over Integers and Floats
		7.4.1 Unbounded Integer Constraints
		7.4.2 Branch and Bound
		7.4.3 Cutting Planes
		7.4.4 Logical Combinations of Linear Constraints
		7.4.5 Linear Constraints over Integer Variables
		7.4.6 Complexity of Linear Constraints over Integers and Floats
	7.5 Nonlinear Constraints
		7.5.1 Solving Non-linear Problems
		7.5.2 Complexity of Nonlinear Constraints
	7.6 Summary
8 Constraint Classes in MiniZinc
	8.1 Logical Connectives
	8.2 Comprehensions
	8.3 Predicates and Functions
		8.3.1 A Simple Predicate and a Simple Function
		8.3.2 Predicates and Functions with Local Variables
		8.3.3 Predicates for Flexibility
	8.4 Global Constraints and Built-In Functions
		8.4.1 Two Problems Modelled with alldifferent in MiniZinc
	8.5 Constraint Classes
		8.5.1 Reification
		8.5.2 Unbounded Integer Constraints
		8.5.3 Floating Point Expressions
		8.5.4 Linear Expressions and Constraints
		8.5.5 Linear Constraints over Integers and Floats
		8.5.6 Nonlinear Problems
	8.6 Specifying the Solver in MiniZinc
	8.7 Summary
	8.8 Exercises
		8.8.1 Trucking Exercise
		8.8.2 Tour Leader Exercise
9 Integrating Solvers with Search
	9.1 Generate and Test
	9.2 Finite Domain Propagation
		9.2.1 Arc Consistency
		9.2.2 Bounds Consistency
	9.3 Tree Search
		9.3.1 Complete Search Without Following a Wrong Branch
		9.3.2 Depth-First Search with Backtracking
	9.4 Reordering the Search Tree
		9.4.1 Variable Order
		9.4.2 Value Order
		9.4.3 Combining Search Heuristics
	9.5 Methods of Exploring the Search Tree
		9.5.1 Hard and Easy Problems
		9.5.2 Depth-First Search
		9.5.3 Breadth-First Search
	9.6 Optimisation
		9.6.1 Admissible Estimates of Cost
		9.6.2 Best First Search
		9.6.3 Branch and Bound
		9.6.4 Why Optimisation Is Hard
	9.7 Learning and Restarts
		9.7.1 Restarts
		9.7.2 Learning
	9.8 Incomplete Search Methods
		9.8.1 Bounded Backtrack Search and Limited Discrepancy Search
	9.9 Summary of Tree Search
	9.10 Local Search
		9.10.1 Hill Climbing
		9.10.2 Escaping from Local Optima
		9.10.3 Large Neighbourhood Search
		9.10.4 Local Search and Learning
	9.11 Summary
10 Search Control in MiniZinc
	10.1 The Search Annotation
	10.2 Controlling Variable Order
	10.3 Controlling Value Order
	10.4 Combining Multiple Search Variants
	10.5 Restarting
	10.6 Summary
	10.7 Exercises
		10.7.1 Maximize the Differences
		10.7.2 Develop a Roster
11 Uncertainty
	11.1 What Is Uncertainty
		11.1.1 Probability
		11.1.2 Confidence
	11.2 Working with Probability
		11.2.1 Multiplying Probability by Cost
		11.2.2 Probability Distribution
		11.2.3 Dependent and Independent Probability Distributions
	11.3 Scenarios
		11.3.1 Two Scenarios
		11.3.2 Four Scenarios
		11.3.3 Scenarios Approximating Continuous Probability Distributions
		11.3.4 Solving Problems with Multiple Scenarios
	11.4 Statistics
		11.4.1 Sampling
		11.4.2 The Law of Large Numbers
		11.4.3 Large Numbers and Small Probabilities
	11.5 Summary
12 IDSS for Optimisation: The Future
	12.1 Transport and Congestion
	12.2 Energy
	12.3 Automation
	12.4 Integrated Supply Chains
	12.5 4th Industrial Revolution
	12.6 Learning, Optimisation, and Policies
	12.7 Summary
Appendix A
	A.1 Big O Notation
	A.2 Working Out the Complexity of an Algorithm
Solutions
	Exercises from Chap. 4
		Worker Task Assignment
			First Challenge
			Second Challenge
			Third Challenge
		Knapsack
			First Challenge
			Second Challenge
			Third Challenge
	Exercises for Chap. 8
		Trucking
			First Challenge
			Second Challenge
			Third Challenge
		Tour Leader Assignment
			Challenge
	Exercise for Chap. 10
		Tournament
References
Index