User guide

FICO Xpress Optimization
R

Xpress Kalis
User guide
Release 12.6

Last update 7 July, 2017www.fico.com

Make every decision countTM

This material is the confidential, proprietary, and unpublished property of Fair Isaac Corporation. Receipt or possession of thismaterial does not convey rights to divulge, reproduce, use, or allow others to use it without the specific written authorizationof Fair Isaac Corporation and use must conform strictly to the license agreement.
The information in this document is subject to change without notice. If you find any problems in this documentation, please
report them to us in writing. Neither Fair Isaac Corporation nor its affiliates warrant that this documentation is error-free, nor
are there any other warranties with respect to the documentation except as may be provided in the license agreement.
©2005–2017 Fair Isaac Corporation and Artelys SA. All rights reserved. Permission to use this software and its documentationis governed by the software license agreement between the licensee and Fair Isaac Corporation (or its affiliate). Portions of
the program may contain copyright of various authors and may be licensed under certain third-party licenses identified in thesoftware, documentation, or both.
In no event shall Fair Isaac Corporation or its affiliates be liable to any person for direct, indirect, special, incidental, or
consequential damages, including lost profits, arising out of the use of this software and its documentation, even if Fair Isaac
Corporation or its affiliates have been advised of the possibility of such damage. The rights and allocation of risk between thelicensee and Fair Isaac Corporation (or its affiliates) are governed by the respective identified licenses in the software,
documentation, or both.
Fair Isaac Corporation and its affiliates specifically disclaim any warranties, including, but not limited to, the implied
warranties of merchantability and fitness for a particular purpose. The software and accompanying documentation, if any,
provided hereunder is provided solely to users licensed under the Fair Isaac Software License Agreement. Fair Isaac
Corporation and its affiliates have no obligation to provide maintenance, support, updates, enhancements, or modifications
except as required to licensed users under the Fair Isaac Software License Agreement.
FICO and Fair Isaac are trademarks or registered trademarks of Fair Isaac Corporation in the United States and may be
trademarks or registered trademarks of Fair Isaac Corporation in other countries. Other product and company names herein
may be trademarks of their respective owners.
Xpress Kalis
Deliverable Version: A
Last Revised: 7 July, 2017
Version 12.6

How to Contact the Xpress Team
Information, Sales and Licensing

Product Support

USA, CANADA AND ALL AMERICASEmail: Support@fico.com(Please include ’Xpress’ in the subject line)

Email: XpressSalesUS@fico.com

Telephone:WORLDWIDE
Email: XpressSalesUK@fico.com
Tel: +44 207 940 8718
Fax: +44 870 420 3601
Xpress Optimization, FICO
FICO HouseInternational Square
Starley Way
Birmingham B37 7GN
UK

NORTH AMERICA
Tel (toll free): +1 (877) 4FI-SUPP
Fax: +1 (402) 496-2224
EUROPE, MIDDLE EAST, AFRICA
Tel: +44 (0) 870-420-3777
UK (toll free): 0800-0152-153
South Africa (toll free): 0800-996-153
Fax: +44 (0) 870-420-3778
ASIA-PACIFIC, LATIN AMERICA, CARIBBEAN
Tel: +1 (415) 446-6185
Brazil (toll free): 0800-891-6146

For the latest news and Xpress software and documentation updates, please visit the Xpress website at
http://www.fico.com/xpress or subscribe to our mailing list.

How to Contact Artelys
Artelys SA
Information and Sales: info-kalis@artelys.com
Licensing and Product Support: support-kalis@artelys.com
Tel: +33 1 44 77 89 00
Fax: +33 1 42 96 22 61
12, rue du Quatre Septembre
75002 Paris Cedex
FranceFor the latest news about Kalis, training course programs, and examples, please visit the Artelys website at
http://www.artelys.com.

Contents
1 Introduction
1.1 Xpress Kalis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Note on product versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Software installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Basic concepts of Constraint Programming . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Contents of this document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2
2
2
3

I

5

Working with Xpress Kalis

2 Modeling basics
2.1 A first model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Implementation with Mosel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1.1 General structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1.2 Solving and solution output . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1.3 Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Running the model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2.1 Working from the Mosel command line . . . . . . . . . . . . . . . . . .
2.1.2.2 Using Xpress Workbench . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2.3 Debugging a model . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Data input from file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Data-driven model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Optimization and enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Continuous variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
6
6
7
7
8
8
8
9
10
11
11
12
13
13
15
15
16
17

3 Constraints
3.1 Constraint handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 Naming constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.5 Explicit posting of constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.6 Explicit constraint propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Arithmetic constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 all_different: Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 abs and distance: Frequency assignment . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18
18
19
19
20
20
21
21
22
22
22
24
25
26
27
27

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Informationi

Contents

3.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 element: Sequencing jobs on a single machine . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Model formulation 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.2 Implementation of model 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.4 Alternative formulation using disjunctions . . . . . . . . . . . . . . . . . . . . .
3.5.5 Implementation of model 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 occurrence: Sugar production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 distribute: Personnel planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 implies: Paint production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.1 Formulation of model 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.2 Implementation of model 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.3 Formulation of model 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.4 Implementation of model 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 equiv: Location of income tax offices . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 cycle: Paint production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11 Generic binary constraints: Euler knight tour . . . . . . . . . . . . . . . . . . . . . . . .
3.11.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11.4 Alternative implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11.5 Alternative implementation 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.12 Symmetry breaking: scenes allocation problem . . . . . . . . . . . . . . . . . . . . . . .
3.12.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.12.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.12.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29
30
30
31
34
34
35
37
37
38
39
39
40
40
42
42
43
44
45
45
46
46
46
48
49
50
50
50
51
51
52
52
54
54
56
58
58
59
61

4 Enumeration
4.1 Predefined search strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Interrupting and restarting the search . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Callbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 User-defined enumeration strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1.1 Parallel machine assignment . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1.2 Machines working in series . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 User search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Reversible numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6 Analyzing infeasibility and handling conflicts . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62
62
63
64
64
65
65
65
66
68
69
70
71
72
73

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Informationii

Contents

5 Scheduling75
5.1 Tasks and resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Precedences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.2.4 Alternative formulation without scheduling objects . . . . . . . . . . . . . . . . 78
5.3 Disjunctive scheduling: unary resources . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4 Cumulative scheduling: discrete resources . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.4.4 Alternative formulation without scheduling objects . . . . . . . . . . . . . . . . 84
5.4.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Renewable and non-renewable resources . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.5.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5.4 Alternative formulation without scheduling objects . . . . . . . . . . . . . . . . 90
5.5.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6 Extensions: setup times, resource choice, usage profiles . . . . . . . . . . . . . . . . . . 92
5.6.1 Setup times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.6.1.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.6.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.6.1.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6.2 Alternative resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6.2.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.6.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.6.3 Resource profiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.6.3.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.6.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.6.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.6.4 Resource idle times and preemption of tasks . . . . . . . . . . . . . . . . . . . . 99
5.6.4.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.6.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.6.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.7 Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.7.1 Variable-based enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.7.1.1 Using cp_minimize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.7.1.2 Using cp_schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.7.2 Task-based enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.7.2.1 Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.7.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.7.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.7.2.4 Alternative search strategies . . . . . . . . . . . . . . . . . . . . . . . . 107
5.7.3 Choice of the propagation algorithm . . . . . . . . . . . . . . . . . . . . . . . . 108
6 Hybridization of CP and MP
109
6.1 Linear relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.2 Automatic relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.1 Integer knapsack problem with side constraint . . . . . . . . . . . . . . . . . . . 110

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Informationiii

Contents

6.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3 Configuring automatic relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.1 Configuration choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 User-defined relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Appendix117

A Trouble shooting

118

B Glossary of CP terms

119

Bibliography

121

Index

122

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Informationiv

C HAPTER 1

Introduction
Constraint Programming is an approach to problem solving that has been particularly successful
for dealing with nonlinear constraint relations over discrete variables. In the following wetherefore often use ‘Constraint Programming’ or ‘CP’ synonymously to ‘finite domain Constraint
Programming’.
In the past, CP has been successfully applied to such different problem types as production
scheduling (with or without resource constraints), sequencing and assignment of tasks, workforce
planning and timetabling, frequency assignment, loading and cutting, and also graph coloring.
The strength of CP lies in its use of a high-level semantics for stating the constraints that preserves
the original meaning of the constraint relations (such high-level constraints are referred to as
global constraints). It is not necessary to translate constraints into an arithmetic form—a process
whereby sometimes much of the problem structure is lost. The knowledge about a problem
inherent to the constraints is exploited by the solution algorithms, rendering them more efficient.

1.1

Xpress Kalis
Xpress Kalis, or Kalis for Mosel, provides access to the Artelys Kalis© Constraint Programming
solver from a Mosel module, kalis. Through Xpress Kalis, the Constraint Programming
functionality of Kalis becomes available in the Mosel environment, allowing the user toformulate and solve CP models in the Mosel language. Xpress Kalis combines a finite domain
solver and a solver over continuous (floating point) variables. To aid the formulation ofscheduling problems, the software defines specific aggregate modeling objects representing tasks
and resources that will automatically setup certain (implicit) constraint relations and trigger theuse of built-in search strategies specialized for this type of problem. Standard schedulingproblems may thus be defined and solved simply by setting up the corresponding task andresource objects. Additionally, Xpress Kalis provides automatic linear relaxations of its constraints
to ease the formulation and solving of a wide range of optimization problems.
All data handling facilities of the Mosel environment, including data transfer in memory (using
the Mosel IO drivers) and ODBC access to databases (through the module mmodbc) can be usedwith kalis without any extra effort.
The Mosel language supports typical programming constructs, such as loops, subroutines, etc.,that may be required to implement more complicated algorithms. Mosel can also be used as aplatform for combining different solvers, in particular Xpress Kalis with Xpress Optimizer for joint
CP – LP/MIP problem solving1 . This manual explains the basics on modeling and programmingwith Mosel and, where necessary, also some more advanced features. For a complete
documentation and a more thorough introduction to its use the reader is referred to the Mosel
language reference manual and the Mosel user guide.
1 See the Xpress Whitepaper Multiple models and parallel solving with Mosel

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

1

Introduction

Beyond the functionality readily available from Xpress Kalis the software also provides a uniqueextension mechanism that opens it up to various kinds of additions of new functionality on thelibrary level that become available within the Mosel language through the Mosel Native Interface(see the Mosel NI reference manual and the Mosel NI user guide). Such user-defined extensions
principally relate to the definition of new constraints and branching schemes.

1.1.1

Note on product versions
Most examples in this manual have been developed using the release 2007.1.0 of Xpress Kalis
with the Xpress Release 2007A beta version of Mosel (1.7.9). If they are run with other productversions the output obtained may look different. In particular, improvements to the algorithms in
the CP solver or modifications to the default settings in Xpress Kalis may influence the behaviorof the constraints or the search.

1.2

Software installation
To be able to work with Xpress Kalis, the Xpress Mosel software and Xpress Kalis must be installed
and licensed. Users may find it convenient to install (in addition) the graphical environment
Xpress Workbench for working with CP models, but this is not a prerequisite: Mosel models canbe edited with any text editor and simply be executed from the command line. The examples of
Chapter 6 of this manual can only be executed if Xpress Optimizer is also present and licensed.
Follow the installation instructions provided with the Xpress distribution for installing Mosel andthe required solvers (and Xpress Workbench) on your computer.

1.3

Basic concepts of Constraint Programming
A Constraint Programming (CP) problem is defined by its decision variables with their domains
and constraints over these variables. The problem definition is usually completed by a branchingstrategy (also referred to as enumeration or search strategy).
CP makes active use of the concept of variable domains, that is, the set out of which a decisionvariable takes its values. In finite domain Constraint Programming these are sets or intervals of
integer numbers.
Each constraint in CP comes with its own (set of) solution algorithm(s), typically based on resultsfrom other areas, such as graph theory. Once a constraint has been established it maintains its setof variables in a solved state, i.e., its solution algorithm removes any values that it finds infeasible
from the domains of the variables.
The constraints in a CP problem are linked by a mechanism called constraint propagation:
whenever the domain of a variable is modified this triggers a re-evaluation of all constraints on
this variable which in turn may cause modifications to other variables or further reduction of thedomain of the first variable as shown in the example in Figure 1.1 (the original domains of thevariables are reduced by the addition of two constraints; in the last step the effect of the second
constraint is propagated to the first constraint, triggering its re-evaluation).
A CP problem is built up incrementally by adding constraints and bounds on its variables. The
solving of a CP problem starts with the statement of the first constraint—values that violate theconstraint relation are removed from the domains of the involved variables. Since the effect of a
newly added constraint is propagated immediately to the entire CP problem it is generally notpossible to modify or delete this constraint from the problem later on.
In some cases the combination of constraint solving and the propagation mechanism may besufficient to prove that a problem instance is infeasible, but most of the time it will be necessary

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information2

Introduction

(a)

(b)

(1)

(2)

(3)

x

y

z

[1..10][5..15][1..15]xy[1..10][5..14]x

4*x=y[2..3](4)x[2..3]yy<zy{8,12}(2)[6..15]
y<z

z

(3)

[6..15]{8,12}
4*x=y

z

(1)

y<z

z
[9..15]xyz[1.5,10][5,15][1,15]xy[1.5,10][5,15]x4*x=y[1.5,3.75[

(4)

y

y _
< z

z
[5,15]y _< z[6,15]

z[5,15]

4*x=y
y _
< z
x
y
z
[1.5,3.75[[6,15][6,15]

Figure 1.1: Example of constraint propagation, (a) finite domain (discrete) variables, (b) continuous variables.

to add an enumeration for reducing all variable domains to a single value (consistent
instantiation or feasible solution) or proving that no such solution exists. In addition it is possible
to define an objective function (or cost function) and search for a feasible solution with the best
objective function value (optimal solution).

1.4

Contents of this document
This document gives an introduction to working with Xpress Kalis. Basic notions of Constraint
Programming are explained but it is expected that the reader has some general understanding ofCP techniques. Since Xpress Kalis is a module for Xpress Mosel this document also describesfeatures of the Mosel language where this appears neccessary to the understanding of thepresented examples.
By means of example models we illustrate the use of the new types defined by Xpress Kalis,
namely

Decision variables: finite domain and floating point variables



Constraints: absolute value and distance, all-different, element, generic binary, linear,
maximum and minimum, occurrence, and logical relations

Enumeration: predefined branching schemes and user search strategies



Scheduling: aggregate modeling objects representing tasks and resources

The first chapter deals with the basics of writing CP models with Mosel. It explains the general
structure of CP models and some basics on working with Mosel, including data handling. Thenfollows a series of small problems illustrating the use of the different constraint relation types in
Xpress Kalis. The next chapter introduces in a more systematic way the different possibilities ofdefining enumeration strategies, some of which already appear in the preceding model
examples. The chapter dedicated to the topic of scheduling introduces the modeling objects‘task’ and ‘resource’ that simplify the formulation of scheduling problems. The following chapter
familiarizes the reader with the concept of linear relaxations and shows how to work with them.
Apart from the initial examples, every example is presented as follows:
1. Example description
2. Formulation as a CP model

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

3

Introduction

3. Implementation with Xpress Kalis: code listing and explanations
4. Results
All example models of this document are included with the set of examples that is provided aspart of the Xpress Kalis distribution.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

4

I. Working with Xpress KalisC HAPTER 2

Modeling basics
This chapter shows how to

2.1



start working with Mosel,create and solve a simple CP model with Xpress Kalis,

understand and analyze the output produced by the software,extend the model with data handling,

define an objective function, and

modify the default branching strategy.

A first model
Consider the following problem: we wish to schedule four meetings A, B, C, and D in three timeslots (numbered 1 to 3). Some meetings are attended by the same persons, meaning that they
may not take place at the same time: meeting A cannot be held at the same time as B or D, andmeeting B cannot take the same time slot as C or D.
More formally, we may write down this problem as follows, where planm(m ∈ MEETINGS = {A, B, C, D}) denotes the time slot for meeting m—these are the decisionvariables of our problem.
∀m ∈ MEETINGS : planm ∈ {1, 2, 3}
planA 6= planB
planA 6= planD
planB 6= planC
planB 6= planD

2.1.1

Implementation with Mosel
The following code listing implements and solves the problem described above.
model "Meeting"uses "kalis"declarations
MEETINGS = {’A’,’B’,’C’,’D’}
TIME = 1..3
plan: array(MEETINGS) of cpvar
end-declarations! Set of meetings! Set of time slots! Time slot per meeting

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

6Modeling basics

forall(m in MEETINGS) setdomain(plan(m), TIME)! Respect incompatibilities
plan(’A’) <> plan(’B’)
plan(’A’) <> plan(’D’)
plan(’B’) <> plan(’C’)
plan(’B’) <> plan(’D’)! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(m in MEETINGS)
writeln("Meeting ", m, ": ", getsol(plan(m)))
end-modelThis Mosel model is saved as a text file with the name meeting.mos. Let us now take a closer lookat what we have just written.
2.1.1.1

General structure

Every Mosel program starts with the keyword model, followed by a model name chosen by theuser. The Mosel program is terminated with the keyword end-model.
As Mosel is itself not a solver, we specify that the Kalis constraint solver is to be used with thestatement
uses "kalis"at the begin of the model.
All objects must be declared in a declarations section, unless they are defined unambiguously
through an assignment. For example, i:= 1 defines i as an integer and assigns to it the value 1.
There may be several such declarations sections at different places in a model.
In the present case, we define two sets, and one array:

MEETINGS is a set of strings.



TIME is a so-called range set—i.e., a set of consecutive integers (here: from 1 to 3).

plan is an array of decision variables of type cpvar (finite domain CP variables; a second
decision variable type of Xpress Kalis is cpfloatvar for continuous variables), indexed by theset MEETINGS.

The model then defines the domains of the variables using the Xpress Kalis procedure setdomain.
The decision variables are indeed created at their declaration with a large default domain andsetdomain reduces these domains to the intersection of the default domain with the indicatedvalues. As in the mathematical model, we use a forall loop to enumerate all the indices in theset MEETINGS.
This is followed by the statement of the constraints, in this model we have four disequality
constraints.
2.1.1.2

Solving and solution output

With the function cp_find_next_sol, we call Kalis to solve the problem (find a feasible

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

7

Modeling basics

assignment of values to all decision variables). We test the return value of this function: if nosolution is found it returns false and we stop the model execution at this point (by calling theMosel procedure exit), otherwise we print out the solution.
To solve the problem Xpress Kalis uses its built-in default search strategies. We shall see later how
to modify these strategies.
The solution for a CP variable is obtained with the function getsol. To write several items on asingle line use write instead of writeln for printing the output.
2.1.1.3

Formatting

Indentation, spaces, and empty lines in our model have been added to increase readability. They
are skipped by Mosel.
Line breaks: It is possible to place several statements on a single line, separating them bysemicolons, as such:plan(’A’) <> plan(’B’); plan(’A’) <> plan(’D’)

But since there are no special ‘line end’ or continuation characters, every line of a statement that
continues over several lines must end with an operator (+, >=, etc.) or characters like ‘,’ that makeit obvious that the statement is not terminated.
As shown in the example, single line comments in Mosel are preceded by !. Multiple line
comments start with (! and terminate with !).

2.1.2

Running the model
You may choose among three different methods for running your Mosel models:
1. From the Mosel command line: this method can be used on all platforms for which Mosel isavailable. It is especially useful if you wish to execute a (batch) sequence of model runs—for
instance, with different parameter settings. The full Mosel functionality, including its
debugger, is accessible in this run mode.
2. Within the graphical environment Xpress Workbench: available to Windows users.
Workbench is a complete modeling and optimization development environment with abuilt-in text editor for working with Mosel models and a number of displays that help
analyze models and solution algorithms in the development phase. Models can be modified
and re-run interactively.
3. From within an application program: Mosel models may be executed and accessed fromapplication programs (C/C++, Java, VBA, C#). This functionality is typically used for the
deployment of Mosel models, integrating them into a company’s information system.
In this manual we shall use the first two methods for running the models we develop. For further
detail on embedding models into application programs the user is referred to the Mosel user
guide.
2.1.2.1

Working from the Mosel command line

When you have entered the complete model into the file meeting.mos, we can proceed to thesolution to our problem. We start Mosel at the command prompt by typing the following
commandmosel execute meeting.mos

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information8Modeling basics

and we will see output something like that below.
Meeting A: 1
Meeting B: 2
Meeting C: 1
Meeting D: 3

The Mosel command for executing the model can be abbreviated tomosel exec meetingor simply
mosel meeting

The model execution performed by the command execute comprises three stages:
1. Compiling meeting.mos
2. Loading the compiled model
3. Running the model we have just loaded.
Instead of using execute, you may choose to explicitly generate the compiled model filechess.bim
mosel compile meeting.mosfollowed bymosel run meeting.bim

to load and run the compiled model.
2.1.2.2

Using Xpress Workbench

To execute the model file meeting.mos with Workbench you need to carry out the following steps.
Start up Workbench: if you have followed the standard installation procedure for Xpress
Workbench, start the program by double clicking the icon on the desktop or selecting Start
 Programs  Xpress  Xpress Workbench. Otherwise, you may also start up Workbenchby double clicking a model file (file with extension .mos).

Open the model file by choosing File  Open. The model source is then displayed in thecentral window (the Workbench Editor).

Click the green Run button
model.

or, alternatively, choose menu entry Run for the desired

The Build pane at the bottom of the workspace displays the model execution status messages
from Mosel and any outpu generated by it. If syntax errors are found in the model they aredisplayed here, with details of the line and character position where the error was detected and a
description of the problem, if available.
Workbench makes all information about the model available for inspection through the
Debugger pane in the right hand window if the model is run in debug mode (green bug icon).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

9Modeling basics

Figure 2.1: Workbench workspace after opening a model

Figure 2.2: Workbench workspace after model execution in debug mode

2.1.2.3

Debugging a model

A first step for debugging a model certainly is to add additional output. In our model, we could,
for instance, print out the definition of the decision variables by adding the line
writeln(plan)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

10Modeling basics

after the definition of the variables’ domains, or even print out the complete problem definition
with the procedure cp_show_prob. To obtain a more easily readable output for debugging theuser may give names to the decision variables of his problem. For example:
forall(m in MEETINGS) setname(plan(m), "Meeting "+m)

Notice that we have used the ’+’ sign to concatenate strings.
Calling the procedure cp_show_stats will display summary statistics of the CP solving.
To obtain detailed information about run-time errors with the command line version models
need to be compiled with the flag -g, for example,
mosel exec -g meeting

For using the Mosel debugger (please see the Mosel language reference manual for further
detail) the compilation flag -G needs to be used instead.
Workbench by default compiles models in standard mode, debug+trace information (option -G) is
automatically enabled when launching a debugging run (the debugger is started by clicking the’debug’ button).

2.2

Data input from file
We now extend the previous example in order to use it with different data sets. If we wish to run
a model with different data sets, it would be impractical and error-prone having to edit themodel file with every change of the data set. Instead, we are now going to see how to read datafrom a text file.
This is a description of the problem we want to solve (example taken from Section 14.4 of thebook ‘Applications of optimization with Xpress-MP’).
A technical university needs to schedule the exams at the end of the term for a course withseveral optional modules. Every exam lasts two hours. Two days have been reserved for the exams
with the following time periods: 8:00–10:00, 10:15–12:15, 14:00–16:00, and 16:15–18:15, resulting
in a total of eight time periods. For every exam the set of incompatible exams that may not takeplace at the same time because they have to be taken by the same students is shown in Table 2.1.
Table 2.1: Incompatibilities between different exams
DA
NA
C++
SE
PM
J
GMA
LP
MP
S
DSE

2.2.1

DA

NA

C++

SE

PM

J

GMA

LP

MP

S

DSE

–
X
–
–
X
–
X
–
–
X
X

X
–
–
–
X
–
X
–
–
X
X

–
–
–
X
X
X
X
–
X
X
X

–
–
X
–
X
X
X
–
–
X
X

X
X
X
X
–
X
X
X
X
X
X

–
–
X
X
X
–
X
–
X
X
X

X
X
X
X
X
X
–
X
X
X
X

–
–
–
–
X
–
X
–
–
X
X

–
–
X
–
X
X
X
–
–
X
X

X
X
X
X
X
X
X
X
X
–
X

X
X
X
X
X
X
X
X
X
X
–

Model formulation
The CP model has the same structure as the previous one, with the difference that we now
introduce a data array INCOMP indicating incompatible pairs of exams and define the disequality

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

11Modeling basics

constraints in a loop instead of writing them out one by one.
∀e ∈ EXAM : plane ∈ {1, . . . , 8}∀d, e ∈ EXAM, INCOMPde = 1 : pland 6= plane

2.2.2

Implementation
The Mosel model now looks as follows.
model "I-4 Scheduling exams (CP)"uses "kalis"declarations
EXAM = 1..11! Set of exams
TIME = 1..8
! Set of time slots
INCOMP: array(EXAM,EXAM) of integer ! Incompatibility between exams
EXAMNAME: array(EXAM) of string
plan: array(EXAM) of cpvar
end-declarations! Time slot for exam

EXAMNAME:: (1..11)["DA","NA","C++","SE","PM","J","GMA","LP","MP","S","DSE"]
initializations from ’Data/i4exam.dat’
INCOMP
end-initializations
forall(e in EXAM) setdomain(plan(e), TIME)! Respect incompatibilities
forall(d,e in EXAM | d<e and INCOMP(d,e)=1)plan(d) <> plan(e)! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(t in TIME) do
write("Slot ", t, ": ")forall(e in EXAM)
if (getsol(plan(e))=t) then write(EXAMNAME(e)," "); end-if
writeln
end-doend-model

The values of the array INCOMP are read in from the file i4exam.dat in an initializations
block. In the definition of the disequality constraints we check the value of the corresponding
array entry—conditions on the indices for loops, sums, and other aggregate operators aremarked by a vertical bar.
The data file has the following contents.
INCOMP: [0 1 0 0 1 0 1 0 0 1 1
1 0 0 0 1 0 1 0 0 1 1
0 0 0 1 1 1 1 0 1 1 1
0 0 1 0 1 1 1 0 0 1 1
1 1 1 1 0 1 1 1 1 1 1
0 0 1 1 1 0 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1
0 0 0 0 1 0 1 0 0 1 1
0 0 1 0 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 0]

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

12

Modeling basics

2.2.3

Results
The model prints out the following results. Only the first seven time slots are used for schedulingexams.
Slot 1: DA C++ LP
Slot 2: NA SE MP
Slot 3: PM
Slot 4: GMA
Slot 5: S
Slot 6: DSE
Slot 7: J
Slot 8:2.2.4

Data-driven model
In the model shown above, we have read the incompatibility data from a file but part of the data(namely the index set EXAM and the number of time slots available) are still hard-coded in themodel. To obtain a fully flexible model that can be run with arbitrary data sets we need to move
all data definitions from the model to the data file.
The new data file i4exam2.dat not only defines the data entries, it also defines the index tuples
for the array INCOMP. Every data entry is preceded by its index tuple (in brackets). There is noneed to write out explicitly the contents of the set EXAM—Mosel will automatically populate thisset with the index values read in for the array INCOMP. In addition, the data file now contains avalue for the number of time periods NT.
INCOMP: [("DA" "NA") 1 ("DA" "PM") 1 ("DA" "GMA") 1 ("DA" "S") 1 ("DA" "DSE") 1("NA" "DA") 1 ("NA" "PM") 1 ("NA" "GMA") 1 ("NA" "S") 1 ("NA" "DSE") 1("C++" "SE") 1 ("C++" "PM") 1 ("C++" "J") 1 ("C++" "GMA") 1("C++" "MP") 1 ("C++" "S") 1 ("C++" "DSE") 1("SE" "C++") 1 ("SE" "PM") 1 ("SE" "J") 1 ("SE" "GMA") 1 ("SE" "S") 1("SE" "DSE") 1("PM" "DA") 1 ("PM" "NA") 1 ("PM" "C++") 1 ("PM" "SE") 1 ("PM" "J") 1("PM" "GMA") 1 ("PM" "LP") 1 ("PM" "MP") 1 ("PM" "S") 1 ("PM" "DSE") 1("J" "C++") 1 ("J" "SE") 1 ("J" "PM") 1 ("J" "GMA") 1 ("J" "MP") 1("J" "S") 1 ("J" "DSE") 1("GMA" "DA") 1 ("GMA" "NA") 1 ("GMA" "C++") 1 ("GMA" "SE") 1("GMA" "PM") 1 ("GMA" "J") 1 ("GMA" "LP") 1 ("GMA" "MP") 1("GMA" "S") 1 ("GMA" "DSE") 1("LP" "PM") 1 ("LP" "GMA") 1 ("LP" "S") 1 ("LP" "DSE") 1("MP" "C++") 1 ("MP" "PM") 1 ("MP" "J") 1 ("MP" "GMA") 1 ("MP" "S") 1("MP" "DSE") 1("S" "DA") 1 ("S" "NA") 1 ("S" "C++") 1 ("S" "SE") 1 ("S" "PM") 1("S" "J") 1 ("S" "GMA") 1 ("S" "LP") 1 ("S" "MP") 1 ("S" "DSE") 1("DSE" "DA") 1 ("DSE" "NA") 1 ("DSE" "C++") 1 ("DSE" "SE") 1("DSE" "PM") 1 ("DSE" "J") 1 ("DSE" "GMA") 1 ("DSE" "LP") 1("DSE" "MP") 1 ("DSE" "S") 1 ]NT: 8

Our model also needs to undergo a few changes: the sets EXAM and TIME are now declared bystating their types, which turns them into dynamic sets (as opposed to their previous constantdefinition by stating their values). As a consequence, the array of decision variables plan isdeclared before the indexing set EXAM is known and Mosel creates this array as a dynamic array,meaning that the declaration results in an empty array and its elements need to be createdexplicitly (using the Mosel procedure create) once the indices are known. Before creating thevariables, we modify the default bounds of Xpress Kalis to the values corresponding to the set
TIME, thus replacing the call to setdomain.
The array INCOMP is explicitly declared as a dynamic array. The initializations block will assign
values to just those entries that are listed in the data file (with the previous, constant declaration,

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

13

Modeling basics

all entries were defined) and the explicit dynamic marker means that Mosel’s automatic
finalization is not applied—it would try to transform the array into a static array. This makes it
possible to reformulate the condition on the loop defining the disequality constraints: we now
simply test for the existence of an entry instead of comparing all data values. With larger data
sets, using the keyword exists may greatly reduce the execution time of loops involving sparsearrays (multidimensional data arrays with few entries different from 0).
model "I-4 Scheduling exams (CP) - 2"
uses "kalis"declarations
NT: integer! Number of time slots
EXAM: set of string! Set of exams
TIME: set of integer! Set of time slots
INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams
plan: array(EXAM) of cpvar
end-declarations! Time slot for exam

initializations from ’Data/i4exam2.dat’
INCOMP NT
end-initializations
TIME:= 1..NT
setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)
forall(e in EXAM) create(plan(e))! Respect incompatibilities
forall(d,e in EXAM | exists(INCOMP(d,e)) and d<e)plan(d) <> plan(e)! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(t in TIME) do
write("Slot ", t, ": ")forall(e in EXAM)
if (getsol(plan(e))=t) then write(e," "); end-if
writeln
end-doend-model

Running this fully data-driven model produces the same solution as the previous version.
An alternative to the explicit creation of the decision variables plan is to move their declaration
after the initialization of the data as shown in the code extract below. In this case, it is importantto finalize the indexing set EXAM, which turns it into a constant set with its current contents
and allows Mosel to create any subsequently declared arrays indexed by this set as static arrays.
declarations
NT: integer! Number of time slots
EXAM: set of string! Set of exams
TIME: set of integer! Set of time slots
INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams
end-declarations
initializations from ’Data/i4exam2.dat’
INCOMP NT
end-initializations
finalize(EXAM)
TIME:= 1..NT

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

14

Modeling basics

setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)declarations
plan: array(EXAM) of cpvar! Time slot for exam
end-declarations

2.3

Optimization and enumeration

2.3.1

Optimization
Since running our model i4exam_ka.mos in Section 2.2.2 has produced a solution to the problem
that does not use all time slots one might wonder which is the minimum number of time slotsthat are required for this problem. This question leads us to the formulation of an optimization
problem.
We introduce a new decision variable numslot over the same value range as the plani variables
and add the constraints that this variable is greater or equal to every plani variable. A simplified
formulation is to say that the variable numslot equals the maximum value of all plani variables.
The objective then is to minimize the value of numslot, which results in the following model.
model "I-4 Scheduling exams (CP) - 3"
uses "kalis"declarations
NT: integer! Number of time slots
EXAM: set of string! Set of exams
TIME: set of integer! Set of time slots
INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams
plan: array(EXAM) of cpvar
numslot: cpvar
end-declarations! Time slot for exam
! Number of time slots used

initializations from ’Data/i4exam2.dat’
INCOMP NT
end-initializations
finalize(EXAM)
TIME:= 1..NT
setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)
forall(e in EXAM) create(plan(e))! Respect incompatibilities
forall(d,e in EXAM | exists(INCOMP(d,e)) and d<e)plan(d) <> plan(e)! Calculate number of time slots usednumslot = maximum(plan)! Solve the problem
if not(cp_minimize(numslot)) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(t in TIME) do
write("Slot ", t, ": ")forall(e in EXAM)
if (getsol(plan(e))=t) then write(e," "); end-if
writeln
end-doend-model

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

15

Modeling basics

Instead of cp_find_next_sol we now use cp_minimize with the objective function variablenumslot as function argument.
This program also generates a solution using seven time slots, thus proving that this is the least
number of slots required to produce a feasible schedule.

2.3.2

Enumeration
When comparing the problem statistics obtained by adding a call to cp_show_stats to the end of
the different versions of our model, we can see that switching from finding a feasible solution to
optimization considerably increases the number of nodes explored by the CP solver.
So far we have simply relied on the default enumeration strategies of Xpress Kalis. We shall now
try to see whether we can reduce the number of nodes explored and hence shorten the timespent by the search for proving optimality.
The default strategy of Kalis for enumerating finite domain variables corresponds to adding thestatement
cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX))

before the start of the search. assign_var denotes the branching scheme (‘a branch is formed byassigning the next chosen value to the branching variable’), KALIS_SMALLEST_DOMAIN is thevariable selection strategy (‘choose the variable with the smallest number of values remaining in
its domain’), and KALIS_MIN_TO_MAX the value selection strategy (‘from smallest to largest value’).
Since we are minimizing the number of time slots, enumeration starting with the smallest value
seems to be a good idea. We therefore keep the default value selection criterion. However, we
may try to change the variable selection heuristic: replacing KALIS_SMALLEST_DOMAIN by
KALIS_MAX_DEGREE results in a reduction of the tree size and search time to less than half of its
default size.
Here follows once more the complete model.
model "I-4 Scheduling exams (CP) - 4"
uses "kalis"declarations
NT: integer! Number of time slots
EXAM: set of string! Set of exams
TIME: set of integer! Set of time slots
INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams
plan: array(EXAM) of cpvar
numslot: cpvar
end-declarations! Time slot for exam
! Number of time slots used

initializations from ’Data/i4exam2.dat’
INCOMP NT
end-initializations
finalize(EXAM)
TIME:= 1..NT
setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)
forall(e in EXAM) create(plan(e))! Respect incompatibilities
forall(d,e in EXAM | exists(INCOMP(d,e)) and d<e)plan(d) <> plan(e)! Calculate number of time slots usednumslot = maximum(plan)! Setting parameters of the enumeration

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

16Modeling basics

cp_set_branching(assign_var(KALIS_MAX_DEGREE, KALIS_MIN_TO_MAX))! Solve the problem
if not(cp_minimize(numslot)) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(t in TIME) do
write("Slot ", t, ": ")forall(e in EXAM)
if (getsol(plan(e))=t) then write(e," "); end-if
writeln
end-docp_show_stats
end-model

NB: In the model versions without optimization we may try to obtain a more evenly distributedschedule by choosing values randomly, that is, by using the value selection criterion
KALIS_RANDOM_VALUE instead of KALIS_MIN_TO_MAX.
Further detail on the definition of branching strategies is given in Chapter 4.

2.4

Continuous variables
All through this chapter we have worked with the decision variable type cpvar (discretevariables). A second variable type in Xpress Kalis are continuous variables (type cpfloatvar). Suchvariables are used in a similar way to what we have seen above for discrete variables, for example:
setparam("KALIS_DEFAULT_CONTINUOUS_LB", 0)
setparam("KALIS_DEFAULT_CONTINUOUS_UB", 10)
declarations
x,y: cpfloatvar
end-declarationsx >= y! Define a constraint! Retrieve information about continuous variables
writeln(getname(x), ":", getsol(x))
writeln(getlb(y), " ", getub(y))

A few differences in the use of the two decision variable types exist:
Constraints involving cpfloatvar cannot be strict inequalities (that is, only the operators <=,>=, and = may be used).



Most global constraints (see Chapter 3) only apply to cpvar; also applicable to cpfloatvar
are maximum and minimum relations.



Search strategies enumerating the values in a variable’s domain can only be used with
cpvar; with cpfloatvar domain splitting must be used (see Chapter 4).

Access functions for enumerating domain values such getnext are not applicable tocpfloatvar.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

17

C HAPTER 3

Constraints
This chapter contains a collection of examples demonstrating the use of Xpress Kalis for solving
different types of (optimization) problems. The first section shows different ways of defining andposting constraints for simple linear constraints. The following sections each introduce a new
constraint type. Since most examples use a combination of different constraints, the following list
may help in finding examples of the use of a certain constraint type quickly.

3.1



arithmetic: linear disequality: 2.1 (meeting.mos), 2.2 (i4exam*.mos), 3.7 (persplan.mos);linear equality/inequality: 3.5 (b4seq*_ka.mos), 3.6 (i1assign_ka.mos), 3.8(b5paint*_ka.mos), 3.9 (j5tax_ka.mos), 4.4 (i1assign_ka.mos), 5.2 (b1stadium_ka.mos);nonlinear: 3.2



all_different: 3.3 (sudoku_ka.mos), 3.5 (b4seq_ka.mos), 3.8 (b5paint*_ka.mos), 3.4(freqasgn.mos), 3.7 (persplan.mos), 3.11 (eulerkn*.mos), 4.4 (i1assign_ka.mos)abs / distance: 3.4 (freqasgn.mos)

cumulative: 5.4 (d4backup2_ka.mos)cycle: 3.10 (b5paint3_ka.mos)disjunctive: 3.5 (b4seq2_ka.mos)element: 3.5 (b4seq_ka.mos), 3.6 (a4sugar_ka.mos), 3.9 (j5tax_ka.mos),
3.8 (b5paint_ka.mos), 4.4 (i1assign_ka.mos), 2D: 3.8 (b5paint2_ka.mos)

distribute / occurrence: 3.6 (a4sugar_ka.mos), 3.7 (persplan.mos),
3.9 (j5tax_ka.mos), 3.12 (scenesalloc.mos)maximum / minimum: 2.3 (i4exam3.mos, i4exam4.mos), 3.5 (b4seq2_ka.mos),
3.4 (freqasgn.mos), 4.4 (i1assign_ka.mos), 3.12 (scenesalloc.mos)

implies / equiv: 3.8 (b5paint_ka.mos), 3.7 (persplan.mos), 3.9 (j5tax_ka.mos),
3.11 (eulerkn2.mos), 3.12 (scenesalloc.mos)

generic binary: 3.11 (eulerkn.mos)

Constraint handlingIn this section we shall work once more with the introductory problem of scheduling meetingsfrom Section 2.1. This model only contains simple arithmetic constraints over discrete variables.
However, all that is said here equally applies to all other constraint types of Xpress Kalis, including
constraint relations over continuous decision variables (that is, variables of the type cpfloatvar).
We now wish to state a few more constraints for this problem.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

18

Constraints

1. Meeting B must take place before day 3.
2. Meeting D cannot take place on day 2.
3. Meeting A must be scheduled on day 1.

3.1.1

Model formulation
The three additional constraints translate into simple (unary) linear constraints. We complete ourmodel as follows:∀m ∈ MEETINGS : planm ∈ {1, 2, 3}
planB ≤ 2
planD 6= 2
planA = 1
planA 6= planB
planA 6= planD
planB 6= planC
planB 6= planD

3.1.2

Implementation
The Mosel implementation of the new constraints is quite straightforward.
model "Meeting (2)"uses "kalis"declarations
MEETINGS = {’A’,’B’,’C’,’D’}
TIME = 1..3
plan: array(MEETINGS) of cpvar
end-declarations! Set of meetings! Set of time slots! Time slot per meeting

forall(m in MEETINGS) do
setdomain(plan(m), TIME)
setname(plan(m), "plan"+m)
end-dowriteln("Original domains: ", plan)
plan(’B’) <= 2plan(’D’) <> 2plan(’A’) = 1
writeln("With constraints: ", plan)! Meeting B before day 3! Meeting D not on day 2! Meeting A on day 1! Respect incompatibilities
plan(’A’) <> plan(’B’)
plan(’A’) <> plan(’D’)
plan(’B’) <> plan(’C’)
plan(’B’) <> plan(’D’)! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
forall(m in MEETINGS)
writeln("Meeting ", m, ": ", getsol(plan(m)))
end-model

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

19

Constraints

3.1.3

Results
As the reader may have noticed, we have added printout of the variables planm at several placesin the model. The output generated by the execution of this model therefore is the following.
Original domains: [planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
With constraints: [planA[1],planB[1..2],planC[1..3],planD[1,3]]
Meeting A: 1
Meeting B: 2
Meeting C: 1
Meeting D: 3

As can be seen from this output, immediately after stating the constraints, the domains of theconcerned variables have been reduced. The constraints are immediately and automaticallyposted to the solver and their effects are propagated to the whole problem.

3.1.4

Naming constraints
Sometimes it may be necessary to access constraints later on, after their definition, in particular ifthey are to become part of logic relations or if they are to be branched on (typically the case for
disjunctive constraints). To this aim Xpress Kalis defines a new type, cpctr, that can be used todeclare constraints giving them a name that can used after their definition. We define constraints
by assigning to them a constraint relation.
Naming constraints has the secondary effect that the constraints are not automatically posted tothe solver. This needs to be done by writing the name of a constraint as a statement on its own(after its definition) as shown in the following model.
model "Meeting (3)"uses "kalis"declarations
MEETINGS = {’A’,’B’,’C’,’D’}
TIME = 1..3
plan: array(MEETINGS) of cpvar
Ctr: array(range) of cpctr
end-declarations! Set of meetings! Set of time slots! Time slot per meeting

forall(m in MEETINGS) do
setdomain(plan(m), TIME)
setname(plan(m), "plan"+m)
end-dowriteln("Original domains: ", plan)Ctr(1):= plan(’B’) <= 2
! Meeting B before day 3
Ctr(2):= plan(’D’) <> 2
! Meeting D not on day 2
Ctr(3):= plan(’A’) = 1! Meeting A on day 1
writeln("After definition of constraints:\n ", plan)
forall(i in 1..3) Ctr(i)writeln("After posting of constraints:\n ", plan)! Respect incompatibilities
plan(’A’) <> plan(’B’)
plan(’A’) <> plan(’D’)
plan(’B’) <> plan(’C’)
plan(’B’) <> plan(’D’)! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-ifFair Isaac Corporation and Artelys SA Confidential and Proprietary Information

20

Constraints! Solution printing
forall(m in MEETINGS) writeln("Meeting ", m, ": ", getsol(plan(m)))
end-model

From the output produced by this model, we can see that the mere definition of named
constraints does not have any effect on the domains of the variables (the constraints are definedin Mosel but not yet sent to the Kalis solver). Only after stating the names of the constraints (thatis, sending them to the solver) we obtain the same domain reductions as with the previous
version of the model.
Original domains: [planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
After definition of constraints:[planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
After posting of constraints:[planA[1],planB[1..2],planC[1..3],planD[1,3]]
Meeting A: 1
Meeting B: 2
Meeting C: 1
Meeting D: 3

3.1.5

Explicit posting of constraints
In all previous examples, we have silently assumed that posting the constraints does not lead to a
failure (infeasibility detected by the solver). In practice, this may not always be a reasonableassumption. Xpress Kalis therefore defines the function cp_post that explicitly posts a constraint
to the solver and returns the status of the constraint system after its addition (true for feasible
and false for infeasible). This functionality may be of special interest for dealing withover-constrained problems to stop the addition of constraints once an infeasibility has been
detected and to report back to the user which constraint has made the problem infeasible.
To use the explicit posting with cp_post, in the previous model we replace the line
forall(i in 1..3) Ctr(i)with the following code.
forall(i in 1..3)
if not cp_post(Ctr(i)) thenwriteln("Constraint ", i, " makes problem infeasible")exit(1)
end-if

The return value of the every constraint posting is checked and the program is stopped if theaddition of a constraint leads to an infeasibility.
The output produced by this model version is exactly the same as what we have seen in theprevious section.

3.1.6

Explicit constraint propagation
The behavior of constraints can also be influenced in a different way. If we turn automatedconstraint propagation off,
setparam("KALIS_AUTO_PROPAGATE", false)then constraints posted to the solver are not propagated. In this case, constraint propagation will
only be launched by a call to cp_propagate or by starting the enumeration (subroutines
cp_find_next_sol, cp_minimize, etc.).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

21

Constraints

3.2

Arithmetic constraints
In the previous sections we have already seen several examples of linear constraints over finite
domain variables. Linear constraints may be regarded as a special case of arithmetic constraints,
that is, equations or inequality relations involving expressions over decision variables formed withthe operators +, -, /, *, ˆ, sum, prod and arithmetic functions like abs or ln. For a complete list ofarithmetic functions supported by the solver the reader is refered to the Xpress Kalis reference
manual.
Arithmetic constraints in Xpress Kalis may be defined over finite domain variables (type cpvar),
continuous variables (type cpfloatvar), or mixtures of both. Notice, however, that arithmetic
constraints involving continuous variables cannot be defined as strict inequalities, that means,
only the relational operators >=, <=, and = may be used.
Here are a few examples of (nonlinear) arithmetic constraints that may be defined with Xpress
Kalis.
model "Nonlinear constraints"
uses "kalis"
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", 5)
setparam("KALIS_DEFAULT_CONTINUOUS_LB", -10)
setparam("KALIS_DEFAULT_CONTINUOUS_UB", 10)
declarations
a,b,c: cpvar
x,y,z: cpfloatvar
end-declarations
x = ln(y)y = abs(z)x*y <= z^2z = -a/b
a*b*c^3 >= 150
while (cp_find_next_sol)
writeln("a:", getsol(a), ", b:", getsol(b), ", c:", getsol(c),", x:", getsol(x), ", y:", getsol(y), ", z:", getsol(z))
end-model

3.3 all_different: Sudoku
Sudoku puzzles, originating from Japan, have recently made their appearance in many westernnewspapers. The idea of these puzzles is to complete a given, partially filled 9 × 9 board with thenumbers 1 to 9 in such a way that no line, column, or 3 × 3 subsquare contains a number morethan once. The tables 3.1 and 3.2 show two instances of such puzzles. Whilst sometimes tricky tosolve for a human, these puzzles lend themselves to solving by a CP approach.

3.3.1

Model formulation
As in the examples, we denote the columns of the board by the set XS = {A, B, . . . , I} and the rows
by YS = {1, 2, . . . , 9}. For every x in XS and y in YS we define a decision variable vxy taking as its
value the number at the position (x, y).
The only constraints in this problem are(1) all numbers in a row must be different,(2) all numbers in a column must be different,

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

22

Constraints

Table 3.1: Sudoku (‘The Times’, 26 January, 2005)
A

B

C

D

1
6

2
3

E

F

4

3

5

8

5

1

6

9

7

4

3
1

3

2

7
8

7

5

9

9
4

4

4

2
5

3

I

6

7

8
9

H

7

5

4

G

5

6

Table 3.2: Sudoku (‘The Guardian’, 29 July, 2005)
A
1

C

8
9

F

G

H

I

3
4

2

7

6

1

5

3

5

7

E

5

4

6

D

8

2
3

B

9

6

4
7

2
4

3
1

9

8

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

23

Constraints(3) all numbers in a 3 × 3 subsquare must be different.
These constraints can be stated with Xpress Kalis’s all_different relation. This constraint ensuresthat all variables in the relation take different values.
∀x ∈ XS, y ∈ YS : vxy ∈ {1, . . . , 9}∀x ∈ XS : all-different(vx1 , . . . , vx9 )∀y ∈ YS : all-different(vAy , . . . , vIy )all-different(vA1 , . . . , vC3 )all-different(vA4 , . . . , vC6 )all-different(vA7 , . . . , vC9 )all-different(vD1 , . . . , vF3 )all-different(vD4 , . . . , vF6 )all-different(vD7 , . . . , vF9 )all-different(vG1 , . . . , vI3 )all-different(vG4 , . . . , vI6 )all-different(vG7 , . . . , vI9 )In addition, certain variables vxy are fixed to the given values.

3.3.2

Implementation
The Mosel implementation for the Sudoku puzzle in Table 3.2 looks as follows.
model "sudoku (CP)"uses "kalis"forward procedure print_solution(numsol: integer)
setparam("kalis_default_lb", 1)
setparam("kalis_default_ub", 9)! Default variable bounds

declarations
XS = {’A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’}! Columns
YS = 1..9! Rowsv: array(XS,YS) of cpvar! Number assigned to cell (x,y)
end-declarations! Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudokuv(’A’,1)=8; v(’F’,1)=3v(’B’,2)=5; v(’G’,2)=4v(’A’,3)=2; v(’E’,3)=7; v(’H’,3)=6v(’D’,4)=1; v(’I’,4)=5v(’C’,5)=3; v(’G’,5)=9v(’A’,6)=6; v(’F’,6)=4v(’B’,7)=7; v(’E’,7)=2; v(’I’,7)=3v(’C’,8)=4; v(’H’,8)=1v(’D’,9)=9; v(’I’,9)=8! All-different values in rows
forall(y in YS) all_different(union(x in XS) {v(x,y)})! All-different values in columns
forall(x in XS) all_different(union(y in YS) {v(x,y)})! All-different values in 3x3 squares
forall(s in {{’A’,’B’,’C’},{’D’,’E’,’F’},{’G’,’H’,’I’}}, i in 0..2)
all_different(union(x in s, y in {1+3*i,2+3*i,3+3*i}) {v(x,y)})Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

24

Constraints! Solve the problem
solct:= 0
while (cp_find_next_sol) do
solct+=1
print_solution(solct)
end-dowriteln("Number of solutions: ", solct)
writeln("Time spent in enumeration: ",getparam("KALIS_COMPUTATION_TIME"), "sec")
writeln("Number of nodes: ", getparam("KALIS_NODES"))!****************************************************************! Solution printing
procedure print_solution(numsol: integer)
writeln(getparam("KALIS_COMPUTATION_TIME"), "sec: Solution ", numsol)
writeln("
A B C
D E F
G H I")
forall(y in YS) do
write(y, ": ")forall(x in XS)
write(getsol(v(x,y)), if(x in {’C’,’F’}, " | ", " "))writeln
if y mod 3 = 0 thenwriteln("---------------------")
end-ifend-doend-procedure
end-model!****************************************************************In this model, the call to cp_find_next_sol is embedded in a while loop to search all feasible
solutions. At every loop execution the procedure print_solution is called to print out thesolution found nicely formatted. Subroutines in Mosel may have declarations blocks for local
declarations and they may take any number of arguments. Since, in our model, the call to theprocedure occurs before its definition, we need to declare it before the first call using the
keyword forward.
For selecting the information that is to be printed by the subroutine we use two different
versions of Mosel’s if statement: the inline if and if-then that includes a block of statements.
At the end of the model run we retrieve from the solver the run time measurement (parameter
KALIS_COMPUTATION_TIME) and the number of nodes explored by the search (parameter
KALIS_NODES).
To obtain a complete list of parameters defined by Xpress Kalis type the command
mosel exam -p kalis(for a listing of the complete functionality of Xpress Kalis leave out the flag -p).

3.3.3

Results
The model shown above generates the following output; this puzzle has only one solution, as is
usually the case for Sudoku puzzles.
0.16sec: Solution 1
A B C
D E F
G H I
1: 8 6 9 | 2 4 3 | 1 5 7
2: 3 5 7 | 6 1 9 | 4 8 2
3: 2 4 1 | 8 7 5 | 3 6 9--------------------4: 4 9 8 | 1 3 2 | 6 7 5Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

25

Constraints

5: 7 1 3 | 5 8 6 | 9 2 4
6: 6 2 5 | 7 9 4 | 8 3 1--------------------7: 1 7 6 | 4 2 8 | 5 9 3
8: 9 8 4 | 3 5 7 | 2 1 6
9: 5 3 2 | 9 6 1 | 7 4 8--------------------Number of solutions: 1
Time spent in enumeration: 0.41sec
Number of nodes: 2712

The all_different relation takes an optional second argument that allows the user to specify the
propagation algorithm to be used for evaluating the constraint. If we change from the default
setting (KALIS_FORWARD_CHECKING) to the more aggressive strategy KALIS_GEN_ARC_CONSISTENCY by
adding this choice as the second argument, for example,
forall(y in YS)
all_different(union(x in XS) {v(x,y)}, KALIS_GEN_ARC_CONSISTENCY)

we observe that the number of nodes is reduced to a single node—the problem is solved bysimply posting the constraints. Whereas the time spent in the search is down to zero, theconstraint posting now takes 4-5 times longer (still just a fraction of a second) due to the larger
computational overhead of the generalized arc consistency algorithm. Allover, the time forproblem definition and solving is reduced to less than a tenth of the previous time.
As a general rule, the generalized arc consistency algorithm achieves stronger pruning (i.e., itremoves more values from the domains of the variables). However, due to the increase incomputation time its use is not always justified. The reader is therefore encouraged to try bothalgorithm settings in his models.

3.4 abs and distance: Frequency assignment
The area of telecommunications, and in particular mobile telecommunications, gives rise to manydifferent variants of frequency assignment problems.
We are given a network of cells (nodes) with requirements of discrete frequency bands. Each cell
has a given demand for a number of frequencies (bands). Figure 3.1 shows the structure of the
network. Nodes linked by an edge are considered as neighbors. They must not be assigned thesame frequencies to avoid interference. Furthermore, if a cell uses several frequencies they mustall be different by at least 2. The objective is to minimize the total number of frequencies used in
the network.
6

1
3
4

9
10

2

8
5

7
Figure 3.1: Telecommunications network

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

26

Constraints

Table 3.3 lists the number of frequency demands for every cell.
Table 3.3: Frequency demands at nodes

3.4.1

Cell

1

2

3

4

5

6

7

8

9

10

Demand

4

5

2

3

2

4

3

4

3

2

Model formulation
Let NODES be the set of all nodes in the network and DEMn the demand of frequencies at noden ∈ NODES. The network is given as a set of edges LINKS. Furthermore, let
DEMANDS = {1, 2, . . . , NUMDEM} be the set of frequencies, numbered consecutively across all
nodes where the upper bound NUMDEM is given by the total number of demands. The auxiliary
array INDEXn indicates the starting index in DEMANDS for node n.
For representing the frequency assigned to every demand d ∈ DEMANDS we introduce thevariables used that take their values from the set {1, 2, . . . , NUMDEM}.
The two sets of constraints (different frequencies assigned to neighboring nodes and minimum
distance between frequencies within a node) can then be modeled as follows.

INDEXn[+DEMn −1
INDEXm[+DEMm −1∀(n, m) ∈ LINKS : all-different used ∪
used 
d=INDEXn

d=INDEXm∀n ∈ NODES, ∀c < d ∈ INDEXn , . . . , INDEXn + DEMn − 1 : |usec − used | ≥ 2
The objective function is to minimize to the number of frequencies used. We formulate this byminimizing the largest frequency number that occurs for the used variables:
minimize maximumd∈DEMANDS (used )3.4.2

Implementation
The edges forming the telecommunications network are modeled as a list LINK, where edge l isgiven as (LINK(l,1),LINK(l,2)).
For the implementation of the constraints on the values of frequencies assigned to the samenode we have two equivalent choices with Kalis, namely using abs or distance constraints.
model "Frequency assignment"
uses "kalis"forward procedure print_solution
declarations
NODES = 1..10
LINKS = 1..18
DEM: array(NODES) of integer
LINK: array(LINKS,1..2) of integer
INDEX: array(NODES) of integer
NUMDEM: integer
end-declarations! Range of nodes! Range of links between nodes! Demand of nodes! Neighboring nodes! Start index in ’use’! Upper bound on no. of freq.

DEM :: (1..10)[4, 5, 2, 3, 2, 4, 3, 4, 3, 2]
LINK:: (1..18,1..2)[1, 3, 1, 4, 1, 6,
2, 4, 2, 7,
3, 4, 3, 6, 3, 8, 3, 9,
4, 7, 4, 9, 4,10,
5, 7, 5, 8, 5, 9,
6, 9, 7, 8, 8,10]

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

27

Constraints

NUMDEM:= sum(n in NODES) DEM(n)! Correspondence of nodes and demand indices:! use(d) d = 1, ..., DEM(1) correspond to the demands of node 1!
d = DEM(1)+1, ..., DEM(1)+DEM(2))- " node 2
INDEX(1):= 1
forall(n in NODES | n > 1) INDEX(n) := INDEX(n-1) + DEM(n-1)
declarations
DEMANDS = 1..NUMDEM
use: array(DEMANDS) of cpvar
numfreq: cpvar
Strategy: array(range) of cpbranchingend-declarationsetc.

! Range of frequency demands! Frequency used for a demand! Number of frequencies used

! Setting the domain of the decision variables
forall(d in DEMANDS) setdomain(use(d), 1, NUMDEM)! All frequencies attached to a node must be different by at least 2
forall(n in NODES, c,d in INDEX(n)..INDEX(n)+DEM(n)-1 | c<d)distance(use(c), use(d)) >= 2
! abs(use(c) - use(d)) >= 2
! Neighboring nodes take all-different frequencies
forall(l in LINKS)
all_different(
union(d in INDEX(LINK(l,1))..INDEX(LINK(l,1))+DEM(LINK(l,1))-1) {use(d)} +union(d in INDEX(LINK(l,2))..INDEX(LINK(l,2))+DEM(LINK(l,2))-1) {use(d)},KALIS_GEN_ARC_CONSISTENCY)! Objective function: minimize the number of frequencies used, that is,! minimize the largest value assigned to ’use’
setname(numfreq, "NumFreq")
numfreq = maximum(use)! Search strategy
Strategy(1):=assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, use)
Strategy(2):=assign_var(KALIS_MAX_DEGREE, KALIS_MIN_TO_MAX, use)
cp_set_branching(Strategy(1))
setparam("KALIS_MAX_COMPUTATION_TIME", 1)
cp_set_solution_callback("print_solution")! Try to find solution(s) with strategy 1
if (cp_minimize(numfreq)) thencp_show_stats
sol:=getsol(numfreq)
end-if! Restart search with strategy 2
cp_reset_search
if sol>0 then
! If a solution was found:numfreq <= sol-1! Add upper bound on objective
end-ifcp_set_branching(Strategy(2))
setparam("KALIS_MAX_COMPUTATION_TIME", 1000)
if (cp_minimize(numfreq)) thencp_show_stats
elif sol>0 thenwriteln("Optimality proven")else
writeln("Problem has no solution")
end-if!********************************************************************! **** Solution printout ****
procedure print_solution
writeln("Number of frequencies: ", getsol(numfreq))
writeln("Frequency assignment: ")Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

28

Constraints

forall(n in NODES) do
write("Node ", n, ": ")forall(d in INDEX(n)..INDEX(n)+DEM(n)-1) write(getsol(use(d)), " ")writeln
end-doend-procedure
end-modelWith just the default search strategy this model finds a solution of value 11 but it runs for a longtime without being able to prove optimality. When experimenting with different searchstrategies we have found that the strategy obtained by changing the variable selection criterion
to KALIS_MAX_DEGREE is able to prove optimality easily once a good solution is known. This
problem is therefore solved in two steps: First, we use the default strategy for finding a goodsolution. This search is stopped after one second by setting a time limit. The search is thenrestarted (previously, we needed to reset the search tree in the solver with cp_reset_search) witha second strategy and the bound on the objective value from the previous run.
To ease the experiments with different search strategies we have defined an array Strategy oftype cpbranching that stores the different search strategy definitions.
Another new feature demonstrated by this implementation is the use of a callback, more
precisely the solution callback of Xpress Kalis. The solution callback is defined with a user
subroutine that will be called by the solver whenever the search has found a solution. Its typicaluses are logging or storing of intermediate solutions or performing some statistics. Our
procedure print_solution simply prints out the solution that has been found.
Improving the problem formulation: we may observe that in our problem formulation all
demand variables within a node and the constraints on these variables are entirely symmetric. In
the absence of other constraints, we may reduce these symmetries by imposing an order on theuse variables,used + 1 ≤ used+1
for demands d and d + 1 belonging to the same cell. Doing so, the problem is solved to optimality
within less than 40 nodes using just the default strategy. We may take this a step further by
writingused + 2 ≤ used+1
The addition of these constraints shortens the search by yet a few more nodes. They can even be
used simply in replacement of the abs or distance constraints.

3.4.3

Results
An optimal solution to this problem uses 11 different frequencies. The model shown in the
program listing prints out the following assignment of frequencies to nodes:
Node 1: 1 3 5 7Node 2: 1 3 5 7 10
Node 3: 2 8
Node 4: 4 6 9Node 5: 4 6
Node 6: 4 6 9 11
Node 7: 2 8 11
Node 8: 1 3 5 7Node 9: 1 3 5
Node 10: 2 8

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

29

Constraints

3.5 element: Sequencing jobs on a single machine
The problem described in this section is taken from Section 7.4 ‘Sequencing jobs on a bottleneckmachine’ of the book ‘Applications of optimization with Xpress-MP’
The aim of this problem is to provide a model that may be used with different objective functions
for scheduling operations on a single (bottleneck) machine. We shall see here how to minimize
the total processing time, the average processing time, and the total tardiness.
A set of tasks (or jobs) is to be processed on a single machine. The execution of tasks is
non-preemptive (that is, an operation may not be interrupted before its completion). For every
task i its release date, duration, and due date are given in Table 3.4.
Table 3.4: Task time windows and durations
Job

1

2

3

4

5

6

7

Release date
DurationDue date

2
5
10

5
6
21

4
8
15

0
4
10

0
2
5

8
4
15

9
2
22

What is the optimal value for each of the objectives: minimizing the total duration of theschedule (makespan), the mean processing time or the total tardiness (that is, the amount of timeby which the completion of jobs exceeds their respective due dates)?

3.5.1

Model formulation 1
We are going to present two alternative model formulations. The first is closer to the
Mathematical Programming formulation in ‘Applications of optimization with Xpress-MP’. The
second uses disjunctive constraints and branching on these. In both model formulations we aregoing deal with the different objective functions in sequence, but the body of the models willremain the same.
To represent the sequence of jobs we introduce variables rankk (k ∈ JOBS = {1, . . . , NJ}) that takeas value the number of the job in position (rank) k. Every job j takes a single position. This
constraint can be represented by an all-different on the rankk variables:
all-different(rank1 , . . . , rankNJ )The processing time durk for the job in position k is given by DURrankk (where DURj denotes theduration given in the table in the previous section). Similarly, the release time relk is given by
RELrankk (where RELj denotes the given release date):∀k ∈ JOBS : durk = DURrankk∀k ∈ JOBS : relk = RELrankk
If startk is the start time of the job at position k, this value must be at least as great as the release
date of the job assigned to this position. The completion time compk of this job is the sum of its
start time plus its duration:∀k ∈ JOBS : startk ≥ relk∀k ∈ JOBS : compk = startk + durk
Another constraint is needed to specify that two jobs cannot be processed simultaneously. The
job in position k + 1 must start after the job in position k has finished, hence the following
constraints:∀k ∈ {1, . . . , NJ − 1} : startk+1 ≥ startk + durk

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

30

Constraints

Objective 1: The first objective is to minimize the makespan (completion time of the schedule), or,equivalently, to minimize the completion time of the last job (job with rank NJ). The complete
model is then given by the following (where MAXTIME is a sufficiently large value, such as thesum of all release dates and all durations):
minimize compNJ∀k ∈ JOBS : rankk ∈ JOBS∀k ∈ JOBS : startk , compk ∈ {0, . . . , MAXTIME}∀k ∈ JOBS : durk ∈ {minj∈JOBS DURj , . . . , maxj∈JOBS DURj }∀k ∈ JOBS : relk ∈ {minj∈JOBS RELj , . . . , maxj∈JOBS RELj }all-different(rank1 , . . . , rankNJ )∀k ∈ JOBS : durk = DURrankk∀k ∈ JOBS : relk = RELrankk∀k ∈ JOBS : startk ≥ relk∀k ∈ JOBS : compk = startk + durk∀k ∈ {1, . . . , NJ − 1} : startk+1 ≥ startk + durk
Objective 2: For minimizing the average processing time, we introduce an additional variable
totComp representing the sum of the completion times of all jobs. We add the following
constraint to the problem to calculate totComp:X
totComp =compkk∈JOBS

The new objective consists of minimizing the average processing time, or equivalently,
minimizing the sum of the job completion times:
minimize totComp
Objective 3: If we now aim to minimize the total tardiness, we again introduce newvariables—this time to measure the amount of time that jobs finish after their due date. We
write latek for the variable that corresponds to the tardiness of the job with rank k. Its value isthe difference between the completion time of a job j and its due date DUEj . If the job finishes
before its due date, the value must be zero. We thus obtain the following constraints:∀k ∈ JOBS : duek = DUErankk∀k ∈ JOBS : latek ≥ compk − duek
For the formulation of the new objective function we introduce the variable totLate representing
the total tardiness of all jobs. The objective now is to minimize the value of this variable:
minimize totLate
X
totLate =latekk∈JOBS

3.5.2

Implementation of model 1
The Mosel implementation below solves the same problem three times, each time with a different
objective, and prints the resulting solutions by calling the procedures print_sol and print_sol3.
model "B-4 Sequencing (CP)"uses "kalis"

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

31

Constraints

forward procedure print_sol
forward procedure print_sol3
declarations
NJ = 7
JOBS=1..NJ! Number of jobs

REL: array(JOBS) of integer
DUR: array(JOBS) of integer
DUE: array(JOBS) of integer! Release dates of jobs
! Durations of jobs
! Due dates of jobs

rank: array(JOBS) of cpvar
start: array(JOBS) of cpvar
dur: array(JOBS) of cpvar
comp: array(JOBS) of cpvar
rel: array(JOBS) of cpvar
end-declarations! Number of job at position k! Start time of job at position k! Duration of job at position k! Completion time of job at position k! Release date of job at position k

initializations from ’Data/b4seq.dat’
DUR REL DUE
end-initializations
MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)MINDUR:= min(j in JOBS) DUR(j); MAXDUR:= max(j in JOBS) DUR(j)MINREL:= min(j in JOBS) REL(j); MAXREL:= max(j in JOBS) REL(j)forall(j in JOBS) do
1 <= rank(j); rank(j) <= NJ
0 <= start(j); start(j) <= MAXTIMEMINDUR <= dur(j); dur(j) <= MAXDUR
0 <= comp(j); comp(j) <= MAXTIMEMINREL <= rel(j); rel(j) <= MAXREL
end-do! One posistion per job
all_different(rank)! Duration of job at position kforall(k in JOBS) dur(k) = element(DUR, rank(k))! Release date of job at position kforall(k in JOBS) rel(k) = element(REL, rank(k))! Sequence of jobs
forall(k in 1..NJ-1) start(k+1) >= start(k) + dur(k)! Start times
forall(k in JOBS) start(k) >= rel(k)! Completion times
forall(k in JOBS) comp(k) = start(k) + dur(k)! Set the branching strategy
cp_set_branching(split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX))!**** Objective function 1: minimize latest completion time ****
if cp_minimize(comp(NJ)) thenprint_sol
end-if!**** Objective function 2: minimize average completion time ****
declarations
totComp: cpvar
end-declarations
totComp = sum(k in JOBS) comp(k)if cp_minimize(totComp) then

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

32

Constraints

print_sol
end-if!**** Objective function 3: minimize total tardiness ****
declarations
late: array(JOBS) of cpvar! Lateness of job at position kdue: array(JOBS) of cpvar! Due date of job at position k
totLate: cpvar
end-declarations
MINDUE:= min(k in JOBS) DUE(k); MAXDUE:= max(k in JOBS) DUE(k)forall(k in JOBS) do
MINDUE <= due(k); due(k) <= MAXDUE
0 <= late(k); late(k) <= MAXTIME
end-do! Due date of job at position kforall(k in JOBS) due(k) = element(DUE, rank(k))! Late jobs: completion time exceeds the due dateforall(k in JOBS) late(k) >= comp(k) - due(k)totLate = sum(k in JOBS) late(k)if cp_minimize(totLate) thenwriteln("Tardiness: ", getsol(totLate))
print_sol
print_sol3
end-if!----------------------------------------------------------------! Solution printing
procedure print_sol
writeln("Completion time: ", getsol(comp(NJ)) ," average: ", getsol(sum(k in JOBS) comp(k)))
write("\t")forall(k in JOBS) write(strfmt(getsol(rank(k)),4))
write("\nRel\t")forall(k in JOBS) write(strfmt(getsol(rel(k)),4))
write("\nDur\t")forall(k in JOBS) write(strfmt(getsol(dur(k)),4))
write("\nStart\t")forall(k in JOBS) write(strfmt(getsol(start(k)),4))
write("\nEnd\t")forall(k in JOBS) write(strfmt(getsol(comp(k)),4))
writeln
end-procedure
procedure print_sol3
write("Due\t")forall(k in JOBS) write(strfmt(getsol(due(k)),4))
write("\nLate\t")forall(k in JOBS) write(strfmt(getsol(late(k)),4))
writeln
end-procedure
end-model

NB: The reader may have been wondering why we did not use the more obvious pair start − end
for naming the variables in this example: end is a keyword of the Mosel language (see the list ofreserved words in the Mosel language reference manual), which means that neither end nor END
may be redefined by a Mosel program. It is possible though, to use versions combining lower andupper case letters, like End, but to prevent any possible confusion we do not recommend theiruse.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

33

Constraints

3.5.3

Results
The minimum makespan of the schedule is 31, the minimum sum of completion times is 103(which gives an average of 103 / 7 = 14. 71). A schedule with this objective value is
5 → 4 → 1 → 7 → 6 → 2 → 3. If we compare the completion times with the due dates we see thatjobs 1, 2, 3, and 6 finish late (with a total tardiness of 21). The minimum tardiness is 18. A
schedule with this tardiness is 5 → 1 → 4 → 6 → 2 → 7 → 3 where jobs 4 and 7 finish one time
unit late and job 3 is late by 16 time units, and it terminates at time 31 instead of being ready atits due date, time 15. This schedule has an average completion time of 15.71.

3.5.4

Alternative formulation using disjunctions
Our second model formulation is possibly a more straightforward way of representing the
problem. It introduces disjunctive constraints and branching on these.
Every job is now represented by its starting time, variables startj (j ∈ JOBS = {1, . . . , NJ}) that taketheir values in {RELj , . . . , MAXTIME} (where MAXTIME is a sufficiently large value, such as the sumof all release dates and all durations, and RELj the release date of job j). We state the disjunctions
as a single disjunctive relation on the start times and durations of all jobs.
disjunctive([start1 , . . . , startNJ ], [DUR1 , . . . , DURNJ ])This constraint replaces the pair-wise disjunctions
starti + DURi ≤ startj ∨ startj + DURj ≤ starti
for all pairs of jobs i < j ∈ JOBS.
The processing time durk for the job in position k is given by DURrankk (where DURj denotes theduration given in the table in the previous section). Similarly, its release time relk is given by
RELrankk (where RELj denotes the given release date).
∀k ∈ JOBS : durk = DURrankk∀k ∈ JOBS : relk = RELrankk
The completion time compj of a job j is the sum of its start time plus its duration DURj .
∀j ∈ JOBS : compj = startj + DURj
Objective 1: The first objective is to minimize the makespan (completion time of the schedule) or,
equivalently, to minimize the completion time finish of the last job. The complete model is thengiven by the following (where MAXTIME is a sufficiently large value, such as the sum of all
release dates and all durations):
minimize finish
finish = maximumj∈JOBS (compj )∀j ∈ JOBS : compj ∈ {0, . . . , MAXTIME}∀j ∈ JOBS : startj ∈ {RELj , . . . , MAXTIME}
disjunctive([start1 , . . . , startNJ ], [DUR1 , . . . , DURNJ ])∀j ∈ JOBS : compj = startj + DURj
Objective 2: The formulation of the second objective (minimizing the average processing time or,
equivalently, minimizing the sum of the job completion times) remains unchanged from the first

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

34

Constraints

model—we introduce an additional variable totComp representing the sum of the completion
times of all jobs.
minimize totComp
X
totComp =compkk∈JOBS

Objective 3: To formulate the objective of minimizing the total tardiness, we introduce newvariables latej to measure the amount of time that a job finishes after its due date. The value ofthese variables corresponds to the difference between the completion time of a job j and its due
date DUEj . If the job finishes before its due date, the value must be zero. The objective now is tominimize the sum of these tardiness variables:
minimize totLate
X
totLate =latej
j∈JOBS∀j ∈ JOBS : latej ∈ {0, . . . , MAXTIME}∀j ∈ JOBS : latej ≥ compj − DUEj

3.5.5

Implementation of model 2
As with model 1, the Mosel implementation below solves the same problem three times, eachtime with a different objective, and prints the resulting solutions by calling the procedures
print_sol and print_sol3.
model "B-4 Sequencing (CP)"uses "kalis"forward procedure print_sol
forward procedure print_sol3
declarations
NJ = 7
JOBS=1..NJ! Number of jobs

REL: array(JOBS) of integer! Release dates of jobs
DUR: array(JOBS) of integer! Durations of jobs
DUE: array(JOBS) of integer! Due dates of jobs
DURS: array(set of cpvar) of integer ! Dur.s indexed by start variables
start: array(JOBS) of cpvar! Start time of jobs
comp: array(JOBS) of cpvar! Completion time of jobs
finish: cpvar! Completion time of the entire schedule
Disj: set of cpctr! Disjunction constraints
Strategy: array(range) of cpbranching ! Branching strategy
end-declarations
initializations from ’Data/b4seq.dat’
DUR REL DUE
end-initializations
MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)forall(j in JOBS) do
0 <= start(j); start(j) <= MAXTIME
0 <= comp(j); comp(j) <= MAXTIME
end-do! Disjunctions between jobs
forall(j in JOBS) DURS(start(j)):= DUR(j)disjunctive(union(j in JOBS) {start(j)}, DURS, Disj, 1)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

35

Constraints! Start times
forall(j in JOBS) start(j) >= REL(j)! Completion times
forall(j in JOBS) comp(j) = start(j) + DUR(j)!**** Objective function 1: minimize latest completion time ****
finish = maximum(comp)
Strategy(1):= settle_disjunction(Disj)
Strategy(2):= split_domain(KALIS_LARGEST_MAX, KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
if cp_minimize(finish) thenprint_sol
end-if!**** Objective function 2: minimize average completion time ****
declarations
totComp: cpvar
end-declarations
totComp = sum(k in JOBS) comp(k)if cp_minimize(totComp) thenprint_sol
end-if!**** Objective function 3: minimize total tardiness ****
declarations
late: array(JOBS) of cpvar! Lateness of jobs
totLate: cpvar
end-declarations
forall(k in JOBS) do
0 <= late(k); late(k) <= MAXTIME
end-do! Late jobs: completion time exceeds the due dateforall(j in JOBS) late(j) >= comp(j) - DUE(j)totLate = sum(k in JOBS) late(k)if cp_minimize(totLate) thenwriteln("Tardiness: ", getsol(totLate))
print_sol
print_sol3
end-if!----------------------------------------------------------------! Solution printing
procedure print_sol
writeln("Completion time: ", getsol(finish) ," average: ", getsol(sum(j in JOBS) comp(j)))
write("Rel\t")forall(j in JOBS) write(strfmt(REL(j),4))
write("\nDur\t")forall(j in JOBS) write(strfmt(DUR(j),4))
write("\nStart\t")forall(j in JOBS) write(strfmt(getsol(start(j)),4))
write("\nEnd\t")forall(j in JOBS) write(strfmt(getsol(comp(j)),4))
writeln
end-procedure
procedure print_sol3
write("Due\t")Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

36

Constraints

forall(j in JOBS) write(strfmt(DUE(j),4))
write("\nLate\t")forall(j in JOBS) write(strfmt(getsol(late(j)),4))
writeln
end-procedure
end-modelThis implementation introduces a new branching scheme, namely settle_disjunction. As
opposed to the branching strategies we have seen so far this scheme defines a branching strategy
over constraints, and not over variables. With this scheme a node is created by choosing a
constraint from the given set and the branches from the node are obtained by adding one of themutually exclusive constraints forming this disjunctive constraint to the constraint system.
NB: the disjunctive constraint of Xpress Kalis establishes pair-wise inequalities between theprocessing times of tasks. However, the definition of disjunctive constraints is not restricted tothis case: a disjunction may have more than two components, and involve constraints of any type,including other logic relations obtained by combining constraints with and or or.

3.6 occurrence: Sugar production
The problem description in this section is taken from Section 6.4 ‘Cane sugar production’ of thebook ‘Applications of optimization with Xpress-MP’
The harvest of cane sugar in Australia is highly mechanized. The sugar cane is immediatelytransported to a sugarhouse in wagons that run on a network of small rail tracks. The sugar
content of a wagonload depends on the field it has been harvested from and on the maturity ofthe sugar cane. Once harvested, the sugar content decreases rapidly through fermentation andthe wagonload will entirely lose its value after a certain time. At this moment, eleven wagons
loaded with the same quantity have arrived at the sugarhouse. They have been examined to findout the hourly loss and the remaining life span (in hours) of every wagon, these data aresummarized in the following table.
Table 3.5: Properties of the lots of cane sugar
Lot

1

2

3

4

5

6

7

8

9

10

11

Loss (kg/h)Life span (h)

43
8

26
8

37
2

28
8

13
4

54
8

62
8

49
8

19
8

28
8

30
8

Every lot may be processed by any of the three, fully equivalent production lines of thesugarhouse. The processing of a lot takes two hours. It must be finished at the latest at the endof the life span of the wagonload. The manager of the sugarhouse wishes to determine a
production schedule for the currently available lots that minimizes the total loss of sugar.

3.6.1

Model formulation
Let WAGONS = {1, . . . , NW} be the set of wagons, NL the number of production lines and DUR
the duration of the production process for every lot. The hourly loss for every wagon w is given
by LOSSw and its life span by LIFEw . We observe that, in an optimal solution, the production lines
need to work without any break—otherwise we could reduce the loss in sugar by advancing thestart of the lot that follows the break. This means that the completion time of every lot is of theform s · DUR, with s > 0 and is an integer. The maximum value of s is the number of time slots (oflength DUR) that the sugarhouse will work, namely NS = ceil(NW / NL), where ceil stands for‘rounded to the next largest integer’. If NW / NL is an integer, every line will process exactly NS
lots. Otherwise, some lines will process NS − 1 lots, but at least one line processes NS lots. In all

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

37

Constraints

cases, the length of the optimal schedule is NS · DUR hours. We call SLOTS = {1, . . . , NS} the set oftime slots.
Every lot needs to be assigned to a time slot. We define variables processw for the time slot
assigned to wagon w and variables lossw for the loss incurred by this wagonload. Every time slot
may take up to NL lots because there are NL parallel lines; therefore, we limit the number ofoccurrences of time slot values among the processw variables (this constraint relation is often
called cardinality constraint):s ∈ SLOTS : |processw = s|w∈WAGONS ≤ NL
The loss of sugar per wagonload w and time slot s is COSTws = s · DUR · LOSSw . Let variables lossw
denote the loss incurred by wagon load w:∀w ∈ WAGONS : lossw = COSTw,processw
The objective function (total loss of sugar) is then given as the sum of all losses:
X
lossw
minimizew∈WAGONS

3.6.2

Implementation
The following model is the Mosel implementation of this problem. It uses the function ceil tocalculate the maximum number of time slots.
The constraints on the processing variables are expressed by occurrence relations and the losses
are obtained via element constraints. The branching strategy uses the variable selection criterion
KALIS_SMALLEST_MAX, that is, choosing the variable with the smallest upper bound.
model "A-4 Cane sugar production (CP)"uses "kalis"declarations
NW = 11
NL = 3
WAGONS = 1..NW
NS = ceil(NW/NL)SLOTS = 1..NS! Number of wagon loads of sugar! Number of production lines! Time slots for production

LOSS: array(WAGONS) of integer
LIFE: array(WAGONS) of integer
DUR: integer
COST: array(SLOTS) of integer! Loss in kg/hour! Remaining time per lot (in hours)! Duration of the production (in hours)! Cost per wagon

loss: array(WAGONS) of cpvar
process: array(WAGONS) of cpvar! Loss per wagon! Time slots for wagon loads

totalLoss: cpvar
end-declarations! Objective variable

initializations from ’Data/a4sugar.dat’
LOSS LIFE DUR
end-initializations
forall(w in WAGONS) setdomain(process(w), 1, NS)! Wagon loads per time slot
forall(s in SLOTS) occurrence(s, process) <= NL! Limit on raw product life
forall(w in WAGONS) process(w) <= floor(LIFE(w)/DUR)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

38

Constraints! Objective function: total loss
forall(w in WAGONS) do
forall(s in SLOTS) COST(s):= s*DUR*LOSS(w)loss(w) = element(COST, process(w))
end-dototalLoss = sum(w in WAGONS) loss(w)cp_set_branching(assign_var(KALIS_SMALLEST_MAX, KALIS_MIN_TO_MAX, process))! Solve the problem
if not (cp_minimize(totalLoss)) thenwriteln("No solution found")exit(0)end-if! Solution printing
writeln("Total loss: ", getsol(totalLoss))
forall(s in SLOTS) do
write("Slot ", s, ": ")forall(w in WAGONS)
if(getsol(process(w))=s) thenwrite("wagon ", strfmt(w,2), strfmt(" (" + s*DUR*LOSS(w) + ")end-ifwriteln
end-do", 8))

end-model

An alternative formulation of the constraints on the processing variables is to replace them by asingle distribute relation, indicating for every time slot the minimum and maximum number(MINUSEs = 0 and MAXUSEs = NL) of production lines that may be used.
forall(s in SLOTS) MAXUSE(s):= NL
distribute(process, SLOTS, MINUSE, MAXUSE)Yet another formulation of this problem is possible with Xpress Kalis, namely interpreting it as acumulative scheduling problem (see Section 5.4), where the wagon loads are represented by tasksof unit duration, scheduled on a discrete resource with a capacity corresponding to the numberof production lines.

3.6.3

Results
We obtain a total loss of 1620 kg of sugar. The corresponding schedule of lots is shown in thefollowing Table 3.6 (there are several equivalent solutions).
Table 3.6: Optimal schedule for the cane sugar lots
Slot 1

Slot 2

Slot 3

Slot 4lot 3 (74 kg)
lot 6 (108 kg)
lot 7 (124 kg)

lot 1 (172 kg)
lot 5 (52 kg)
lot 8 (196 kg)

lot 4 (168 kg)
lot 9 (114 kg)
lot 11 (180 kg)

lot 2 (208 kg)
lot 10 (224 kg)

3.7 distribute: Personnel planning
The director of a movie theater wishes to establish a plan with the working locations for his
personnel. The theater has eight employees: David, Andrew, Leslie, Jason, Oliver, Michael, Jane,and Marilyn. The ticket office needs to be staffed with three persons, theater entrances one andtwo require two persons each, and one person needs to be put in charge of the cloakroom. Due

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

39

Constraints

to different qualifications and respecting individual likes and dislikes, the following constraints
need to be taken into account:
1. Leslie must be at the second entrance of the theater.
2. Michael must be at the first entrance of the theater.
3. David, Michael and Jason cannot work with each other.
4. If Oliver is selling tickets, Marylin must be with him.

3.7.1

Model formulation
Let PERS be the set of personnel and LOC = {1, . . . , 4} the set of working locations where 1 stands
for the ticket office, 2 and 3 for entrances 1 and 2 respectively, and 4 for the cloakroom.
We introduce decision variables placep for the working location assigned to person p. The fourindividual constraints on working locations can then be stated as follows:
placeLeslie = 3
placeMichael = 2
all-different(placeDavid , placeMichael , placeJason )placeOliver = 1 ⇒ placeMarylin = 1
We also have to meet the staffing requirement of every working location:∀l ∈ LOC : |placep = l|p∈PERS = REQl

3.7.2

Implementation
For the implementation of the staffing requirements we may choose among two different
constraints of Xpress Kalis, namely occurrence constraints (one per working location) or a
distribute constraint (also known as global cardinality constraint) over all working locations.
The following model shows both options. As opposed to the previous example (Section 3.6.2 wenow have equality constraints. We therefore use the three-argument version of distribute(instead of the version with four arguments where the last two are the lower and upper bounds
respectively).
For an attractive display, the model also introduces a few auxiliary data structures with the namesof the working locations and the corresponding index values in the set LOC.
model "Personnel Planning (CP)"uses "kalis"forward procedure print_solution
declarations
PERS = {"David","Andrew","Leslie","Jason","Oliver","Michael","Jane","Marilyn"}! Set of personnel
LOC = 1..4
! Set of locations
LOCNAMES = {"Ticketoffice", "Theater1", "Theater2","Cloakroom"}! Names of locations
LOCNUM: array(LOCNAMES) of integer! Numbers assoc. with loc.s
REQ: array(LOC) of integer! No. of pers. req. per loc.
place: array(PERS) of cpvar
end-declarations! Workplace assigned to each peson! Initialize data

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

40

Constraints

LOCNUM("Ticketoffice"):= 1; LOCNUM("Theater1"):= 2
LOCNUM("Theater2"):= 3; LOCNUM("Cloakroom"):= 4
REQ:: (1..4)[3, 2, 2, 1]! Each variable has a lower bound of 1 (Ticketoffice) and an upper bound! of 4 (Cloakroom)
forall(p in PERS) do
setname(place(p),"workplace["+p+"]")
setdomain(place(p), LOC)
end-do! "Leslie must be at the second entrance of the theater"
place("Leslie") = LOCNUM("Theater2")! "Michael must be at the first entrance of the theater"
place("Michael") = LOCNUM("Theater1")! "David, Michael and Jason cannot work with each other"
all_different({place("David"), place("Michael"), place("Jason")})! "If Oliver is selling tickets, Marylin must be with him"
implies(place("Oliver")=LOCNUM("Ticketoffice"),place("Marilyn")=LOCNUM("Ticketoffice"))! Creation of a resource constraint of for every location! forall(d in LOC) occurrence(LOCNUM(d), place) = REQ(d)! Formulation of resource constraints using global cardinality constraint
distribute(place, LOC, REQ)
! Setting parameters of the enumeration
cp_set_branching(assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN, place))! Solve the problem
if not(cp_find_next_sol) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution output
nbSolutions:= 1
print_solution! Search for other solutions
while (cp_find_next_sol) do
nbSolutions += 1
print_solution
end-do! **** Solution printout ****
procedure print_solution
declarations
LOCIDX: array(LOC) of string
end-declarations
forall(l in LOCNAMES) LOCIDX(LOCNUM(l)):=l
writeln("\nSolution number ", nbSolutions)forall(p in PERS)
writeln(" Working place of ", p, ": ", LOCIDX(getsol(place(p))))end-procedure
end-model

Since we merely wish to find a feasible assignment of working locations, this model first tests
whether a feasible solution exists. If this is the case, it also enumerates all other feasible solutions.
Each time a solution is found it is printed out by call to the procedure print_solution.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

41

Constraints

3.7.3

Results
This problem has 38 feasible solutions. A graphical representation of a feasible assignment isshown in Figure 3.2.

Figure 3.2: Personnel schedule representation

The following Mosel code was used for generating the graphic (see the documentation ofmodule mmsvg in the Mosel language reference manual for further explanation).
! **** Solution printout and graphical display ****
procedure draw_solution
svgerase
svgaddgroup("PersGraph", "Personnel")svgsetstyle(SVG_TEXTANCHOR, "end")
svgaddgroup("LocGraph", "Locations")
svgaddgroup("AsgnGraph", "Assignments", SVG_BLACK)
forall(d in LOCNAMES)
svgaddtext("LocGraph", 4, LOCNUM(d), d)
FACT:=LOCNAMES.size/PERS.size
idx:= 1
forall(p in PERS, idx as counter) do
svgaddline("AsgnGraph", 2, idx*FACT, 4, getsol(place(p)))
svgaddtext("PersGraph", 2, idx*FACT, p)
end-dosvgsetgraphscale(75)svgsetgraphviewbox(0,0,5,LOCNAMES.size+1)
svgrefresh! Uncomment to pause at every iteration:
if nbSolutions<MAXSOL then svgpause; end-if
end-procedure

3.8 implies: Paint production
The problem description in this section is taken from Section 7.5 ‘Paint production’ of the book

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

42

Constraints‘Applications of optimization with Xpress-MP’
As a part of its weekly production a paint company produces five batches of paints, always thesame, for some big clients who have a stable demand. Every paint batch is produced in a single
production process, all in the same blender that needs to be cleaned between every two batches.
The durations of blending paint batches 1 to 5 are respectively 40, 35, 45, 32, and 50 minutes. The
cleaning times depend on the colors and the paint types. For example, a long cleaning period isrequired if an oil-based paint is produced after a water-based paint, or to produce white paintafter a dark color. The times are given in minutes in the following Table 3.7 CLEAN where CLEANijdenotes the cleaning time between batch i and batch j.
Table 3.7: Matrix of cleaning times
1
2
3
4
5

1

2

3

4

5

0
5
13
9
3

11
0
15
13
7

7
13
0
5
7

13
15
23
0
7

11
15
11
3
0

Since the company also has other activities, it wishes to deal with this weekly production in the
shortest possible time (blending and cleaning). Which is the corresponding order of paintbatches? The order will be applied every week, so the cleaning time between the last batch of
one week and the first of the following week needs to be counted for the total duration ofcleaning.

3.8.1

Formulation of model 1
As for the problem in Section 3.5 we are going to present two alternative model formulations.
The first one is closer to the Mathematical Programming formulation in ‘Applications of
optimization with Xpress-MP’, the second uses a two-dimensional element constraint.
Let JOBS = {1, . . . , NJ} be the set of batches to produce, DURj the processing time for batch j, and
CLEANij the cleaning time between the consecutive batches i and j. We introduce decisionvariables succj taking their values in JOBS, to indicate the successor of every job, and variables
cleanj for the duration of the cleaning after every job. The cleaning time after every job is
obtained by indexing CLEANij with the value of succj . We thus have the following problem
formulation.
X
minimize(DURj + cleanj )j∈JOBS∀j ∈ JOBS : succj ∈ JOBS\{j}∀j ∈ JOBS : cleanj = CLEANj,succj
[
all-different 
succj j∈JOBS

The objective function sums up the processing and cleaning times of all batches. The last
(all-different) constraint guarantees that every batch occurs exactly once in the production
sequence.
Unfortunately, this model does not guarantee that the solution forms a single cycle. Solving it
indeed results in a total duration of 239 with an invalid solution that contains two sub-cycles
1 → 3 → 2 → 1 and 4 → 5 → 4. A first possibility is to add a disjunction excluding this solution to
our model and re-solve it iteratively until we reach a solution without sub-cycles.
∀succ1 6= 3 ∨ succ3 6= 2 ∨ succ2 6= 1 ∨ succ1 6= 5 ∨ succ5 6= 4

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

43

Constraints

However, this procedure is likely to become impractical with larger data sets since it may
potentially introduce an extremely large number of disjunctions. We therefore choose a
different, a-priori formulation of the sub-cycle elimination constraints with a variable yj per batchand NJ · (NJ − 1) implication constraints.
∀j ∈ JOBS : rankj ∈ {1, . . . , NJ}∀i ∈ JOBS, ∀j = 2, . . . , NJ, i 6= j : succi = j ⇒ yj = yi + 1
The variables yj correspond to the position of job j in the production cycle. With these constraints,
job 1 always takes the first position.

3.8.2

Implementation of model 1
The Mosel implementation of the model formulated in the previous section is quite
straightforward. The sub-cycle elimination constraints are implemented as logic relations with
implies (a stronger formulation of these constraints is obtained by replacing the implications byequivalences, using equiv).
model "B-5 Paint production (CP)"uses "kalis"declarations
NJ = 5
JOBS=1..NJ! Number of paint batches (=jobs)

DUR: array(JOBS) of integer! Durations of jobs
CLEAN: array(JOBS,JOBS) of integer ! Cleaning times between jobs
CB: array(JOBS) of integer! Cleaning times after a batch
succ: array(JOBS) of cpvar
clean: array(JOBS) of cpvar
y: array(JOBS) of cpvar
cycleTime: cpvar
end-declarations! Successor of a batch! Cleaning time after batches! Variables for excluding subtours! Objective variable

initializations from ’Data/b5paint.dat’
DUR CLEAN
end-initializations
forall(j in JOBS) do
1 <= succ(j); succ(j) <= NJ; succ(j) <> j
1 <= y(j); y(j) <= NJ
end-do! Cleaning time after every batch
forall(j in JOBS) do
forall(i in JOBS) CB(i):= CLEAN(j,i)
clean(j) = element(CB, succ(j))
end-do! Objective: minimize the duration of a production cycle
cycleTime = sum(j in JOBS) (DUR(j)+clean(j))! One successor and one predecessor per batch
all_different(succ)! Exclude subtours
forall(i in JOBS, j in 2..NJ | i<>j)
implies(succ(i) = j, y(j) = y(i) + 1)
! Solve the problem
if not cp_minimize(cycleTime) thenwriteln("Problem is infeasible")exit(1)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

44

Constraints

end-ifcp_show_stats! Solution printing
writeln("Minimum cycle time: ", getsol(cycleTime))
writeln("Sequence of batches:\nBatch Duration Cleaning")
first:=1
repeatwriteln(" ", first, strfmt(DUR(first),8), strfmt(getsol(clean(first)),9))first:=getsol(succ(first))
until (first=1)
end-model

3.8.3

Formulation of model 2
We may choose to implement the paint production problem using rank variables similarly to thesequencing model in Section 3.5.1.
As before, let JOBS = {1, . . . , NJ} be the set of batches to produce, DURj the processing time forbatch j, and CLEANij the cleaning time between the consecutive batches i and j. We introduce
decision variables rankk taking their values in JOBS, for the number of the job in position k.
Variables cleank (k ∈ JOBS) now denote the duration of the kth cleaning time. This duration is
obtained by indexing CLEANij with the values of two consecutive rankk variables. We thus havethe following problem formulation.
X
X
minimize
DURj +
cleankj∈JOBSk∈JOBS∀k ∈ JOBS : rankk ∈ JOBS∀k ∈ {1, . . . , NJ − 1} : cleank = CLEANrankk ,rankk+1
cleanNJ = CLEANrankNJ ,rank1!
[
all-different
rankkk∈JOBSAs in model 1, the objective function sums up the processing and cleaning times of all batches.
Although not strictly necessary from the mathematical point of view, we use different sum indicesfor durations and cleaning times to show the difference between summing over jobs or job
positions. We now have an all-different constraint over the rank variables to guarantee thatevery batch occurs exactly once in the production sequence.

3.8.4

Implementation of model 2
The implementation of the second model uses the 2-dimensional version of the element
constraint in Xpress Kalis.
model "B-5 Paint production (CP)"uses "kalis"declarations
NJ = 5
JOBS=1..NJ! Number of paint batches (=jobs)

DUR: array(JOBS) of integer! Durations of jobs
CLEAN: array(JOBS,JOBS) of integer ! Cleaning times between jobs
rank: array(JOBS) of cpvar
clean: array(JOBS) of cpvar
cycleTime: cpvar
end-declarations! Number of job in position k! Cleaning time after batches! Objective variable

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

45

Constraints

initializations from ’Data/b5paint.dat’
DUR CLEAN
end-initializations
forall(k in JOBS) setdomain(rank(k), JOBS)! Cleaning time after every batch
forall(k in JOBS)
if k<NJ thenelement(CLEAN, rank(k), rank(k+1)) = clean(k)elseelement(CLEAN, rank(k), rank(1)) = clean(k)end-if! Objective: minimize the duration of a production cycle
cycleTime = sum(j in JOBS) DUR(j) + sum(k in JOBS) clean(k)! One position for every job
all_different(rank)! Solve the problem
if not cp_minimize(cycleTime) thenwriteln("Problem is infeasible")exit(1)
end-ifcp_show_stats! Solution printing
writeln("Minimum cycle time: ", getsol(cycleTime))
writeln("Sequence of batches:\nBatch Duration Cleaning")
forall(k in JOBS)
writeln(" ", getsol(rank(k)), strfmt(DUR(getsol(rank(k))),8),
strfmt(getsol(clean(k)),9))end-model

3.8.5

Results
The minimum cycle time for this problem is 243 minutes which is achieved with the following
sequence of batches: 1 → 4 → 3 → 5 → 2 → 1. This time includes 202 minutes of (incompressible)
processing time and 41 minutes of cleaning.
When comparing the problem statistics produced by Xpress Kalis for this problem we see that thesecond model is a weaker formulation resulting in a considerably longer enumeration (using thedefault strategies).

3.9 equiv: Location of income tax offices
The example description in the following sections is taken from Section 15.5 ‘Location of income
tax offices’ of the book ‘Applications of optimization with Xpress-MP’.
The income tax administration is planning to restructure the network of income tax offices in aregion. The number of inhabitants of every city and the distances between each pair of cities are
known (Table 3.8). The income tax administration has determined that offices should beestablished in three cities to provide sufficient coverage. Where should these offices be located tominimize the average distance per inhabitant to the closest income tax office?

3.9.1

Model formulation
Let CITIES be the set of cities. For the formulation of the problem, two groups of decisionvariables are necessary: a variable buildc that is one if and only if a tax office is established in city

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information46

Constraints

Table 3.8: Distance matrix and population of cities
1

2

3

4

5

6

7

8

9

10

11

12

1
2
3
4
5
6
7
8
9
10
11
12

0
15
37
55
24
60
18
33
48
40
58
67

15
0
22
40
38
52
33
48
42
55
61
61

37
22
0
18
16
30
43
28
20
58
39
39

55
40
18
0
34
12
61
46
24
62
43
34

24
38
16
34
0
36
27
12
24
49
37
43

60
52
30
12
36
0
57
42
12
50
31
22

18
33
43
61
27
57
0
15
45
22
40
61

33
48
28
46
12
42
15
0
30
37
25
46

48
42
20
24
24
12
45
30
0
38
19
19

40
55
58
62
49
50
22
37
38
0
19
40

58
61
39
43
37
31
40
25
19
19
0
21

67
61
39
34
43
22
61
46
19
40
21
0

Pop. (in 1000)

15

10

12

18

5

24

11

16

13

22

19

20

c, and a variable dependc that takes the number of the office on which city c depends. For theformulation of the constraints, we further introduce two sets of auxiliary variables: depdistc , thedistance from city c to the office indicated by dependc , and numdepc , the number of cities
depending on an office location.
The following relations are required to link the buildc with the dependc variables:(1) numdepc counts the number of occurrences of office location c among the variables dependc .
(2) numdepc ≥ 1 if and only if the office in c is built (as a consequence, if the office in c is not
built, then we must have numdepc = 0).
∀c ∈ CITIES : numdepc = |dependd = c|d∈CITIES∀c ∈ CITIES : numdepc ≥ 1 ⇔ buildc = 1
Since the number of offices built is limited by the given bound NUMLOC
X
buildc ≤ NUMLOC
c∈CITIES

it would actually be sufficient to formulate the second relation between the buildc and dependc
variables as the implication ‘If numdepc ≥ 1 then the office in c must be built, and inversely, if theoffice in c is not built, then we must have numdepc = 0’.
The objective function to be minimized is the total distance weighted by the number of
inhabitants of the cities. We need to divide the resulting value by the total population of theregion to obtain the average distance per inhabitant to the closest income tax office. The
distance depdistc from city c to the closest tax office location is obtained by a discrete function,
namely the row c of the distance matrix DISTcd indexed by the value of dependc :depdistc = DISTc,dependc
We now obtain the following CP model:Xminimize
POPc · distcc∈CITIES∀c ∈ CITIES : buildc ∈ {0, 1}, dependc ∈ CITIES,
numdepc ∈ CITIES ∪ {0}, depdistc ∈ {mind∈CITIES DISTc,d , . . . , maxd∈CITIES DISTc,d }∀c ∈ CITIES : depdistc = DISTc,dependc

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

47

Constraints

Xbuildc ≤ NUMLOC

c∈CITIES∀c ∈ CITIES : numdepc = |dependd = c|d∈CITIES∀c ∈ CITIES : numdepc ≥ 1 ⇔ buildc = 1

3.9.2

Implementation
To solve this problem, we define a branching strategy with two parts, one for the buildc variables
and a second strategy for the depdistc variables. The latter are enumerated using the
split_domain branching scheme that divides the domain of the branching variable into several
disjoint subsets (instead of assigning a value to the variable). We now pass an array of typecpbranching as the argument to procedure cp_set_branching. The different strategies will beapplied in their order in this array. Since our enumeration strategy does not explicitly include alldecision variables of the problem, Xpress Kalis will enumerate these using the default strategy if
any unassigned variables remain after the application of our search strategy.
model "J-5 Tax office location (CP)"uses "kalis"forward procedure calculate_dist
setparam("KALIS_DEFAULT_LB", 0)declarations
NC = 12
CITIES = 1..NC! Set of cities

DIST: array(CITIES,CITIES) of integer ! Distance matrix
POP: array(CITIES) of integer! Population of cities
LEN: dynamic array(CITIES,CITIES) of integer ! Road lengths
NUMLOC: integer! Desired number of tax offices
D: array(CITIES) of integer! Auxiliary array used in constr. def.
build: array(CITIES) of cpvar
depend: array(CITIES) of cpvar
depdist: array(CITIES) of cpvar
numdep: array(CITIES) of cpvar
totDist: cpvar
Strategy: array(1..2) of cpbranchingend-declarations! 1 if office in city, 0 otherwise! Office on which city depends! Distance to tax office! Number of depending cities per off.
! Objective function variable! Branching strategy

initializations from ’Data/j5tax.dat’
LEN POP NUMLOC
end-initializations! Calculate the distance matrix
calculate_dist
forall(c in CITIES) dobuild(c) <= 1
1 <= depend(c); depend(c) <= NC
min(d in CITIES) DIST(c,d) <= depdist(c)depdist(c) <= max(d in CITIES) DIST(c,d)
numdep(c) <= NC
end-do! Distance from cities to tax offices
forall(c in CITIES) do
forall(d in CITIES) D(d):=DIST(c,d)
element(D, depend(c)) = depdist(c)end-do! Number of cities depending on every office
forall(c in CITIES) occurrence(c, depend) = numdep(c)Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information48

Constraints! Relations between dependencies and offices built
forall(c in CITIES) equiv( build(c) = 1, numdep(c) >= 1 )! Limit total number of officessum(c in CITIES) build(c) <= NUMLOC! Branching strategy
Strategy(1):= assign_and_forbid(KALIS_MAX_DEGREE, KALIS_MAX_TO_MIN, build)
Strategy(2):= split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX,
depdist, true, 5)
cp_set_branching(Strategy)! Objective: weighted total distance
totDist = sum(c in CITIES) POP(c)*depdist(c)! Solve the problem
if not cp_minimize(totDist) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
writeln("Total weighted distance: ", getsol(totDist)," (average per inhabitant: ",getsol(totDist)/sum(c in CITIES) POP(c), ")")
forall(c in CITIES) if(getsol(build(c))>0) thenwrite("Office in ", c, ": ")forall(d in CITIES) write(if(getsol(depend(d))=c, " "+d, ""))
writeln
end-if!----------------------------------------------------------------! Calculate the distance matrix using Floyd-Warshall algorithm
procedure calculate_dist! Initialize all distance labels with a sufficiently large value
BIGM:=sum(c,d in CITIES | exists(LEN(c,d))) LEN(c,d)
forall(c,d in CITIES) DIST(c,d):=BIGM
forall(c in CITIES) DIST(c,c):=0! Set values on the diagonal to 0

! Length of existing road connections
forall(c,d in CITIES | exists(LEN(c,d))) do
DIST(c,d):=LEN(c,d)
DIST(d,c):=LEN(c,d)
end-do! Update shortest distance for every node triple
forall(b,c,d in CITIES | c<d )if DIST(c,d) > DIST(c,b)+DIST(b,d) then
DIST(c,d):= DIST(c,b)+DIST(b,d)
DIST(d,c):= DIST(c,b)+DIST(b,d)
end-ifend-procedure
end-modelThis implementation contains another example of the use of a subroutine in Mosel: thecalculation of the distance data is carried out in the procedure calculate_dist. We thus use asubroutine to structure our model, removing secondary tasks from the main model formulation.

3.9.3

Results
The optimal solution to this problem has a total weighted distance of 2438. Since the region has
a total of 185,000 inhabitants, the average distance per inhabitant is 2438/185 ≈ 13.178 km. The
three offices are established at nodes 1, 6, and 11. The first serves cities 1, 2, 5, 7, the office inFair Isaac Corporation and Artelys SA Confidential and Proprietary Information

49

Constraints

node 6 cities 3, 4, 6, 9, and the office in node 11 cities 8, 10, 11, 12.

3.10

cycle: Paint production
In this section we work once more with the paint production problem from Section 3.8. The
objective of this problem is to determine a production cycle of minimal length for a given set ofjobs with sequence-dependent cleaning times between every pair of jobs.

3.10.1Model formulation
The problem formulation in Section 3.8 uses ’all-different’ constraints to ensure that every job
occurs once only, calculates the duration of cleaning times with ’element’ constraints, andintroduces auxiliary variables and constraints to prevent subcycles in the production sequence. All
these constraints can be expressed by a single constraint relation, the ’cycle’ constraint.
Let JOBS = {1, . . . , NJ} be the set of batches to produce, DURj the processing time for batch j, and
CLEANij the cleaning time between the consecutive batches i and j. As before we define decisionvariables succj taking their values in JOBS, to indicate the successor of every job. The complete
model formulation is the following,

minimize

X

DURj + cleantimej∈JOBS∀j ∈ JOBS : succj ∈ JOBS\{j}cleantime = cycle((succj )j∈JOBS , (CLEANij )i,j∈JOBS )where ’cycle’ stands for the relation ’sequence into a single cycle without subcycles orrepetitions’. The variable cleantime equals the total duration of the cycle.

3.10.2

Implementation
The Mosel model using the cycle constraint looks as follows.
model "B-5 Paint production (CP)"uses "kalis"
setparam("KALIS_DEFAULT_LB", 0)declarations
NJ = 5
JOBS=0..NJ-1! Number of paint batches (=jobs)

DUR: array(JOBS) of integer! Durations of jobs
CLEAN: array(JOBS,JOBS) of integer ! Cleaning times between jobs
CB: array(JOBS) of integer! Cleaning times after a batch
succ: array(JOBS) of cpvar
cleanTime,cycleTime: cpvar
end-declarations! Successor of a batch! Durations of cleaning / complete cycle

initializations from ’Data/b5paint.dat’
DUR CLEAN
end-initializations
forall(j in JOBS) do
0 <= succ(j); succ(j) <= NJ-1; succ(j) <> jend-doFair Isaac Corporation and Artelys SA Confidential and Proprietary Information

50

Constraints! Assign values to ’succ’ variables as to obtain a single cycle! ’cleanTime’ is the sum of the cleaning times
cycle(succ, cleanTime, CLEAN)! Objective: minimize the duration of a production cycle
cycleTime = cleanTime +sum(j in JOBS) DUR(j)! Solve the problem
if not cp_minimize(cycleTime) thenwriteln("Problem is infeasible")exit(1)
end-ifcp_show_stats! Solution printing
writeln("Minimum cycle time: ", getsol(cycleTime))
writeln("Sequence of batches:\nBatch Duration Cleaning")
first:=1
repeatwriteln(" ", first, strfmt(DUR(first),8),
strfmt(CLEAN(first,getsol(succ(first))),9) )first:=getsol(succ(first))
until (first=1)
end-model

Notice that we have renumbered the tasks, starting the index range with 0, to conform with the
input format expected by the cycle constraint.

3.10.3Results
The optimal solution to this problem has a minimum cycle time of 243 minutes, resulting from
202 minutes of (incompressible) processing time and 41 minutes of cleaning.
The problem statistics produced by Xpress Kalis for a model run reveal that the ’cycle’ version ofthis model is the most efficient way of representing and solving the problem: it takes fewer
nodes and a shorter execution time than the two versions of Section 3.8.

3.11

Generic binary constraints: Euler knight tour
Our task is to find a tour on a chessboard for a knight figure such that the knight moves throughevery cell exactly once and at the end of the tour returns to its starting point. The path of theknight must follow the standard chess rules: a knight moves either one cell vertically and two
cells horizontally, or two cells in the vertical and one cell in the horizontal direction, as shown in
the following graphic (Figure 3.3):

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

51

Constraints

K

Figure 3.3: Permissible moves for a knight

3.11.1Model formulation
To represent the chessboard we number the cells from 0 to N-1, where N is the number of cells of
the board. The path of the knight is defined by N variables posi that indicate the ith position of
the knight on its tour.
The first variable is fixed to zero as the start of the tour. Another obvious constraint we need tostate is that all variables posi take different values (every cell of the chessboard is visited exactlyonce):
all-different(pos1 , . . . , posN )We are now left with the necessity to establish a constraint relation that checks whether
consecutive positions define a valid knight move. To this aim we define a new binary constraint’valid_knight_move’ that checks whether a given pair of values defines a permissible moveaccording to the chess rules for knight moves. Vertically and horizontally, the two values must be
no more than two cells apart and the sum of the vertical and horizontal difference must be equal
to three. The complete model then looks as follows.
∀i ∈ PATH = {1, . . . , N} : posi ∈ {0, . . . , N − 1}
pos1 = 0
all-different(pos1 , . . . , posN )∀i ∈ POS = {1, . . . , N − 1} : valid_knight_move(posi , posi+1 )valid_knight_move(posN , pos1 )3.11.2

Implementation
Testing whether moving from position a to position b is a valid move for a knight figure can bedone with the following function valid_knight_move where ’div’ means integer division without
rest and ’mod’ is the rest of the integer division:

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

52

Constraints

function valid_knight_move(a,b)
xa := a div E
ya := a mod E
xb := b div E
yb := b mod E
deltax := |xa − xb|
deltay := |ya − yb|return ((deltax ≤ 2) and (deltay ≤ 2) and (deltax + deltay = 3))
end-function

The following Mosel model defines the user constraint function valid_knight_move as theimplementation of the new binary constraints on pairs of movep variables (the constraints are
established with generic_binary_constraint).
model "Euler Knight Moves"uses "kalis"parameters
S = 8
NBSOL = 1
end-parameters! Number of rows/columns! Number of solutions sought

forward procedure print_solution(sol: integer)
N:= S * S
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", N-1)
declarations
PATH = 1..N
pos: array(PATH) of cpvar
end-declarations! Total number of cells! Cells on the chessboard! Cell at position p in the tour

! Fix the start position
pos(1) = 0! Each cell is visited once
all_different(pos, KALIS_GEN_ARC_CONSISTENCY)! The path of the knight obeys the chess rules for valid knight moves
forall(i in 1..N-1)
generic_binary_constraint(pos(i), pos(i+1), "valid_knight_move")generic_binary_constraint(pos(N), pos(1), "valid_knight_move")! Setting enumeration parameters
cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN,
pos, 14))! Search for up to NBSOL solutions
solct:= 0
while (solct<NBSOL and cp_find_next_sol) do
solct+=1
cp_show_stats
print_solution(solct)
end-do! **** Test whether the move from position a to b is admissible ****
function valid_knight_move(a:integer, b:integer): boolean
declarations
xa,ya,xb,yb,delta_x,delta_y: integer
end-declarations
xa := a div S
ya := a mod S

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

53

Constraints

xb := b div S
yb := b mod S
delta_x := abs(xa-xb)
delta_y := abs(ya-yb)
returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
end-function!****************************************************************! Solution printing
procedure print_solution(sol: integer)
writeln("Solution ", sol, ":")
forall(i in PATH)
write(getval(pos(i)), if(i mod 10 = 0, "\n ", ""), " -> ")writeln("0")
end-procedure
end-model

The branching scheme used in this model is the probe_assign_var heuristic, in combination withthe variable selection KALIS_SMALLEST_MIN (choose variable with smallest lower bound) and thevalue selection criterion KALIS_MAX_TO_MIN (from largest to smallest domain value). Anothersearch strategy that was found to work well (though slower than the strategy in the code listing)iscp_set_branching(assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN, pos))

Our model defines two parameters. It is thus possible to change either the size of the chessboard(S) or the number of solutions sought (NBSOL) when executing the model without having tomodify the model source.

3.11.3Results
The first solution printed out by our model is the following tour.
0 -> 17 -> 34 -> 51 -> 36 -> 30 -> 47 -> 62 -> 45 -> 39-> 54 -> 60 -> 43 -> 33 -> 48 -> 58 -> 52 -> 35 -> 41 -> 56-> 50 -> 44 -> 38 -> 55 -> 61 -> 46 -> 63 -> 53 -> 59 -> 49-> 32 -> 42 -> 57 -> 40 -> 25 -> 8 -> 2 -> 19 -> 4 -> 14-> 31 -> 37 -> 22 -> 7 -> 13 -> 28 -> 18 -> 24 -> 9 -> 3-> 20 -> 26 -> 16 -> 1 -> 11 -> 5 -> 15 -> 21 -> 6 -> 23-> 29 -> 12 -> 27 -> 10 -> 0

3.11.4

Alternative implementation
Whereas the aim of the model above is to give an example of the definition of user constraints, it
is possible to implement this problem in a more efficient way using the model developed for thecyclic scheduling problem in Section 3.10. The set of successors (domains of variables succp ) can becalculated using the same algorithm that we have used above in the implementation of theuser-defined binary constraints.
Without repeating the complete model definition at this place, we simply display the model
formulation, including the calculation of the sets of possible successors (procedure
calculate_successors, and the modified procedure print_sol for solution printout. We use a
simpler version of the ’cycle’ constraints than the one we have seen in Section 3.10, its only
argument is the set of successor variables—there are no weights to the arcs in this problem.
model "Euler Knight Moves"uses "kalis"parameters
S = 8! Number of rows/columns

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

54

Constraints

NBSOL = 1
end-parameters! Number of solutions sought

forward procedure calculate_successors(p: integer)
forward procedure print_solution(sol: integer)
N:= S * S
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", N)
declarations
PATH = 0..N-1
succ: array(PATH) of cpvar
end-declarations! Total number of cells! Cells on the chessboard! Successor of cell p! Calculate set of possible successors
forall(p in PATH) calculate_successors(p)! Each cell is visited once, no subtours
cycle(succ)! Search for up to NBSOL solutions
solct:= 0
while (solct<NBSOL and cp_find_next_sol) do
solct+=1
cp_show_stats
print_solution(solct)
end-do! **** Calculate possible successors ****
procedure calculate_successors(p: integer)
declarations
SuccSet: set of integer! Set of successors
end-declarations
xp := p div S
yp := p mod S
forall(q in PATH) do
xq := q div S
yq := q mod S
delta_x := abs(xp-xq)
delta_y := abs(yp-yq)
if (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3) then
SuccSet +={q}end-ifend-dosetdomain(succ(p), SuccSet)
end-procedure!****************************************************************! **** Solution printing ****
procedure print_solution(sol: integer)
writeln("Solution ", sol, ":")
thispos:=0
nextpos:=getval(succ(0))
ct:=1while (nextpos<>0) do
write(thispos, if(ct mod 10 = 0, "\n ", ""), " -> ")val:=getval(succ(thispos))thispos:=nextpos
nextpos:=getval(succ(thispos))ct+=1
end-dowriteln("0")
end-procedure

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

55

Constraints

end-model

The calculation of the domains for the succp variables reduces these to 2-8 elements (as comparedto the N = 64 values for every posp variables), which clearly reduces the search space for thisproblem.
This second model finds the first solution to the problem after 131 nodes taking just a fraction of
a second to execute on a standard PC whereas the first model requires several thousand nodes
and considerably longer running times. It is possible to reduce the number of branch-and-boundnodes even further by using yet another version of the ’cycle’ constraint that works with successor
and predecessor variables. This version of ’cycle’ performs a larger amount of propagation, at theexpense of (slightly) slower execution times for our problem. The procedure
calculate_successors now sets the domain of predp to the same values as succp for all cells p.
declarations
PATH = 0..N-1
succ: array(PATH) of cpvar
pred: array(PATH) of cpvar
end-declarations! Cells on the chessboard! Successor of cell p! Predecessor of cell p! Calculate sets of possible successors and predecessors
forall(p in PATH) calculate_successors(p)! Each cell is visited once, no subtours
cycle(succ, pred)

Figure 3.4 shows the graphical display of a knight’s tour created with the user graph drawing
functionality.

Figure 3.4: Knight’s tour solution graph3.11.5

Alternative implementation 2
Yet more efficient (a similar number of nodes with significantly shorter running times) is thefollowing model version using the ’cycle’ constraint described in Section 3.10. Since travel times
from one position to the next are irrelevant in this model we simply fix all coefficients for the’cycle’ constraint to a constant and constrain the cycle length to the corresponding value.
All else, including the calculation of the sets of possible successors (procedure

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

56

Constraints

calculate_successors, and the procedure print_sol for solution printout is copied unchanged
from the previous model.
model "Euler Knight Moves"uses "kalis"parameters
S = 8
NBSOL = 1
end-parameters! Number of rows/columns! Number of solutions sought

forward procedure calculate_successors(p: integer)
forward procedure print_solution(sol: integer)
N:= S * S
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", N)
declarations
PATH = 0..N-1
succ: array(PATH) of cpvar
end-declarations! Total number of cells! Cells on the chessboard! Successor of cell p! Calculate set of possible successors
forall(p in PATH) calculate_successors(p)! Each cell is visited once, no subtours
cycle(succ)! Search for up to NBSOL solutions
solct:= 0
while (solct<NBSOL and cp_find_next_sol) do
solct+=1
cp_show_stats
print_solution(solct)
end-do! **** Calculate possible successors ****
procedure calculate_successors(p: integer)
declarations
SuccSet: set of integer! Set of successors
end-declarations
xp := p div S
yp := p mod S
forall(q in PATH) do
xq := q div S
yq := q mod S
delta_x := abs(xp-xq)
delta_y := abs(yp-yq)
if (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3) then
SuccSet +={q}end-ifend-dosetdomain(succ(p), SuccSet)
end-procedure!****************************************************************! **** Solution printing ****
procedure print_solution(sol: integer)
writeln("Solution ", sol, ":")
thispos:=0
nextpos:=getval(succ(0))
ct:=1while (nextpos<>0) do
write(thispos, if(ct mod 10 = 0, "\n ", ""), " -> ")Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

57

Constraints

val:=getval(succ(thispos))thispos:=nextpos
nextpos:=getval(succ(thispos))ct+=1
end-dowriteln("0")
end-procedure
end-model

3.12

Symmetry breaking: scenes allocation problem
A movie producer has to decide when to shoot the scenes for a movie. Every scene involves a
specific set of actors. A least 2 scenes and at most 5 scenes can be filmed per day. All actors of ascene must, of course, be present on the day the scene is shot. The actors have fees representing
the amount they are paid per day they spend in the studio. The movie producer wishes tominimize the production costs incurred through the actors’ fees.

3.12.1Model formulation
Let SCENES denote the set of scenes, ACTORS all the actors taking part in the movie, and DAYS
the set of eligible days. The decision variables shoots indicating which day a scene is shot taketheir values in the set DAYS. A second set of variables are the binary indicators workad that takethe value 1 if actor a works on the day d.
Every day, the number of scenes shot needs to lie within the interval of minimum and maximum
permissible numbers (MINSCENESHOTd , . . . , MAXSCENESHOTd ). We also need to formulate theimplication ’if an actor works on a day, then this day is due’, or stated otherwise ’if a scene thatthe actor appears in is scheduled on day d, then the actor is working on this day’:∀s ∈ SCENES : shoots ∈ DAYS∀a ∈ ACTORS, d ∈ DAYS : workad ∈ {0, 1}∀d ∈ DAYS : |shoots = d|s∈SCENES ∈ {MINSCENESHOTd , . . . , MAXSCENESHOTd }∀a ∈ ACTORS, s ∈ APPEARa , d ∈ DAYS : shoots = d ⇒ workad = 1
The objective function is to minimize the total cost incurred through actors’ fees:Xminimize
DAILYFEEa · workada∈ACTORS,d∈DAYS

Symmetry breaking constraints: it is easy to see that days are entirely interchangeable (e.g. allscenes from day 1 could be exchanged with those assigned to day 2 without any impact on the
total cost). Indeed, any permuation of days with the same scene allocations will result in the same
total cost. So it might be worthwhile to investigate how we can reduce the number of
permutations in order to shorten solving times.
Consider a scene s1 : it needs to be assigned some specific day, say day 1 (all days areinterchangeable at this point). Now consider a second scene s2 : it can either be assigned the same
day as the first or some other (additional) day—all other days being interchangeable at this point
we can assume this will be day 2. Generalizing this observation, for any scene s we can limit its
value set to the days already used by scenes 1, . . . , s − 1 plus one additional day, that is:shoot1 = 1∀s ∈ SCENES, s > 1 : shoots ≤ maximum(shoot1 , . . . , shoots−1 ) + 1

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

58

Constraints

3.12.2

Implementation
For the implementation of the lower and upper bounds on the number of scenes to be shot per
day we use a global cardinality (’distribute’) constraint that distributes the scenes to be shot over
the available days.
For the formulation of the symmetry breaking constraints some auxiliary objects are introduced,
namely the list shootListSb of the predecessors of scene s (that is, shoot1 , . . . , shoots−1 ) in
enumeration order of the set of scenes, and an additional decision variable maxShootSbs definedas the maximum value among the variables in this list.
model "Scenes Allocation (CP)"uses "kalis"! Gain access to the Xpress Kalis solver! **** Data ****
declarations
SCENES: range! Set of scene numbers
DAYS = 1..5
! Day numbers when the scenes can be shot
ACTORS: set of string! Set of actors
DAILYFEE: array(ACTORS) of integer! Daily fees of actors
CAST: array(SCENES) of set of string! Cast of actors per scene
APPEAR: array(ACTORS) of set of integer ! Scenes where an actor appears
MINSCENESHOT: array(DAYS) of integer! Minimum number of scenes per day
MAXSCENESHOT: array(DAYS) of integer! Maximum number of scenes per day
end-declarations! Initialize actors DAILYFEE
DAILYFEE::(["Georges Clooney","Penelope Cruz","Leonardo DiCaprio","Nathalie Portman","Ryan Gosling","Monica Bellucci","Javier Bardem","Keira Knightley","Vincent Cassel","Marion Cotillard","Emma Watson"])[264, 250, 303,
40, 75, 93, 87, 57, 74, 33, 95]! Initialize minimum and maximum numbers of scenes that have to be shot per day
MINSCENESHOT::([1,2,3,4,5])[2,2,2,2,2]
MAXSCENESHOT::([1,2,3,4,5])[5,5,5,5,5]! Initialize sets of actors per scene
CAST(1):= {"Monica Bellucci"}
CAST(2):= {"Georges Clooney","Monica Bellucci","Ryan Gosling","Nathalie Portman"}
CAST(3):= {"Keira Knightley","Leonardo DiCaprio","Vincent Cassel","Ryan Gosling"}
CAST(4):= {"Penelope Cruz","Vincent Cassel"}
CAST(5):= {"Vincent Cassel","Javier Bardem","Georges Clooney","Keira Knightley","Marion Cotillard"}
CAST(6):= {"Emma Watson","Keira Knightley","Javier Bardem","Leonardo DiCaprio","Marion Cotillard"}
CAST(7):= {"Penelope Cruz","Georges Clooney"}
CAST(8):= {"Vincent Cassel","Nathalie Portman"}
CAST(9):= {"Penelope Cruz","Keira Knightley","Vincent Cassel","Leonardo DiCaprio","Emma Watson"}
CAST(10):= {"Penelope Cruz","Keira Knightley","Leonardo DiCaprio","Georges Clooney"}
CAST(11):= {"Georges Clooney"}
CAST(12):= {"Monica Bellucci","Emma Watson","Keira Knightley","Nathalie Portman","Ryan Gosling"}
CAST(13):= {"Monica Bellucci","Nathalie Portman","Penelope Cruz","Georges Clooney"}
CAST(14):= {"Javier Bardem","Leonardo DiCaprio"}
CAST(15):= {"Emma Watson","Nathalie Portman","Keira Knightley","Georges Clooney"}
CAST(16):= {"Leonardo DiCaprio","Keira Knightley","Penelope Cruz","Vincent Cassel"}
CAST(17):= {"Leonardo DiCaprio","Georges Clooney","Ryan Gosling"}
CAST(18):= {"Leonardo DiCaprio","Keira Knightley","Monica Bellucci","Emma Watson"}
CAST(19):= {"Penelope Cruz"}! Calculate appearance in scenes for each actor
forall(a in ACTORS) APPEAR(a):= union(s in SCENES | a in CAST(s)) {s}! **** Problem statement ****
declarations
shoot: array(SCENES) of cpvar ! Decision var.s: day when a scene will be shot
work: array(ACTORS,DAYS) of cpvar! Decision var.s: presence of actor i on day k
totalCost: cpvar! Objective
shootListSb: cpvarlist! List of shoot variables for symmetry breaking

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

59

Constraints

maxShootSb: array(SCENES) of cpvar! Max. value of shoot variables list
! per scene (formulation of symmetry breaking)end-declarations
setparam("kalis_default_ub", 200000000)! Kalis default upper bound! **** Domain definition ****! Each shoot variable takes a value from the set DAYS
forall(s in SCENES) do
setname(shoot(s),"shoot["+s+"]")
setdomain(shoot(s), DAYS)
end-do! The total cost has a lower bound of $0 and an upper bound of $200000000
setname(totalCost, "totalCost")
setdomain(totalCost, 0, 200000000)! work : binary variables that indicate if actor i is present on day k
forall(a in ACTORS, d in DAYS) do
setname(work(a,d), "work["+a+","+d+"]")
setdomain(work(a,d), 0, 1)
end-do! **** Constraints ****
! Global Cardinality Constraint to express lower and upper bounds on the! number of scenes that have to be shot each day
distribute(shoot,DAYS,MINSCENESHOT,MAXSCENESHOT)! When an actor works on a day, this day is due
forall(a in ACTORS, s in APPEAR(a), d in DAYS)
implies(shoot(s)=d, work(a,d)=1)! Symmetry breaking
shoot(1) = 1
forall(s in SCENES | s > 1) doshootListSb += shoot(s-1)
maxShootSb(s) = maximum(shootListSb)
shoot(s) <= maxShootSb(s)+1
end-do! All days are interchangeable at this stage! For a scene s, we need to consider! just the previously used days + 1:
! D(s)={1,...,max(shoot(1),...,shoot(s-1))+1}! Objective function
totalCost = sum(a in ACTORS, d in DAYS) DAILYFEE(a)*work(a,d)! Branching strategy
cp_set_branching(assign_and_forbid(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX, shoot))! **** Problem solving and solution reporting ****
if cp_minimize(totalCost) then! Display total costwriteln("Total cost: ", getsol(totalCost))! Display scenes scheduled on each day
forall(d in DAYS) do
write("\nDay ", d, ": scenes ")forall(s in SCENES | getsol(shoot(s))=d) write(s, " ")end-do! Display days worked by each actor
forall(a in ACTORS) do
write("\n", strfmt(a,-16), " :")forall(d in DAYS | getsol(work(a,d)) = 1) write("end-dowritelnelsewriteln("No solution found.")end-ifDay ",d)end-model

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

60

Constraints

3.12.3Results
The model shown above generates the following output:
Total cost: 3497
Day 1: scenes 1 8
Day 2: scenes 2 5 11 12 15
Day 3: scenes 3 7 10 13 17
Day 4: scenes 4 19
Day 5: scenes 6 9 14 16 18
Georges Clooney : Day 2 Day 3
Penelope Cruz
: Day 3 Day 4
Leonardo DiCaprio: Day 3 Day 5
Nathalie Portman : Day 1 Day 2
Ryan Gosling: Day 2 Day 3
Monica Bellucci : Day 1 Day 2
Javier Bardem: Day 2 Day 5
Keira Knightley : Day 2 Day 3
Vincent Cassel: Day 1 Day 2
Marion Cotillard : Day 2 Day 5
Emma Watson: Day 2 Day 5

Day 5
Day 3
Day 3

Day 5

Day 5
Day 3

Day 4

Day 5

Without the symmetry breaking constraints, the solving time is more than one order ofmagnitude longer (both for finding the optimal solution and proving its optimality) than whenthese constraints are included in the model.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

61

C HAPTER 4

Enumeration
This chapter gives an overview on different issues related to the definition of search strategies
with Xpress Kalis, namely

predefined search strategies,means of interrupting and restarting the enumeration,

search callbacks, andthe definition of user search strategies.

The last section discusses what may be done in the case of an infeasible constraint system:

4.1

analyzing infeasibility and handling conflicts

Predefined search strategies
With Xpress Kalis a branching strategy is composed of three components:
The branching scheme determines the shape of the search tree, this includes exhaustive
schemes like assign_var and split_domain (enumeration of decision variables),settle_disjunction (enumeration over constraints), and task_serialize (enumeration oftasks in scheduling problems), or potentially incomplete searches with probe_assign_var orprobe_settle_disjunction.



The variable selection strategy determines the choice of the branching variables. Predefined
selection criteria include
KALIS_INPUT_ORDER

variables in the given order,

KALIS_LARGEST_MAX

variable with largest upper bound,

KALIS_LARGEST_MIN

variable with largest lower bound,

KALIS_MAX_DEGREE

variable occurring in the largest number of constraints,

KALIS_MAXREGRET_LB

variable with largest difference between its lower boundand second-smallest domain value,

KALIS_MAXREGRET_UB

variable with largest difference between its upper boundand second-largest domain value,

KALIS_RANDOM_VARIABLE

random variable choice,

KALIS_SDOMDEG_RATIO

variable with smallest ratio domain size / degree,

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

62

Enumeration

KALIS_SMALLEST_DOMAINKALIS_SMALLEST_MAX
KALIS_SMALLEST_MIN
KALIS_WIDEST_DOMAIN

variable with smallest number of domain values/smallest
domainintervall,variable with smallest upper bound,variable with smallest lower bound).
variable with largest number of domain values/largest
domain interval,

The user may also define his own variable selection strategy (see Section 4.4.3 below).


The value selection strategy determines the choice of the branching value once the variable
to be branched on is known. The following predefined selection criteria are available.
KALIS_MAX_TO_MIN
KALIS_MIDDLE_VALUEKALIS_MIN_TO_MAXKALIS_NEAREST_VALUEKALIS_RANDOM_VALUE

enumeration of values in decreasing order,
enumerate first values in the middle of the variable’s
domain,enumeration of values in increasing order,
choose the value closest to a target value previously
specified with settarget,choose a random value out of the variable’s domain.

The predefined criteria can be replaced by the user’s own value selection strategy (seeSection 4.4.3 below).
Depending on the choice of the branching scheme, it may be possible to specify additionalparameters to configure the enumeration. The reader is referred to the Xpress Kalis reference
manual for further detail. In the case of constraint branching, there is quite obviously no variableor branching value selection. The special case of task-based branching strategies (branching
scheme task_serialize) is discussed in Section 5.7. Enumeration of continuous variables (typecpfloatvar) always uses the branching scheme split_domain with the KALIS_SMALLEST_DOMAIN or
KALIS_WIDEST_DOMAIN variable selection (the former is used by the default strategy, the latteroften works better in purely continuous problems) and only a subset of the value selection
strategies listed above.
Branching strategies may be defined for certain specified variables (or, where applicable,
constraints or tasks), or, if the corresponding argument of the branching scheme function is leftout, are applied to all decision variables in a model (see, for instance, model b4seq_ka.mos in
Section 3.5).
If the user’s model does not specify any branching strategy, then Xpress Kalis will apply default
strategies to enumerate all variables in the model. Even if one does not wish to change thedefault enumeration (for discrete variables: ‘smallest domain first’ and ‘smallest value first’), it
may still be desirable to define a branching strategy to fix a certain order for the enumeration ofdifferent groups of decision variables. The previous chapter contains several examples of this: inthe model a4sugar_ka.mos (Section 3.6) we define an enumeration over some of the variables ofa model, giving them thus preference over the remainder. In model j5tax_ka.mos (Section 3.9)
we have seen an example of a search strategy composed of different enumerations for groups ofdecision variables.
If a model contains both, discrete and continuous variables (cpvar and cpfloatvar) the default
strategies enumerate first the discrete and then the continuous variables.

4.2

Interrupting and restarting the search
When solving large applications it is often not possible to enumerate the complete search tree
within a reasonable time span. Several stopping criteria are therefore available in Xpress Kalis tointerrupt the search. These are

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

63Enumeration

KALIS_MAX_BACKTRACKS

maximum number of backtracks,

KALIS_MAX_COMPUTATION_TIME

limit on total time spent in search,

KALIS_MAX_DEPTH

maximum search tree depth,

KALIS_MAX_NODES

maximum number of nodes to explore,

KALIS_MAX_SOLUTIONS

maximum number of solutions,

KALIS_OPT_ABS_TOLERANCE

absolute difference between the objective function value in asolution and its best possible value (= current upper bound on
objective function in maximization problems and lower boundwith minimization),

KALIS_OPT_REL_TOLERANCE

relative difference between the objective function value in asolution and its best possible value (= current upper bound on
objective function in maximization problems and lower boundwith minimization).

These parameters are accessed with the Mosel functions setparam and getparam (see, forexample, the output of problem statistics in model sudoku_ka.mos in Section 3.3, and the searchtime limit set in the model freqasgn.mos of Section 3.4).
In optimization problems, after a solution has been found the search continues from this point
unless the setting of parameter KALIS_OPTIMIZE_WITH_RESTART is changed. The same is true if thesearch is interrupted by means of one of the above-named criteria and then continued, forinstance with a different search strategy. To restart the search from the root node the procedure
cp_reset_search needs to be called (as an example, see model freqasgn.mos in Section 3.4)

4.3

Callbacks
During the search the user’s model may interact with the solver at certain predefined points bymeans of callback functions. This functionality is particularly useful to retrieve solution
information for intermediate solutions during an optimization run as shown in the model
freqasgn.mos (Section 3.4). Other than this solution callback, the user may set functions that will
be called at every branch or at every node (see the Xpress Kalis reference manual for further
detail).

4.4

User-defined enumeration strategies
The following problem description is taken from Section 14.1 of ‘Applications of optimization
with Xpress-MP’.
An operator needs to be assigned to each of the six machines in a workshop. Six workers havebeen pre-selected. Everyone has undergone a test of her productivity on every machine. Table 4.1
lists the productivities in pieces per hour. The machines run in parallel, that is, the total
productivity of the workshop is the sum of the productivities of the people assigned to themachines.
The objective is to determine an assignment of workers to machines that maximizes the total
productivity. We may start by calculating a (non-optimal) heuristic solution using the following
fairly natural method: choose the assignment p → m with the highest productivity, cross out theline p and the column m (since the person has been placed and the machine has an operator),and restart this process until we have assigned all persons—the resulting assignment ishighlighted in bold print in the data table. However, our aim really is to solve this problem tooptimality for the case of parallel machines and also for machines working in series.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

64Enumeration

Table 4.1: Productivity in pieces per hour

4.4.1

Workers

1

2

Machines
3
4

5

6

1
2
3
4
5
6

13
18
20
23
28
19

24
25
20
26
33
36

31
30
27
28
34
25

40
43
34
37
38
45

29
22
33
30
20
24

19
15
25
18
17
27

Model formulation
This problem type is well known under the name of the assignment problem. Let PERS be the setof workers, MACH the set of machines (both of the same size N), and OUTPpm the productivity ofworker p on machine m. We define N integer variables assignp taking values in the set ofmachines, where assignp denotes the number of the machine to which the person p is assigned.
The fact that a person p is assigned to a single machine m and a machine m is operated by asingle person p is then expressed by the constraint that all variables assignp take different values.
∀p ∈ PERS : assignp ∈ MACH!
[
all-different
assignpm∈MACHFurthermore, let outputp denote the output produced by person p. The values of these variables
are obtained as discrete functions in the assignp variables:∀p ∈ PERS : outputp = OUTPp,assignp
4.4.1.1

Parallel machine assignment

The objective function to be maximized sums the outputp variables.
Xmaximize
outputpp∈PERS

Certain assignments may be infeasible. In such a case, the value of the corresponding machineneeds to be removed from the domain of the variable assignp .
4.4.1.2

Machines working in series

If the machines work in series, the least productive worker on the machine she has been assigned
to determines the total productivity of the workshop. An assignment will still be described by Nvariables assignp and an all-different constraint on these variables. We also have the outputp
variables with the constraints linking them to the values of the assignp variables from theprevious model. To this we add a variable pmin for the minimum productivity. The objective is tomaximize pmin. This type of optimization problem where one wants to maximize a minimum iscalled maximin, or bottleneck.
maximize pmin
pmin = minimump∈PERS (outputp )Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

65Enumeration

4.4.2

Implementation
The following Mosel program first implements and solves the model for the case of parallelmachines. Afterwards, we define the variable pmin that is required for solving the problem forthe case that the machines work in series.
model "I-1 Personnel assignment (CP)"uses "kalis"forward procedure parallel_heurforward procedure print_sol(text1,text2:string, objval:integer)
declarations
PERS = 1..6
MACH = 1..6
OUTP: array(PERS,MACH) of integer
end-declarations! Personnel! Machines! Productivity

initializations from ’Data/i1assign.dat’
OUTP
end-initializations! **** Exact solution for parallel machines ****
declarations
assign: array(PERS) of cpvar
output: array(PERS) of cpvar
totalProd: cpvar
O: array(MACH) of integer
Strategy: cpbranchingend-declarations! Machine assigned to a person! Productivity of every person! Total productivity! Auxiliary array for constraint def.
! Branching strategy

forall(p in PERS) setdomain(assign(p), MACH)! Calculate productivity per worker
forall(p in PERS) do
forall(m in MACH) O(m):= OUTP(p,m)
element(O, assign(p)) = output(p)end-do! Calculate total productivity
totalProd = sum(p in PERS) output(p)! One person per machine
all_different(assign)! Branching strategy
Strategy:= assign_var(KALIS_LARGEST_MAX, KALIS_MAX_TO_MIN, output)
cp_set_branching(Strategy)! Solve the problem
if cp_maximize(totalProd) thenprint_sol("Exact solution (parallel assignment)", "Total", getsol(totalProd))
end-if! **** Exact solution for serial machines ****
declarations
pmin: cpvar
end-declarations! Minimum productivity! Calculate minimum productivity
pmin = minimum(output)! Branching strategy
Strategy:= assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN, output)
cp_set_branching(Strategy)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

66

Enumeration! Solve the problem
if cp_maximize(pmin) thenprint_sol("Exact solution (serial machines)", "Minimum", getsol(pmin))end-ifWhen the solution to the parallel assignment problem is found, we print out the solution andre-start the search with a new branching strategy and a new objective function. Since the firstsearch has finished completely (no interruption by a time limit, etc.) there is no need to reset thesolver between the two runs.
The branching strategy chosen for the parallel assignment problem is inspired by the intuitive
procedure described in the introduction to Section 4.4: instead of enumerating the possible
assignments of workers to machines (= enumeration of the assignp variables) we define anenumeration over the outputp variables, choosing the variable with the largest remaining value(KALIS_LARGEST_MAX) and branch on its values in decreasing order (KALIS_MAX_TO_MIN). For thesecond problem we need to proceed differently: to avoid being left with a small productivity
value for some worker p we pick first the outputp variable with the smallest lower bound(KALIS_SMALLEST_MIN); again we enumerate the values starting with the largest one.
The following procedure parallel_heur may be added to the above program. It heuristicallycalculates a (non-optimal) solution to the parallel assignment problem using the intuitive
procedure described in the introduction to Section 4.4.
procedure parallel_heurdeclarations
ALLP, ALLM: set of integer
HProd: integer
pmax,omax,mmax: integer
end-declarations! Copies of sets PERS and MACH
! Total productivity value! Copy the sets of workers and machines
forall(p in PERS) ALLP+={p}forall(m in MACH) ALLM+={m}! Assign workers to machines as long as there are unassigned persons
while (ALLP<>{}) do
pmax:=0; mmax:=0; omax:=0! Find the highest productivity among the remaining workers and machines
forall(p in ALLP, m in ALLM)
if OUTP(p,m) > omax thenomax:=OUTP(p,m)
pmax:=p; mmax:=m
end-ifassign(pmax) = mmax
ALLP-={pmax}; ALLM-={mmax}
end-do! Assign chosen machine to person pmax
! Remove person and machine from sets

writeln("Heuristic solution (parallel assignment):")forall(p in PERS)
writeln(" ",p, " operates machine ", getval(assign(p))," (",getval(output(p)), ")")
writeln(" Total productivity: ", getval(totalProd))
end-procedure

The model is completed with a procedure for printing out the solution in a properly formatted
way.
procedure print_sol(text1,text2:string, objval:integer)
writeln(text1,":")
forall(p in PERS)
writeln(" ",p, " operates machine ", getsol(assign(p))," (",getsol(output(p)), ")")

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

67Enumeration

writeln(" ", text2, " productivity: ", objval)
end-procedure
end-model

4.4.3

User searchInstead of using predefined variable and value selection criteria as shown in all previous model
implementations we may choose to define our own search heuristics. We now show how to
implement the search strategies from the previous model ‘by hand.’ In our implementation we
add each time a second criterion for breaking ties in cases where the main criterion applies toseveral variables at a time.
Variable selection: the variable selection function has a fixed format—it receives as its argument
a list of variables of type cpvarlist and it returns an integer, the list index of the chosenbranching variable. The list of variables passed into the function may contain variables that are
already instantiated. As a first step in our implementation we, therefore, determine the set Vsetof yet uninstantiated variables—or to be more precise, the set of their indices in the list. The
entries of the list of variables are accessed with the function getvar. Among the uninstantiatedvariables we calculate the set of variables Iset with the largest upper bound value (using
function getub). Finally, among these variables, we choose the one with the smallest
second-largest value (this corresponds to a maximum regret strategy). Predecessor (next-smallest)
values in the domain of a decision variable are obtained with the function getprev. Inversely, we
have function getnext for an enumeration of domain values in ascending order. The chosen index
value is assigned to returned as the function’s return value.
function varchoice(Vars: cpvarlist): integer
declarations
Vset,Iset: set of integer
end-declarations! Set of uninstantiated variables
forall(i in 1..getsize(Vars))
if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
if Vset={} thenreturned:= 0else! Get the variable(s) with largest upper bounddmax:= max(i in Vset) getub(getvar(Vars,i))
forall(i in Vset)
if getub(getvar(Vars,i)) = dmax then Iset+= {i}; end-if
dmin:= dmax
! Choose variable with smallest next-best value among those indexed by ’Iset’
forall(i in Iset) do
prev:= getprev(getvar(Vars,i),dmax)
if prev < dmin thenreturned:= idmin:= prev
end-ifend-doend-ifend-function

The variable selection strategy varchoicemin for the second optimization run (serial machines) is
implemented in a similar way. We first establish the set of variables with the smallest lower
bound value (using getlb), Iset; among these we choose the variable with the smallest upperbound (getub).
function varchoicemin(Vars: cpvarlist): integer
declarations

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

68Enumeration

Vset,Iset: set of integer
end-declarations! Set of uninstantiated variables
forall(i in 1..getsize(Vars))
if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
if Vset={} thenreturned:= 0else! Get the variable(s) with smallest lower bounddmin:= min(i in Vset) getlb(getvar(Vars,i))
forall(i in Vset)
if getlb(getvar(Vars,i)) = dmin then Iset+= {i}; end-if! Choose variable with smallest upper bound among those indexed by ’Iset’
dmax:= getparam("kalis_default_ub")
forall(i in Iset)
if getub(getvar(Vars,i)) < dmax thenreturned:= i
dmax:= getub(getvar(Vars,i))
end-ifend-ifend-function

Value selection: the value selection function receives as its argument the chosen branchingvariable and returns a branching value for this variable. The value selection criterion we havechosen (corresponding to KALIS_MAX_TO_MIN) is to enumerate all values for the branchingvariable, starting with the largest remaining one (that is, the variable’s upper bound):function valchoice(x: cpvar): integer
returned:= getub(x)end-function

Notice that with an assign_var or assign_and_forbid strategy, the user’s value selection strategy
should make sure to return a value that is currently in the branching variable’s domain (a value
chosen between the lower and upper bound is not guaranteed to lie in the domain) by using
function contains.
Setting user search strategies: to indicate that we wish to use our own variable or value selection
strategy we simply need to replace the predefined constants by the name of our Mosel functions:
Strategy:= assign_var("varchoice", "valchoice", output)

defines the strategy for the first optimization run andStrategy:= assign_var("varchoicemin", "valchoice", output)

re-defines it for the serial machine case. Since our function valchoice does just the same as the
KALIS_MAX_TO_MIN criterion, we could also combine it with our variable choice function:
Strategy:= assign_var("varchoicemin", KALIS_MAX_TO_MIN, output)

4.4.4

Results
The following table summarizes the results found with the different solution methods for thetwo problems of parallel and serial machines. There is a notable difference between the heuristic
method and the exact solution to the problem with parallel machines.
By adding output of solver statistics to our model (cp_show_stats) we find that our user searchstrategies result in the same search trees and program execution durations as with the predefined
strategies for the parallel assignment and arrive at a slightly different solution for the serial case.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

69

Enumeration

Table 4.2: Optimal assignments for different model versions
Person

4.5

Alg.

1

2

3

4

5

6

Productivity

Parallel Machines

Heur.
Exact

4 (19)
3 (31)

1 (18)
5 (43)

6 (33)
4 (25)

2 (26)
6 (30)

3 (34)
1 (28)

5 (45)
2 (36)

175
193

Serial MachinesExact

5 (40)

3 (30)

6 (33)

2 (26)

1 (28)

4 (27)

26

Reversible numbers
When developing your own search strategies and also in the implementation of user constraints
it is sometimes helpful to be able to save some information related to a particular state of theconstraint system and have the corresponding values restored automatically whenever the system
returns to an earlier state during backtrack.
Within Xpress Kalis, this type of backtrackable information is implemented by the types
cpreversible and cpreversiblearray. A reversible number is an object that takes integer or realvalues associated with a given state of the constraint system. Earlier values are restored when thesystem backtracks to the corresponding state.
The values of reversible numbers are stored with the constraint system, and as such one might betempted to compare them with decision variables, but there is a fundamental difference between
the two: the principle of incrementality does not apply to reversible numbers. Whereas thebounds on decision variables can only be reduced from any node to its descendants, the value ofa reversible number might be any random sequence, such as 1 at the first node, -2 at its
immediate child node, and 3 at the node of the next lower level. The following small example
illustrates this. At every node, the coefficients of all fixed variables are saved in the array ofreversibles ka and the reversible number k is the sum of the already fixed terms. The example
further uses a reversible depth to save the current level in the branching tree. The ’branch-up’
and ’branch-down’ callbacks are used for displaying the current values of all numbers.
model "Tracing reversible numbers"
uses "kalis", "mmsystem"
declarations
N = 5
R = 1..N
C: array(R) of integer
x: array(R) of cpvar
k,depth: cpreversible
ka: cpreversiblearray
end-declarations
C::(1..5)[-7,15,-3,19,-45]! Initialization: all reversible numbers at 0
set_reversible_attributes(depth, 0)
set_reversible_attributes(k, 0)
set_reversible_attributes(ka, 1, N, 0)! Decision variables and constraints
forall(i in R) setdomain(x(i), 0, 1)
sum(i in R) x(i) >= 3!************ Callback functions ************
procedure save_node_statesetval(depth, getval(depth)+1)
k.val:= sum(i in R) if(is_fixed(x(i)), C(i)*x(i).val, 0)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

70Enumeration

forall(i in R) setelt(ka,i, if(is_fixed(x(i)), C(i)*x(i).val, 0))
end-procedure
procedure branch_up
writeln(textfmt(" "*2*round(depth.val)+ "up
end-procedure
procedure branch_down
writeln(textfmt(" "*2*round(depth.val)+ "down
end-procedure",-20), k, "\t", ka)",-20), k, "\t", ka)!********************************************
cp_set_node_callback("save_node_state")
cp_set_branch_callback("branch_down", "branch_up")
cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MAX_TO_MIN))
setparam("KALIS_MAX_SOLUTIONS", 3)
while (cp_find_next_sol) do
writeln(" "*2*round(depth.val), "Solution: ", x)
end-doend-model

The output produced by the example is shown here, notice how the tree depth value is used toindent the lines, and observe how the values of reversibles change between nodes, in particular
the value of the reversible number k.
down
0.000000[0 0 0 0 0 ]down-7.000000[-7 0 0 0 0 ]down
8.000000[-7 15 0 0 0 ]down
5.000000[-7 15 -3 0 0 ]down
24.000000[-7 15 -3 19 0 ]Solution: [V001[1],V002[1],V003[1],V004[1],V005[1]]up
5.000000[-7 15 -3 0 0 ]down
24.000000[-7 15 -3 19 0 ]Solution: [V001[1],V002[1],V003[1],V004[1],V005[0]]up
5.000000[-7 15 -3 0 0 ]up
8.000000[-7 15 0 0 0 ]down
5.000000[-7 15 -3 0 0 ]down
5.000000[-7 15 -3 0 0 ]Solution: [V001[1],V002[1],V003[1],V004[0],V005[1]]up
5.000000[-7 15 -3 0 0 ]up
8.000000[-7 15 0 0 0 ]up-7.000000[-7 0 0 0 0 ]up
0.000000[0 0 0 0 0 ]up
0.000000[0 0 0 0 0 ]4.6

Analyzing infeasibility and handling conflicts
In many cases the return status ’problem infeasible’ or ’ constraint inconsistent’ is not a desirable
situation since we really wish to find a solution to the problem we are solving. To support theuser’s analysis of the cause of the infeasibility Kalis can generate reports about sets of infeasible
constraints. During the development of a model such a facility helps tracking model formulation
errors and in applications inconsistencies in data are identified more easily.
We shall work once more with the Sudoku example from Section 3.3. Instead of launching theenumeration through the CP solver we now prompt the user to input a value for a randomly
chosen cell. If the value set by the user leads to an inconsistent state of the constraint system weinvoke the solver display of the minimal set of constraints causing the infeasibility.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

71Enumeration

4.6.1

Implementation
The problem statement and setting of start data remain exactly the same as with the standard
implementation of the problem seen in Section 3.3. What is new are the prompt for user input
and the subsequent handling of infeasibilities. The underlying mechanisms are markers (often
referred to as choice points) to save the state of the constraint solver at a given moment and thepossibility to return to the last such saved state. The corresponding Mosel subroutines are
cp_save_state and cp_restore_state. After stating a new constraint but before propagating its
effect (the automated propagation has been switched off through the setting of AUTO_PROPAGATEat the beginning of the model) we save the state of the constraint system. If the new constraint
turns out to be infeasible the solver is set back to the state before the constraint propagation andwe can then invoke the infeasibility analysis (cp_infeas_analysis).
The subroutine for solution printing has been replaced by a routine printing the values of all
fixed variables.
model "Conflicts"
uses "kalis"forward procedure print_values
setparam("kalis_default_lb", 1)
setparam("kalis_default_ub", 9)! Default variable bounds

declarations
XS = {’A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’}! Columns
YS = 1..9! Rowsv: array(XS,YS) of cpvar! Number assigned to cell (x,y)
end-declarations
forall(x in XS,y in YS) setname(v(x,y), "v("+x+","+y+")")
setparam("KALIS_AUTO_PROPAGATE", 0)! Disable automatic propagation! Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudokuv(’A’,1)=8; v(’F’,1)=3v(’B’,2)=5; v(’G’,2)=4v(’A’,3)=2; v(’E’,3)=7; v(’H’,3)=6v(’D’,4)=1; v(’I’,4)=5v(’C’,5)=3; v(’G’,5)=9v(’A’,6)=6; v(’F’,6)=4v(’B’,7)=7; v(’E’,7)=2; v(’I’,7)=3v(’C’,8)=4; v(’H’,8)=1v(’D’,9)=9; v(’I’,9)=8! All-different values in rows
forall(y in YS) all_different(union(x in XS) {v(x,y)})! All-different values in columns
forall(x in XS) all_different(union(y in YS) {v(x,y)})! All-different values in 3x3 squares
forall(s in {{’A’,’B’,’C’},{’D’,’E’,’F’},{’G’,’H’,’I’}}, i in 0..2)
all_different(union(x in s, y in {1+3*i,2+3*i,3+3*i}) {v(x,y)})! Prompt user for new assignments
declarations
NX: array(1..9) of string
val: integer
end-declarations
NX::(1..9)[’A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’]
cp_save_state
res:=cp_propagate

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

72Enumeration

print_values
setrandseed(3)while (res and (or(x in XS,y in YS) not is_fixed(v(x,y))) ) do
! Select randomly a yet unassigned cellrx:=round(0.5+9*random); ry:=round(0.5+9*random)
while (is_fixed(v(NX(rx),ry))) do
rx:=round(0.5+9*random); ry:=round(0.5+9*random)
end-do! Prompt for user input
writeln(v(NX(rx),ry), " = ")readln(val)! Add the new constraintv(NX(rx),ry)=val
cp_save_state
res:=cp_propagate! State a new constraint! Save system state before propagation! Propagate the new constraint! Print resulting board
print_values
end-do! An infeasible state has been reached
if not res thencp_restore_state! Restore state before propagation
cp_infeas_analysis! Analyze infeasibility, print report
else
writeln("Problem solved")
end-if!****************************************************************! Print fixed values
procedure print_values
writeln("
A B C
D E F
G H I")
forall(y in YS) do
write(y, ": ")forall(x in XS)
write(if(is_fixed(v(x,y)), string(getval(v(x,y))), "."),
if(x in {’C’,’F’}, " | ", " "))writeln
if y mod 3 = 0 thenwriteln("---------------------")
end-ifend-doend-procedure
end-model

4.6.2

Results
With the following user value input sequence:v(F,7)[1,5..6,8] =1
v(I,1)[1..2,7,9] =1v(I,8)[2,6..7] =2

we obtain an infeasibility for the third value. The values printed at this stage and the report
generated by the solver show why this value leads to a conflict.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

73Enumeration

A B C
D E F
G H I
1: 8 . . | . . 3 | . . 1
2: . 5 . | . . . | 4 . 7
3: 2 . 1 | . 7 . | . 6 9--------------------4: . . . | 1 . . | . . 5
5: . . 3 | . . . | 9 . .
6: 6 . . | . . 4 | . . 7--------------------7: . 7 . | . 2 1 | . . 3
8: . . 4 | . . . | . 1 2
9: . . . | 9 . . | . . 8-------------------------------------------Minimal Conflict Set-----------------------1 : AllDifferent(v(I,1),v(I,2),v(I,3),v(I,4),v(I,5),v(I,6),v(I,7),v(I,8),v(I,9))

Note: in the present example we examine the effect of adding just a single (bound) constraint toour problem. However, the infeasibility analysis functionality can be applied for any number andtype of constraints.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

74

C HAPTER 5

SchedulingThis chapter shows how to

5.1



define and setup the modeling objects cptask and cpresource,formulate and solve scheduling problems using these objects,access information from the modeling objects.

parameterize search strategies involving the scheduling objects,

Tasks and resources
Scheduling and planning problems are concerned with determining a plan for the execution of agiven set of tasks. The objective may be to generate a feasible schedule that satisfies the given
constraints (such as sequence of tasks or limited resource availability) or to optimize a given
criterion such as the makespan of the schedule.
Xpress Kalis defines several aggregate modeling objects to simplify the formulation of standard
scheduling problems: tasks (processing operations, activities) are represented by the type cptask
and resources (machines, raw material etc.) by the type cpresource. When working with thesescheduling objects it is often sufficient to state the objects and their properties, such as task
duration or resource use; the necessary constraint relations are set up automatically by Xpress
Kalis (referred to as implicit constraints). In the following sections we show a number of examples
using this mechanism:The simplest case of a scheduling problem involves only tasks and precedence constraints
between tasks (project scheduling problem in Section 5.2).

Tasks may be mutually exclusive, e.g. because they use the same unitary resource(disjunctive scheduling / sequencing problem in Section 5.3).

Resources may be usable by several tasks at a time, up to a given capacity limit (cumulative
resources, see Section 5.4).



A different classification of resources is the distinction between renewable andnon-renewable resources (see Section 5.5).

Many extensions of the standard problems are possible, such as sequence-dependent setup
time (see Section 5.6.1), choice of resources (Section 5.6.2), tasks with non-constant resource
profiles (Section 5.6.3), or given idle times for resources (Section 5.6.4).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information75

Scheduling

If the enumeration is started with the function cp_schedule the solver will employ specialized
search strategies suitable for the corresponding (scheduling) problem type. It is possible toparameterize these strategies or to define user search strategies for scheduling objects (seeSection 5.7). Alternatively, the standard optimization functions cp_minimize / cp_maximize may
be used. In this case the enumeration does not exploit the structural information provided by thescheduling objects and works simply with decision variables.
The properties of scheduling objects (such as start time or duration of tasks) can be accessed andemployed, for instance, in the definition of constraints, thus giving the user the possibility toextend the predefined standard problems with other types of constraints. For even greater
flexibility Xpress Kalis also enables the user to formulate his scheduling problems without theaggregate modeling objects, using dedicated global constraints on decision variables of typecpvar. Most examples in this chapter are therefore given with two different implementations,
one using the scheduling objects and another without these objects.

5.2

Precedences
Probably the most basic type of a scheduling problem is to plan a set of tasks that are linked byprecedence constraints.
The problem described in this section is taken from Section 7.1 ‘Construction of a stadium’ of thebook ‘Applications of optimization with Xpress-MP’
A construction company has been awarded a contract to construct a stadium and wishes tocomplete it within the shortest possible time. Table 5.1 lists the major tasks and their durations inweeks. Some tasks can only start after the completion of certain other tasks, equally indicated in
the table.
Table 5.1: Data for stadium construction

5.2.1

Task

Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Installing the construction site
TerracingConstructing the foundations
Access roads and other networks
Erecting the basement
Main floor
Dividing up the changing rooms
Electrifying the terraces
Constructing the roof
Lighting of the stadium
Installing the terraces
Sealing the roof
Finishing the changing rooms
Constructing the ticket officeSecondary access roads
Means of signalling
Lawn and sport accessories
Handing over the building

Duration

Predecessors

2
16
9
8
10
6
2
2
9
5
3
2
1
7
4
3
9
1

none
1
2
2
3
4,5
4
6
4,6
4
6
9
7
2
4,14
8,11,1412
17

Model formulation
This problem is a classical project scheduling problem. We add a fictitious task with 0 durationthat corresponds to the end of the project. We thus consider the set of tasks TASKS = {1, . . . , N}
where N is the fictitious end task.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information76

SchedulingEvery construction task j (j ∈ TASKS) is represented by a task object taskj with variable start timetaskj . start and a duration fixed to the given value DURj . The precedences between tasks are
represented by a precedence graph with arcs (i, j) symbolizing that task i precedes task j.
The objective is to minimize the completion time of the project, that is the start time of the last,fictitious task N. We thus obtain the following model where an upper bound HORIZON on thestart times is given by the sum of all task durations:tasks taskj (j ∈ TASKS)
minimize taskN . start∀j ∈ TASKS : taskj . start ∈ {0, . . . , HORIZON}∀j ∈ TASKS : taskj . duration = DURj[∀j ∈ TASKS : taskj . predecessors ={taski }i∈TASKS,s.t.∃ARCij

5.2.2

Implementation
The following model shows the implementation of this problem with Xpress Kalis. Since there areno side-constraints, the earliest possible completion time of the schedule is the earliest start of
the fictitious task N. To trigger the propagation of task-related constraints we call the function
cp_propagate followed by a call to cp_shave that performs some additional tests to remove
infeasible values from the task variables’ domains. At this point, constraining the start of thefictitious end task to its lower bound reduces all task start times to their feasible intervals
through the effect of constraint propagation. The start times of tasks on the critical path are
fixed to a single value. The subsequent call to minimization only serves for instantiating all
variables with a single value so as to enable the graphical representation of the solution.
model "B-1 Stadium construction (CP)"uses "kalis"declarations
N = 19! Number of tasks in the project! (last = fictitious end task)

TASKS = 1..N
ARC: dynamic array(range,range) of integer ! Matrix of the adjacency graph
DUR: array(TASKS) of integer! Duration of tasks
HORIZON : integer! Time horizon
task: array(TASKS) of cptask
bestend: integer
end-declarations! Tasks to be planned

initializations from ’Data/b1stadium.dat’
DUR ARC
end-initializations
HORIZON:= sum(j in TASKS) DUR(j)! Setting up the tasks
forall(j in TASKS) do
setdomain(getstart(task(j)), 0, HORIZON)! Time horizon for start times
set_task_attributes(task(j), DUR(j))! Duration
setsuccessors(task(j), union(i in TASKS | exists(ARC(j,i))) {task(i)})
end-do! Precedences
if not cp_propagate or not cp_shave thenwriteln("Problem is infeasible")exit(1)
end-ifFair Isaac Corporation and Artelys SA Confidential and Proprietary Information

77

Scheduling! Since there are no side-constraints, the earliest possible completion! time is the earliest start of the fictitious task N
bestend:= getlb(getstart(task(N)))
getstart(task(N)) <= bestend
writeln("Earliest possible completion time: ", bestend)! For tasks on the critical path the start/completion times have been fixed! by setting the bound on the last task. For all other tasks the range of! possible start/completion times gets displayed.
forall(j in TASKS) writeln(j, ": ", getstart(task(j)))! Complete enumeration: schedule every task at the earliest possible date
if cp_minimize(getstart(task(N))) thenwriteln("Solution after optimization: ")forall(j in TASKS) writeln(j, ": ", getsol(getstart(task(j))))end-ifend-model

Instead of indicating the predecessors of a task, we may just as well state the precedence
constraints by indicating the sets of successors for every task:
setsuccessors(task(j), union(i in TASKS | exists(ARC(j,i))) {task(i)})

5.2.3

Results
The earliest completion time of the stadium construction is 64 weeks.

5.2.4

Alternative formulation without scheduling objects
As for the previous formulation, we work with a set of tasks TASKS = {1, . . . , N} where N is thefictitious end task. For every task j we introduce a decision variable startj to denote its start time.
With DURj the duration of task j, the precedence relation ‘task i precedes task j’ is stated by theconstraint
starti + DURi ≤ startj
We therefore obtain the following model for our project scheduling problem:
minimize startN∀j ∈ TASKS : startj ∈ {0, . . . , HORIZON}∀i, j ∈ TASKS, ∃ARCij : starti + DURi ≤ startj
The corresponding Mosel model is printed in full below. Notice that we have used explicit postingof the precedence constraints—in the case of an infeasible data instance this may help tracing thecause of the infeasibility.
model "B-1 Stadium construction (CP)"uses "kalis"declarations
N = 19! Number of tasks in the project! (last = fictitious end task)

TASKS = 1..N
ARC: dynamic array(range,range) of integer ! Matrix of the adjacency graph
DUR: array(TASKS) of integer! Duration of tasks
HORIZON : integer! Time horizon
start: array(TASKS) of cpvar
bestend: integer! Start dates of tasks

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information78

Schedulingend-declarations
initializations from ’Data/b1stadium.dat’
DUR ARC
end-initializations
HORIZON:= sum(j in TASKS) DUR(j)forall(j in TASKS) do
0 <= start(j); start(j) <= HORIZON
end-do! Task i precedes task j
forall(i, j in TASKS | exists(ARC(i, j))) do
Prec(i,j):= start(i) + DUR(i) <= start(j)if not cp_post(Prec(i,j)) thenwriteln("Posting precedence ", i, "-", j, " failed")
exit(1)
end-ifend-do! Since there are no side-constraints, the earliest possible completion! time is the earliest start of the fictitious task N
bestend:= getlb(start(N))
start(N) <= bestend
writeln("Earliest possible completion time: ", bestend)! For tasks on the critical path the start/completion times have been fixed! by setting the bound on the last task. For all other tasks the range of! possible start/completion times gets displayed.
forall(j in TASKS) writeln(j, ": ", start(j))
end-model

5.3

Disjunctive scheduling: unary resources
The problem of sequencing jobs on a single machine described in Section 3.5 may be represented
as a disjunctive scheduling problem using the ‘task’ and ‘resource’ modeling objects.
The reader is reminded that the problem is to schedule the processing of a set of non-preemptivetasks (or jobs) on a single machine. For every task j its release date, duration, and due date are
given. The problem is to be solved with three different objectives, minimizing the makespan, theaverage completion time, or the total tardiness.

5.3.1

Model formulation
The major part of the model formulation consists of the definition of the scheduling objects‘tasks’ and ‘resources’.
Every job j (j ∈ JOBS = {1, . . . , NJ}) is represented by a task object taskj , with a start timetaskj . start in {RELj , . . . , MAXTIME} (where MAXTIME is a sufficiently large value, such as the sumof all release dates and all durations, and RELj the release date of job j) and the task duration
taskj . duration fixed to the given processing time DURj . All jobs use the same resource res ofunitary capacity. This means that at most one job may be processed at any one time, we thus
implicitly state the disjunctions between the jobs.
Another implicit constraint established by the task objects is the relation between the start,
duration, and completion time of a job j.
∀j ∈ JOBS : taskj . end = taskj . start + taskj . duration
Objective 1: The first objective is to minimize the makespan (completion time of the schedule) or,

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

79

Schedulingequivalently, to minimize the completion time finish of the last job. The complete model is thengiven by the following (where MAXTIME is a sufficiently large value, such as the sum of all
release dates and all durations):
resource res
tasks taskj (j ∈ JOBS)
minimize finish
finish = maximumj∈JOBS (taskj . end)
res. capacity = 1∀j ∈ JOBS : taskj . end ∈ {0, . . . , MAXTIME}∀j ∈ JOBS : taskj . start ∈ {RELj , . . . , MAXTIME}∀j ∈ JOBS : taskj . duration = DURj∀j ∈ JOBS : taskj . requirementres = 1

Objective 2: The formulation of the second objective (minimizing the average processing time or,
equivalently, minimizing the sum of the job completion times) remains unchanged from the firstmodel—we introduce an additional variable totComp representing the sum of the completion
times of all jobs.
minimize totComp
X
totComp =taskj . end
j∈JOBS

Objective 3: To formulate the objective of minimizing the total tardiness, we introduce newvariables latej to measure the amount of time that a job finishes after its due date. The value ofthese variables corresponds to the difference between the completion time of a job j and its due
date DUEj . If the job finishes before its due date, the value must be zero. The objective now is tominimize the sum of these tardiness variables:
minimize totLate
X
totLate =latej
j∈JOBS∀j ∈ JOBS : latej ∈ {0, . . . , MAXTIME}∀j ∈ JOBS : latej ≥ taskj . end − DUEj

5.3.2

Implementation
The following implementation with Xpress Kalis (file b4seq3_ka.mos) shows how to set up thenecessary task and resource modeling objects. The resource capacity is set with procedure
set_resource_attributes (the resource is of the type KALIS_UNARY_RESOURCE meaning that itprocesses at most one task at a time), for the tasks we use the procedure set_task_attributes.
The latter exists in several overloaded versions for different combinations of arguments (taskattributes)—the reader is referred to the Xpress Kalis Reference Manual for further detail.
For the formulation of the maximum constraint we use an (auxiliary) list of variables: Xpress Kalis
does not allow the user to employ the access functions to modeling objects (getstart,
getduration, etc.) in set expressions such as union(j in JOBS) getend(task(j)).
model "B-4 Sequencing (CP)"uses "kalis"forward procedure print_sol

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

80

Schedulingforward procedure print_sol3
declarations
NJ = 7
JOBS=1..NJ! Number of jobs

REL: array(JOBS) of integer
DUR: array(JOBS) of integer
DUE: array(JOBS) of integer! Release dates of jobs
! Durations of jobs
! Due dates of jobs

task: array(JOBS) of cptask
res: cpresource! Tasks (jobs to be scheduled)! Resource (machine)

finish: cpvar
end-declarations! Completion time of the entire schedule

initializations from ’Data/b4seq.dat’
DUR REL DUE
end-initializations! Setting up the resource (formulation of the disjunction of tasks)
set_resource_attributes(res, KALIS_UNARY_RESOURCE, 1)! Setting up the tasks (durations and disjunctions)forall(j in JOBS) set_task_attributes(task(j), DUR(j), res)MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)forall(j in JOBS) do
0 <= getstart(task(j)); getstart(task(j)) <= MAXTIME
0 <= getend(task(j)); getend(task(j)) <= MAXTIME
end-do! Start times
forall(j in JOBS) getstart(task(j)) >= REL(j)!**** Objective function 1: minimize latest completion time ****
declarations
L: cpvarlist
end-declarations
forall(j in JOBS) L += getend(task(j))
finish = maximum(L)if cp_schedule(finish) >0 thenprint_sol
end-if!**** Objective function 2: minimize average completion time ****
declarations
totComp: cpvar
end-declarations
totComp = sum(j in JOBS) getend(task(j))
if cp_schedule(totComp) > 0 thenprint_sol
end-if!**** Objective function 3: minimize total tardiness ****
declarations
late: array(JOBS) of cpvar! Lateness of jobs
totLate: cpvar
end-declarations
forall(j in JOBS) do
0 <= late(j); late(j) <= MAXTIMEFair Isaac Corporation and Artelys SA Confidential and Proprietary Information81

Schedulingend-do! Late jobs: completion time exceeds the due dateforall(j in JOBS) late(j) >= getend(task(j)) - DUE(j)totLate = sum(j in JOBS) late(j)if cp_schedule(totLate) > 0 thenwriteln("Tardiness: ", getsol(totLate))
print_sol
print_sol3
end-if!----------------------------------------------------------------! Solution printing
procedure print_sol
writeln("Completion time: ", getsol(finish) ," average: ", getsol(sum(j in JOBS) getend(task(j))))write("Rel\t")forall(j in JOBS) write(strfmt(REL(j),4))
write("\nDur\t")forall(j in JOBS) write(strfmt(DUR(j),4))
write("\nStart\t")forall(j in JOBS) write(strfmt(getsol(getstart(task(j))),4))
write("\nEnd\t")forall(j in JOBS) write(strfmt(getsol(getend(task(j))),4))
writeln
end-procedure
procedure print_sol3
write("Due\t")forall(j in JOBS) write(strfmt(DUE(j),4))
write("\nLate\t")forall(j in JOBS) write(strfmt(getsol(late(j)),4))
writeln
end-procedure
end-model

5.3.3

Results
This model produces similar results as those reported for the model versions in Section 3.5. Figure
5.1 shows a Gantt chart display of the solution. Above the Gantt chart we can see the resource
usage display: the machine is used without interruption by the tasks, that is, even if we relaxed
the constraints given by the release times and due dates it would not have been possible togenerate a schedule terminating earlier.

Figure 5.1: Solution Gantt chart

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information82

Scheduling

5.4

Cumulative scheduling: discrete resources
The problem described in this section is taken from Section 9.4 ‘Backing up files’ of the book
‘Applications of optimization with Xpress-MP’
Our task is to save sixteen files of the following sizes: 46kb, 55kb, 62kb, 87kb, 108kb, 114kb,
137kb, 164kb, 253kb, 364kb, 372kb, 388kb, 406kb, 432kb, 461kb, and 851kb onto empty disks of
1.44Mb capacity. How should the files be distributed in order to minimize the number of floppy
disks used?

5.4.1

Model formulation
This problem belongs to the class of binpacking problems. We show here how it may beformulated and solved as a cumulative scheduling problem, where the disks are the resource andthe files the tasks to be scheduled.
The floppy disks may be represented as a single, discrete resource disks, where every time unit
stands for one disk. The resource capacity corresponds to the disk capacity.
We represent every file f (f ∈ FILES) by a task object filef , with a fixed duration of 1 unit and a
resource requirement that corresponds to the given size SIZEf of the file. The ‘start’ field of thetask then indicates the choice of the disk for saving this file.
The objective is to minimize the number of disks that are used, which corresponds to minimizing
the largest value taken by the ‘start’ fields of the tasks (that is, the number of the disk used forsaving a file). We thus have the following model.
resource disks
tasks filesf (f ∈ FILES)
minimize diskuse
diskuse = maximumf∈FILES (filef . start)
disks. capacity = CAP∀f ∈ FILES : filef . start ≥ 1∀f ∈ FILES : filef . duration = 1∀f ∈ FILES : filef . requirementdisks = SIZEf

5.4.2

Implementation
The implementation with Xpress Kalis is quite straightforward. We define a resource of the type
KALIS_DISCRETE_RESOURCE, indicating its total capacity. The definition of the tasks is similar towhat we have seen in the previous example.
model "D-4 Bin packing (CP)"uses "kalis"declarations
ND: integer
FILES = 1..16
DISKS: range! Number of floppy disks! Set of files! Set of disks

CAP: integer
SIZE: array(FILES) of integer! Floppy disk size
! Size of files to be saved

file: array(FILES) of cptask
disks: cpresource
L: cpvarlist
diskuse: cpvar
end-declarations! Tasks (= files to be saved)! Resource representing disks! Number of disks used

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

83

Scheduling

initializations from ’Data/d4backup.dat’
CAP SIZE
end-initializations! Provide a sufficiently large number of disks
ND:= ceil((sum(f in FILES) SIZE(f))/CAP)DISKS:= 1..ND! Setting up the resource (capacity limit of disks)
set_resource_attributes(disks, KALIS_DISCRETE_RESOURCE, CAP)
! Setting up the tasks
forall(f in FILES) do
setdomain(getstart(file(f)), DISKS)! Start time (= choice of disk)
set_task_attributes(file(f), disks, SIZE(f)) ! Resource (disk space) req.
set_task_attributes(file(f), 1)! Duration (= number of disks used)
end-do! Limit the number of disks used
forall(f in FILES) L += getstart(file(f))
diskuse = maximum(L)! Minimize the total number of disks used
if cp_schedule(diskuse) = 0 thenwriteln("Problem infeasible")
end-if! Solution printing
writeln("Number of disks used: ", getsol(diskuse))
forall(d in 1..getsol(diskuse)) dowrite(d, ":")
forall(f in FILES) write( if(getsol(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-docp_show_stats
end-model

5.4.3

Results
Running the model results in the solution shown in Table 5.2, that is, 3 disks are needed forbacking up all the files.
Table 5.2: Distribution of files to disks

5.4.4

Disk

File sizes (in kb)

Used space (in Mb)

1
2
3

46 87 137 164 253 364 388
55 62 108 372 406 432
114 461 851

1.439
1.435
1.426

Alternative formulation without scheduling objects
Instead of defining task and resource objects it is also possible to formulate this problem with a‘cumulative’ constraint over standard finite domain variables that represent the different
attributes of tasks without being grouped into a predefined object. A single ‘cumulative’
constraint expresses the problem of scheduling a set of tasks on one discrete resource by
establishing the following relations between its arguments (five arrays of decision variables forthe properties related to tasks—start, duration, end, resource use and size— all indexed by thesame set R and a constant or time-indexed resource capacity):∀j ∈ R : startj + durationj = endj

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

84

Scheduling∀j ∈ R : usej · durationj = sizejX∀t ∈ TIMES :usej ≤ CAPt

j∈R|t∈[UB(startj )..LB(endj )]where UB stands for ‘upper bound’ and LB for ‘lower bound’ of a decision variable.
Let savef denote the disk used for saving a file f and usef the space used by the file (f ∈ FILES). As
with scheduling objects, the ‘start’ property of a task corresponds to the disk chosen for saving
the file, and the resource requirement of a task is the file size. Since we want to save every fileonto a single disk, the ‘duration’ durf is fixed to 1. The remaining task properties ‘end’ and ‘size’(ef and sf ) that need to be provided in the formulation of ‘cumulative’ constraints are not reallyrequired for our problem; their values are determined by the other three properties.

5.4.5

Implementation
The following Mosel model implements the second model version using the cumulative
constraint.
model "D-4 Bin packing (CP)"uses "kalis", "mmsystem"
setparam("kalis_default_lb", 0)declarations
ND: integer
FILES = 1..16
DISKS: range! Number of floppy disks! Set of files! Set of disks

CAP: integer
SIZE: array(FILES) of integer! Floppy disk size
! Size of files to be saved

save: array(FILES) of cpvar
use: array(FILES) of cpvar
dur,e,s: array(FILES) of cpvar
diskuse: cpvar! Disk a file is saved on! Space used by file on disk
! Auxiliary arrays for ’cumulative’! Number of disks used

Strategy: array(FILES) of cpbranching ! Enumeration
FSORT: array(FILES) of integer
end-declarations
initializations from ’Data/d4backup.dat’
CAP SIZE
end-initializations! Provide a sufficiently large number of disks
ND:= ceil((sum(f in FILES) SIZE(f))/CAP)DISKS:= 1..ND
finalize(DISKS)! Limit the number of disks useddiskuse = maximum(save)forall(f in FILES) do
setdomain(save(f), DISKS)
use(f) = SIZE(f)dur(f) = 1
end-do! Every file onto a single disk

! Capacity limit of disks
cumulative(save, dur, e, use, s, CAP)
! Definition of search (place largest files first)
qsort(SYS_DOWN, SIZE, FSORT)! Sort files in decreasing order of size
forall(f in FILES)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

85

Scheduling

Strategy(f):= assign_var(KALIS_SMALLEST_MIN, KALIS_MIN_TO_MAX, {save(FSORT(f))})cp_set_branching(Strategy)! Minimize the total number of disks used
if not cp_minimize(diskuse) thenwriteln("Problem infeasible")
end-if! Solution printing
writeln("Number of disks used: ", getsol(diskuse))
forall(d in 1..getsol(diskuse)) dowrite(d, ":")
forall(f in FILES) write( if(getsol(save(f))=d , " "+SIZE(f), ""))
writeln(" space used: ", sum(f in FILES | getsol(save(f))=d) SIZE(f))
end-doend-model

The solution produced by the execution of this model has the same objective function value, but
the distribution of the files to the disks is not exactly the same: this problem has several different
optimal solutions, in particular those that may be obtained be interchanging the order numbersof the disks. To shorten the search in such a case it may be useful to add some symmetry breaking
constraints that reduce the size of the search space by removing a part of the feasible solutions.
In the present example we may, for instance, assign the biggest file to the first disk and thesecond largest to one of the first two disks, and so on, until we reach a lower bound on thenumber of disks required (a save lower bound estimate is given by rounding up to the next larger
integer the sum of files sizes divided by the disk capacity).

5.5

Renewable and non-renewable resources
Besides the distinction ‘disjunctive–cumulative’ or ‘unary–discrete’ that we have encountered in
the previous sections there are other ways of describing or classifying resources. Anotherimportant property is the concept of renewable versus non-renewable resources. The previous
examples have shown instances of renewable resources (machine capacity, manpower etc.): theamount of resource used by a task is released at its completion and becomes available for othertasks. In the case of non-renewable resources (e.g. money, raw material, intermediate products),
the tasks using the resource consume it, that is, the available quantity of the resource isdiminuished by the amount used up by processing a task.
Instead of using resources tasks may also produce certain quantities of resource. Again, we may
have tasks that provide an amount of resource during their execution (renewable resources) ortasks that add the result of their production to a stock of resource (non-renewable resources).
Let us now see how to formulate the following problem: we wish to schedule five jobs P1 to P5
representing two stages of a production process. P1 and P2 produce an intermediate productthat is needed by the jobs of the final stage (P3 to P5). For every job we are given its minimum
and maximum duration, its cost or, for the jobs of the final stage, its profit contribution. Theremay be two cases, namely model A: the jobs of the first stage produce a given quantity ofintermediate product (such as electricity, heat, steam) at every point of time during their
execution, this intermediate product is consumed immediately by the jobs of the final stage.
Model B: the intermediate product results as ouput from the jobs of the first stage and isrequired as input to start the jobs of the final stage. The intermediate product in model A is arenewable resource and in model B we have the case of a non-renewable resource.

5.5.1

Model formulation
Let FIRST = {P1, P2} be the set of jobs in the first stage, FINAL = {P3, P4, P5} the jobs of thesecond stage, and the set JOBS the union of all jobs. For every job j we are given its minimum andFair Isaac Corporation and Artelys SA Confidential and Proprietary Information86

Schedulingmaximum duration MINDj and MAXDj respectively. RESAMTj is the amount of resource needed as
input or resulting as output from a job. Furthermore we have a cost COSTj for jobs j of the firststage and a profit PROFITj for jobs j of the final stage.
Model A (renewable resource)
The case of a renewable resource is formulated by the following model. Notice that the resource
capacity is set to 0 indicating that the only available quantities of resource are those produced by
the jobs of the first production stage.

resource res
tasks taskj (j ∈ JOBS)
X
maximize(PROFITj − COSTj ) × taskj . durationj∈JOBS

res. capacity = 0∀j ∈ JOBS : taskj . start, taskj . end ∈ {0, . . . , HORIZON}∀j ∈ JOBS : taskj . duration ∈ {MINDj , . . . , MAXDj }∀j ∈ FIRST : taskj . provisionres = RESAMTj∀j ∈ FINAL : taskj . requirementres = RESAMTj
Model B (non-renewable resource)
In analogy to the model A we formulate the second case as follows.

resource res
tasks taskj (j ∈ JOBS)
X
maximize(PROFITj − COSTj ) × taskj . durationj∈JOBS

res. capacity = 0∀j ∈ JOBS : taskj . start, taskj . end ∈ {0, . . . , HORIZON}∀j ∈ JOBS : taskj . duration ∈ {MINDj , . . . , MAXDj }∀j ∈ FIRST : taskj . productionres = RESAMTj∀j ∈ FINAL : taskj . consumptionres = RESAMTj
However, this model does not entirely correspond to the problem description above since theproduction of the intermediate product occurs at the start of a task. To remedy this problem we
may introduce an auxiliary task Endj for every job j in the first stage. The auxiliary job has
duration 0, the same completion time as the original job and produces the intermediate productin the place of the original job.

∀j ∈ FIRST : taskEndj . end = taskj . end∀j ∈ FIRST : taskEndj . duration = 0∀j ∈ FIRST : taskj . productionres = 0∀j ∈ FIRST : taskEndj . productionres = RESAMTj

5.5.2

Implementation
The following Mosel model implements case A. We use the default scheduling solver (function

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

87

Scheduling

cp_schedule) indicating by the value true for the optional second argument that we wish to
maximize the objective function.
model "Renewable resource"
uses "kalis", "mmsystem"
forward procedure solution_founddeclarations
FIRST = {’P1’,’P2’}
FINAL = {’P3’,’P4’,’P5’}
JOBS = FIRST+FINAL
MIND,MAXD: array(JOBS) of integer ! Limits on job durations
RESAMT: array(JOBS) of integer ! Resource use/production
HORIZON: integer! Time horizon
PROFIT: array(FINAL) of real
! Profit from production
COST: array(JOBS) of real
! Cost of production
CAP: integer! Available resource quantity
totalProfit: cpfloatvar
task: array(JOBS) of cptask
intermProd: cpresource
end-declarations! Task objects for jobs
! Non-renewable resource (intermediate prod.)

initializations from ’Data/renewa.dat’[MIND,MAXD] as ’DUR’ RESAMT HORIZON PROFIT COST CAP
end-initializations! Setting up resources
set_resource_attributes(intermProd, KALIS_DISCRETE_RESOURCE, CAP)
setname(intermProd, "IntP")! Setting up the tasks
forall(j in JOBS) do
setname(task(j), j)
setduration(task(j), MIND(j), MAXD(j))
setdomain(getend(task(j)), 0, HORIZON)
end-do! Providing tasks
forall(j in FIRST) provides(task(j), RESAMT(j), intermProd)! Requiring tasks
forall(j in FINAL) requires(task(j), RESAMT(j), intermProd)! Objective function: total profit
totalProfit = sum(j in FINAL) PROFIT(j)*getduration(task(j)) sum(j in JOBS) COST(j)*getduration(task(j))
cp_set_solution_callback("solution_found")setparam("KALIS_MAX_COMPUTATION_TIME", 30)! Solve the problem
starttime:= gettime
if cp_schedule(totalProfit,true)=0 thenexit(1)
end-if! Solution printing
writeln("Total profit: ", getsol(totalProfit))
writeln("Job\tStart\tEnd\tDuration")
forall(j in JOBS)
writeln(j, "\t ", getsol(getstart(task(j))), "\t ", getsol(getend(task(j))),"\t ", getsol(getduration(task(j))))procedure solution_foundwriteln(gettime-starttime , " sec. Solution found with total profit = ",getsol(totalProfit))
forall(j in JOBS)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

88

Schedulingwrite(j, ": ", getsol(getstart(task(j))), "-", getsol(getend(task(j))),"(", getsol(getduration(task(j))), "), ")writeln
end-procedure
end-model

The model for case B adds the two auxiliary tasks (forming the set ENDFIRST) that mark thecompletion of the jobs in the first stage. The only other difference are the task properties
produces and consumes that define the resource constraints. We only repeat the relevant part ofthe model:
declarations
FIRST = {’P1’,’P2’}
ENDFIRST = {’EndP1’, ’EndP2’}
FINAL = {’P3’,’P4’,’P5’}
JOBS = FIRST+ENDFIRST+FINAL
MIND,MAXD: array(JOBS) of integer ! Limits on job durations
RESAMT: array(JOBS) of integer ! Resource use/production
HORIZON: integer! Time horizon
PROFIT: array(FINAL) of real
! Profit from production
COST: array(JOBS) of real
! Cost of production
CAP: integer! Available resource quantity
totalProfit: cpfloatvar
task: array(JOBS) of cptask
intermProd: cpresource
end-declarations! Task objects for jobs
! Non-renewable resource (intermediate prod.)

initializations from ’Data/renewb.dat’[MIND,MAXD] as ’DUR’ RESAMT HORIZON PROFIT COST CAP
end-initializations! Setting up resources
set_resource_attributes(intermProd, KALIS_DISCRETE_RESOURCE, CAP)
setname(intermProd, "IntP")! Setting up the tasks
forall(j in JOBS) do
setname(task(j), j)
setduration(task(j), MIND(j), MAXD(j))
setdomain(getend(task(j)), 0, HORIZON)
end-do! Production tasks
forall(j in ENDFIRST) produces(task(j), RESAMT(j), intermProd)
forall(j in FIRST) getend(task(j)) = getend(task("End"+j))! Consumer tasks
forall(j in FINAL) consumes(task(j), RESAMT(j), intermProd)

5.5.3

Results
The behavior of the (default) search and the results of the two models are considerably different.
The optimal solution with an objective of 344.9 for case B represented in Figure 5.3 is proven
within a fraction of a second. Finding a good solution for case A takes several seconds on astandard PC; finding the optimal solution (see Figure 5.2) and proving its optimality requires
several minutes of running time. The main reason for this poor behavior of the search is our
choice of the objective function: the cost-based objective function does not propagate well andtherefore does not help with pruning the search tree. A better choice for objective functions inscheduling problems generally are criteria involving the task decision variables (start, duration, orcompletion time, particularly the latter).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information89

Scheduling

Figure 5.2: Solution for case A (resource provision and requirement)

Figure 5.3: Solution for case B (resource production and consumption)

5.5.4

Alternative formulation without scheduling objects
Instead of defining task and resource objects we may equally formulate this problem with a‘producer-consumer’ constraint over standard finite domain variables that represent the different
attributes of tasks without being grouped into a predefined object. A single ‘producer-consumer’
constraint expresses the problem of scheduling a set of tasks producing or consuming a
non-renewable resource by establishing the following relations between its arguments (sevenarrays of decision variables for the properties related to tasks—start, duration, end, per unit andcumulated resource production, per unit and cumulated resource consumption— all indexed by
the same set R):∀j ∈ R : startj + durationj = endj
∀j ∈ R : producej · durationj = psizej∀j ∈ R : consumej · durationj = csizejX∀t ∈ TIMES :(producej − consumej ) ≥ 0
j∈R|t∈[UB(startj )..LB(endj )]where UB stands for ‘upper bound’ and LB for ‘lower bound’ of a decision variable.

5.5.5

Implementation
The following Mosel model implements the second model version using the producer_consumer
constraint.
model "Non-renewable resource"

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

90

Schedulinguses "kalis"
setparam("KALIS_DEFAULT_LB", 0)declarations
FIRST = {’P1’,’P2’}
ENDFIRST = {’EndP1’, ’EndP2’}
FINAL = {’P3’,’P4’,’P5’}
JOBS = FIRST+ENDFIRST+FINALPCJOBS = ENDFIRST+FINAL
MIND,MAXD: array(JOBS) of integer ! Limits on job durations
RESAMT: array(JOBS) of integer ! Resource use/production
HORIZON: integer! Time horizon
PROFIT: array(FINAL) of real
! Profit from production
COST: array(JOBS) of real
! Cost of production
CAP: integer! Available resource quantity
totalProfit: cpfloatvar
fstart,fdur,fcomp: array(FIRST) of cpvar! Start, duration & completion of jobs
start,dur,comp: array(PCJOBS) of cpvar ! Start, duration & completion of jobs
produce,consume: array(PCJOBS) of cpvar ! Production/consumption per time unit
psize,csize: array(PCJOBS) of cpvar! Cumulated production/consumption
end-declarations
initializations from ’Data/renewb.dat’[MIND,MAXD] as ’DUR’ RESAMT HORIZON PROFIT COST CAP
end-initializations! Setting up the tasks
forall(j in PCJOBS) do
setname(start(j), j)
setdomain(dur(j), MIND(j), MAXD(j))
setdomain(comp(j), 0, HORIZON)
start(j) + dur(j) = comp(j)end-doforall(j in FIRST) do
setname(fstart(j), j)
setdomain(fdur(j), MIND(j), MAXD(j))
setdomain(fcomp(j), 0, HORIZON)
fstart(j) + fdur(j) = fcomp(j)end-do! Production tasks
forall(j in ENDFIRST) do
produce(j) = RESAMT(j)consume(j) = 0
end-doforall(j in FIRST) fcomp(j) = comp("End"+j)! Consumer tasks
forall(j in FINAL) do
consume(j) = RESAMT(j)produce(j) = 0
end-do! Resource constraint
producer_consumer(start, comp, dur, produce, psize, consume, csize)! Objective function: total profit
totalProfit = sum(j in FINAL) PROFIT(j)*dur(j) sum(j in FIRST) COST(j)*fdur(j)if not cp_maximize(totalProfit) thenexit(1)
end-ifwriteln("Total profit: ", getsol(totalProfit))
writeln("Job\tStart\tEnd\tDuration")

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

91

Schedulingforall(j in FIRST)
writeln(j, "\t ", getsol(fstart(j)), "\t ", getsol(fcomp(j)),"\t ", getsol(fdur(j)))
forall(j in PCJOBS)
writeln(j, "\t ", getsol(start(j)), "\t ", getsol(comp(j)),"\t ", getsol(dur(j)))
end-modelThis model generates the same solution as the previous model version with a slightly longer
running time (though still just a fraction of a second on a standard PC).

5.6

Extensions: setup times, resource choice, usage profiles

5.6.1

Setup times
Consider once more the problem of planning the production of paint batches introduced in
Section 3.8. Between the processing of two batches the machine needs to be cleaned. The
cleaning (or setup) times incurred are sequence-dependent and asymetric. The objective is todetermine a production cycle of the shortest length.
5.6.1.1

Model formulation

For every job j (j ∈ JOBS = {1, . . . , NJ}), represented by a task object taskj , we are given its
processing duration DURj . We also have a matrix of cleaning times CLEAN with entries CLEANjk
indicating the duration of the cleaning operation if task k succedes task j. The machineprocessing the jobs is modeled as a resource res of unitary capacity, thus stating the disjunctions
between the jobs.
With the objective to minimize the makespan (completion time of the last batch) we obtain thefollowing model:
resource res
tasks taskj (j ∈ JOBS)
minimize finish
finish = maximumj∈JOBS (taskj . end)
res. capacity = 1∀j ∈ JOBS : taskj . duration = DURj∀j ∈ JOBS : taskj . requirementres = 1∀j, k ∈ JOBS : setup(taskj , taskk ) = CLEANjk
The tricky bit in the formulation of the original problem is that we wish to minimize the cycle
time, that is, the completion of the last job plus the setup required between the last and the firstjobs in the sequence. Since our task-based model does not contain any information about thesequence or rank of the jobs we introduce auxiliary variables firstjob and lastjob for the index
values of the jobs in the first and last positions of the production cycle, and a variable cleanlf forthe duration of the setup operation between the last and first tasks. The following constraints
express the relations between these variables and the task objects:
firstjob, lastjob ∈ JOBS
firstjob 6= lastjob∀j ∈ JOBS : taskj . end = finish ⇔ lastjob = j∀j ∈ JOBS : taskj . start = 1 ⇔ firstjob = j

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

92

Schedulingcleanlf = CLEANlastjob,firstjob
Minimizing the cycle time then corresponds to minimizing the sum finish + cleanlf.
5.6.1.2

Implementation

The following Mosel model implements the task-based model formulated above. The setup times
between tasks are set with the procedure setsetuptimes indicating the two task objects and thecorresponding duration value.
model "B-5 Paint production (CP)"uses "kalis"declarations
NJ = 5
JOBS=1..NJ! Number of paint batches (=jobs)

DUR: array(JOBS) of integer! Durations of jobs
CLEAN: array(JOBS,JOBS) of integer ! Cleaning times between jobs
task: array(JOBS) of cptask
res: cpresource
firstjob,lastjob,cleanlf,finish: cpvar
L: cpvarlist
cycleTime: cpvar! Objective variable
Strategy: array(range) of cpbranchingend-declarations
initializations from ’Data/b5paint.dat’
DUR CLEAN
end-initializations! Setting up the resource (formulation of the disjunction of tasks)
set_resource_attributes(res, KALIS_UNARY_RESOURCE, 1)! Setting up the tasks
forall(j in JOBS) getstart(task(j)) >= 1
! Start times
forall(j in JOBS) set_task_attributes(task(j), DUR(j), res) ! Dur.s + disj.
forall(j,k in JOBS) setsetuptime(task(j), task(k), CLEAN(j,k), CLEAN(k,j))! Cleaning times between batches! Cleaning time at end of cycle (between last and first jobs)
setdomain(firstjob, JOBS); setdomain(lastjob, JOBS)
firstjob <> lastjob
forall(j in JOBS) equiv(getend(task(j))=getmakespan, lastjob=j)
forall(j in JOBS) equiv(getstart(task(j))=1, firstjob=j)cleanlf = element(CLEAN, lastjob, firstjob)
forall(j in JOBS) L += getend(task(j))
finish = maximum(L)! Objective: minimize the duration of a production cycle
cycleTime = finish - 1 + cleanlf! Solve the problem
if cp_schedule(cycleTime) = 0 thenwriteln("Problem is infeasible")exit(1)
end-ifcp_show_stats! Solution printing
declarations
SUCC: array(JOBS) of integer
end-declarations

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

93

Schedulingforall(j in JOBS)
forall(k in JOBS)
if getsol(getstart(task(k))) = getsol(getend(task(j)))+CLEAN(j,k) then
SUCC(j):= k
break
end-ifwriteln("Minimum cycle time: ", getsol(cycleTime))
writeln("Sequence of batches:\nBatch Start Duration Cleaning")
forall(k in JOBS)
writeln(" ", k, strfmt(getsol(getstart(task(k))),7), strfmt(DUR((k)),8),
strfmt(if(SUCC(k)>0, CLEAN(k,SUCC(k)), getsol(cleanlf)),9))end-model

5.6.1.3

Results

The results are similar to those reported in Section 3.8. It should be noted here that this model
formulation is less efficient, in terms of search nodes and running times, than the previous modelversions, and in particular the ’cycle’ constraint version presented in Section 3.10. However, thetask-based formulation is more generic and easier to extend with additional features than the
problem-specific formulations in the previous model versions.
The graphical representation of the results looks as follows (Figure 5.4).

Figure 5.4: Solution graph

5.6.2

Alternative resources
Quite frequently in scheduling applications the assignment of tasks to resources is not entirely
fixed from the outset. For instance, there may be a group of resources (identical or not) among
which to choose for a given processing step. If the resources are identical the task will have thesame properties (duration, amount of resource use/provision/consumption/production)
independent of the resource used for its processing. Otherwise, if resources are non-identical
there is some resource-dependent data component.
We shall show here how to formulate a tiny example of four tasks that may be processed by two
non-identical machines. Each task must be assigned to a single machine. The resource usage pertask depends on the machine it is assigned to.
5.6.2.1

Model formulation

For each task j in the set of tasks TASKS we are given a fixed duration DURj and amachine-dependent amount of resource REQjm that is required per time unit for the whole
duration of the task. Both machines have the same capacity CAP.
The resulting model looks as follows.
resource resm (m ∈ MACH)
tasks taskj (j ∈ TASKS)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

94

Schedulingminimize makespan∀m ∈ MACH : resm . capacity = CAP∀j ∈ TASKS : taskj . start, taskj . end ∈ {0, . . . , HORIZON}∀j ∈ TASKS : taskj . duration = DURt∀j ∈ TASKS, m ∈ MACH : taskj . assignmentresm ∈ {0, 1}
X∀j ∈ TASKS :taskj . assignmentresm = 1
m∈MACH∀j ∈ TASKS, m ∈ MACH : taskj . requirementresm ∈ {0, REQjm }5.6.2.2

Implementation

This is a Mosel implementation of the scheduling problem with alternative resources.
uses "kalis"
setparam("KALIS_DEFAULT_LB", 0)declarations
TASKS = {"a","b","c","d"}MACH = {"M1", "M2"}
USE: array(TASKS,MACH) of integer
DUR: array(TASKS) of integer
T: array(TASKS) of cptask
R: array(MACH) of cpresource
end-declarations! Index set of tasks! Index set of resources! Machine-dependent res. requirement! Durations of tasks! Tasks! Resources

DUR::(["a","b","c","d"])[7, 9, 8, 5]
USE::(["a","b","c","d"],["M1","M2"])[
4, 3,
2, 3,
2, 1,
4, 5]
! Define discrete resources
forall(m in MACH)
set_resource_attributes(R(m), KALIS_DISCRETE_RESOURCE, 5)! Define tasks with machine-dependent resource usages
forall(j in TASKS) do
T(j).duration:= DUR(j)T(j).name:= jrequires(T(j), union(m in MACH) {resusage(R(m), USE(j,m))})end-docp_set_solution_callback("print_solution")starttime:=timestamp! Solve the problem
if cp_schedule(getmakespan)=0 thenwriteln("No solution")exit(0)end-if! Solution printing
forall(j in TASKS)
writeln(j, ": ", getsol(getstart(T(j))), " - ", getsol(getend(T(j))))forall(t in 1..getsol(getmakespan)) dowrite(strfmt(t-1,2), ": ")! We cannot use ’getrequirement’ here to access solution information! (it returns a value corresponding to the current state, that is 0)
forall(j in TASKS | t>getsol(getstart(T(j))) and t<=getsol(getend(T(j))))Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information95

Schedulingwrite(j, ":",
sum(m in MACH) USE(j,m)*getsol(getassignment(T(j),R(m))), "writeln
end-do" )! ****************************************************************! Print solutions during enumeration at the node where they are foundprocedure print_solution
writeln(timestamp-starttime, "sec. Solution: ", getsol(getmakespan))
forall(m in MACH) do
writeln(m, ":")
forall(t in 0..getsol(getmakespan)-1) dowrite(strfmt(t,2), ": ")forall(j in TASKS | getrequirement(T(j), R(m), t)>0)
write(j, ":", getrequirement(T(j), R(m), t), " " )writeln(" (total ", sum(j in TASKS) getrequirement(T(j), R(m), t), ")" )end-doend-doend-procedure
end-model

A new feature introduced by this example are the resusage objects that are employed in thedefinition of the resource requirement constraints for the tasks. A resusage consists of a resource
object and a resource usage (specified by a constant, lower and upper bounds, or a complete
profile — see Section 5.6.3). In this example we use the simplest version with a fixed resource
usage value. Optional third and forth arguments to requires can be defined to specify theminimum and maximum number of resources to be used by a task. The default version (employedin this example) will choose a single resource from the set of alternative resources.
The implementation also shows how to retrieve solution information about resource assignments
at a solution node (that is, during the enumeration) and after the search. At the solution node
the function getrequirement returns the desired resource usage information; for a solution
summary after terminating the search we need to work with the decision variable obtained
through getassignment.
The formulation of produces, consumes, and provides constraints with resusage objects is
analogous to what we have shown here for requires.
Note: when implementing alternative resources you always have to use the resource type
KALIS_DISCRETE_RESOURCES, setting a capacity limit of 1 for modeling disjunctive resources.
5.6.2.3

Results

Figure 5.5 shows two solutions generated by the execution of our model. The first solution uses alesser total amount resource but the second one is optimal with respect to the objective ofminimizing the makespan.
Note: leaving the decision about the resource choice open for the solver considerably increases
the complexity of a scheduling problem. We therefore recommend to use this feature sparingly.
Optimization problems involving resource assignment and sequencing aspects are often moreeasily solved by a decompostion approach (see the Xpress Whitepaper Hybrid MIP/CP solving with
Xpress Optimizer and Xpress Kalis).

5.6.3

Resource profiles
In all preceding examples we have worked with the assumption that a task is defined by a

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information96

Scheduling

Figure 5.5: Solutions for scheduling with resource choice

Figure 5.6: Task profiles

constant, though not necessarily fixed resource requirement (respectively resource provision,
consumption, or production). Following this line of thought, a sequence of processesing steps
with different resource usages would be represented by a corresponding number of tasks, eachwith a constant resource usage. However, the number of cptask objects required by such aformulation may be prohibitively large. Kalis therefore offers the possibility to define profiledtasks, that is, tasks with a non-constant resource usage profile. A task resource usage profilestates for every time unit of the execution of the task the corresponding amount of resource. For
example the four tasks in Figure 5.6 have the profiles Profilea : (12, 12, 6, 2, 2, 2, 2), Profileb : (12,12, 6, 2, 2, 2, 2, 2, 2), Profilec : (12, 12, 3, 3, 3, 3, 3, 3), and Profiled : (6, 6, 6, 6, 6) respectively.
5.6.3.1

Model formulation

Let TASKS = {0 a0 ,0 b0 ,0 c0 ,0 d0 } be the set of tasks and res a resource of capacity CAP required by alltasks for their execution. With the objective of minimizing the makespan of the schedule we may
formulate the model as follows.
resource res
tasks taskj (j ∈ TASKS)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

97

Schedulingminimize makespanres. capacity = CAP∀j ∈ TASKS : taskj . start, taskj . end ∈ {0, . . . , HORIZON}∀j ∈ TASKS : taskj . duration = DURj∀j ∈ TASKS : taskj . requirementres = Profilej
This model formulation differs from a standard cumulative scheduling model (see Section 5.4 only
in a single point: the resource requirement Profilej of a task j is a list of values and not just asingle constant.
5.6.3.2

Implementation

Let us now take a look at the model formulation with Mosel.
uses "kalis"
setparam("KALIS_DEFAULT_LB", 0)declarations
TASKS = {"a","b","c","d"}! Index set of tasks
Profile: array(TASKS) of list of integer! Task profiles
DUR: array(TASKS) of integer! Durations of tasks
T: array(TASKS) of cptask
R: cpresource
end-declarations! Tasks! Cumulative resource

DUR::(["a","b","c","d"])[7, 9, 8, 5]
Profile("a"):= [12, 12, 6, 2, 2, 2, 2]
Profile("b"):= [12, 12, 6, 2, 2, 2, 2, 2, 2]
Profile("c"):= [12, 12, 3, 3, 3, 3, 3, 3]
Profile("d"):= [6, 6, 6, 6, 6]! Define a discrete resource
set_resource_attributes(R, KALIS_DISCRETE_RESOURCE, 18)
R.name:="machine"! Define tasks with profiled resource usage
forall(t in TASKS) do
T(t).duration:= DUR(t)T(t).name:= trequires(T(t), resusage(R, Profile(t)))
end-docp_set_solution_callback("print_solution")starttime:=timestamp! Solve the problem
if cp_schedule(getmakespan)=0 thenwriteln("No solution")exit(0)end-if! Solution printing
writeln("Schedule with makespan ", getsol(getmakespan), ":")
forall(t in TASKS)
writeln(t, ": ", getsol(getstart(T(t))), " - ", getsol(getend(T(t))))! ****************************************************************! Print solutions during enumeration at the node where they are found.
! ’getrequirement’ can only be used here to access solution information,! not after the enumeration (it returns a value corresponding to the! current state, that is, 0 after the enumeration).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information98

Schedulingprocedure print_solution
writeln(timestamp-starttime, "sec. Solution: ", getsol(getmakespan))
forall(i in 0..getsol(getmakespan)-1) dowrite(strfmt(i,2), ": ")forall(t in TASKS | getrequirement(T(t), R, i)>0)
write(t, ":", getrequirement(T(t), R, i), " " )writeln(" (total ", sum(t in TASKS) getrequirement(T(t), R, i), ")" )end-doend-procedure
end-model

The statement of the resource constraints (requires) uses an additional type of scheduling object
for the definition of the resource profiles, namely resusage. We have already encountered thisobject in Section 5.6.2 where it was employed in the definition of sets of alternative resources. In
the present case there is only a single resource that must be used by all tasks, we now employ
resusage to define resource usage profiles.
5.6.3.3

Results

The chart in Figure 5.7 shows an optimal schedule of the four tasks on a resource with capacity
18. All tasks are completed by time 11.

Figure 5.7: Solution for scheduling with resource profile

5.6.4

Resource idle times and preemption of tasks
In the examples of cumulative scheduling we have looked at so far resources are defined with afixed constant capacity. In reality, it often happens that the resource availability is not constantover time: a resource ’staff’, for instance, is likely to show variations corresponding to thepresence or absence of personnel. Such changes to the resource level can be defined periodwise
with the subroutine setcapacity. In the case of machine resources there may be scheduled
downtimes for maintenance or other breaks, such as week-ends, relating to working hours. Anysuch periods that are known from the outset should be marked as ’unavailable for processing
tasks’.
From the perspective of tasks there are two cases of resource unavailability: (1) any task starting
before the resource unavailability must also be finished before the begin of this period (generally

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information99

Schedulingknown as non-preemptive scheduling), and (2) a task started before the unavailability resumes its
processing once the resource becomes available again (the case of preemptive scheduling).
With Kalis, the first case applies when resource capacities are set to 0 using setcapacity(independent of the type of the task). The second case is modeled by using profiled tasks andindicating resource unavailability with setidletimes.
For simplicity’s sake, we merely consider two tasks, a and b, that are to be scheduled on a
resource of capacity 3 that is unavailable in certain time periods. Task a has a constant resource
requirement of 1 for 4 units of time, task b has the resource usage profile (1,1,1,2,2,2,1,1). Bothtasks are preemptive.
5.6.4.1

Model formulation

Let TASKS = {0 a0 ,0 b0 } be the set of tasks and res a resource of capacity CAP required by the tasks
for their execution. The set IDLESET contains the time periods during which the resource isunavailable preempting the processing of tasks. With the objective of minimizing the makespanof the schedule we may formulate the model as follows.
resource res
tasks taskj (j ∈ TASKS)
minimize makespanres. capacity = CAP
res. idletimes = IDLESET∀j ∈ TASKS : taskj . start, taskj . end ∈ {0, . . . , HORIZON}∀j ∈ TASKS : taskj . duration ≥ DURj∀j ∈ TASKS : taskj . requirementres = Profilej
Please notice that we do not fix the durations of the tasks in this formulation: we may indicate(lower or upper) bounds to restrict the total duration of a task, but if we want to leave room forpreemptions the bounds on the durations of tasks must include some slack.
5.6.4.2

Implementation

The following model shows how to implement our example problem with Mosel.
model "Preemption"
uses "kalis"
setparam("KALIS_DEFAULT_LB", 0)declarations
aprofile,bprofile: list of integera,b: cptask
R: cpresource
end-declarations! Define a discrete resource
set_resource_attributes(R, KALIS_DISCRETE_RESOURCE, 3)! Create a ’hole’ in the availability of the resource:! Uncomment one of the following two lines to compare their effect! setcapacity(R, 1, 2, 0); setcapacity(R, 7, 8, 0)
setidletimes(R, (1..2)+(7..8))! Define two tasks (a: constant resource use, b: resource profile)a.duration >= 4

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

100Schedulinga.name:= "task_a"aprofile:= [1,1,1,1]b.duration >= 8b.name:= "task_b"
bprofile:= [1,1,1,2,2,2,1,1]! Resource usage constraints
requires(a, resusage(R,aprofile))
requires(b, resusage(R,bprofile))
cp_set_solution_callback("print_solution")! Solve the problem
if cp_schedule(getmakespan)<>0 thencp_show_sol
else
writeln("No solution")
end-if! ****************************************************************
procedure print_solution
writeln("Solution: ", getsol(getmakespan))writeln("Schedule: a: ", getsol(getstart(a)), "-", getsol(getend(a))-1,", b: ", getsol(getstart(b)), "-", getsol(getend(b))-1)
writeln("Resource usage:")forall(t in 0..getsol(getmakespan)-1)
writeln(strfmt(t,5), ": Cap: ", getcapacity(R,t), ", a:",getrequirement(a, R, t), ", b:", getrequirement(b, R, t))
end-procedure
end-model

There are several equivalent ways of stating the constant resource usage of task a. Instead ofdefining explicitly the complete profile we may simply write
requires(a, resusage(R,1))

or even shorter:
requires(a, 1, R)

5.6.4.3

Results

The model shown above produces the following solution output.
Solution: 12
Schedule: a: 0-5, b: 0-11
Resource usage:
0: Cap: 3, a:1, b:1
1: Cap: 3, a:0, b:0
2: Cap: 3, a:0, b:0
3: Cap: 3, a:1, b:1
4: Cap: 3, a:1, b:1
5: Cap: 3, a:1, b:2
6: Cap: 3, a:0, b:2
7: Cap: 3, a:0, b:0
8: Cap: 3, a:0, b:0
9: Cap: 3, a:0, b:2
10: Cap: 3, a:0, b:1
11: Cap: 3, a:0, b:1

The same model, replacing the line

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

101

Schedulingsetidletimes(R, (1..2)+(7..8))by this version indicating non-preemptive resource unavailability
setcapacity(R, 1, 2, 0);

setcapacity(R, 7, 8, 0)

results in the following solution where the tasks are placed in such a way that they do not
overlap with any ’hole’ in resource availability.
Solution: 17
Schedule: a: 3-6, b: 9-16
Resource usage:
0: Cap: 3, a:0, b:0
1: Cap: 0, a:0, b:0
2: Cap: 0, a:0, b:0
3: Cap: 3, a:1, b:0
4: Cap: 3, a:1, b:0
5: Cap: 3, a:1, b:0
6: Cap: 3, a:1, b:0
7: Cap: 0, a:0, b:0
8: Cap: 0, a:0, b:0
9: Cap: 3, a:0, b:1
10: Cap: 3, a:0, b:1
11: Cap: 3, a:0, b:1
12: Cap: 3, a:0, b:2
13: Cap: 3, a:0, b:2
14: Cap: 3, a:0, b:2
15: Cap: 3, a:0, b:1
16: Cap: 3, a:0, b:1

It is also possible to define both, preemptive and non-preemptive times of unavailability for thesame resource. For example, if times 1-2 correspond to a weekend where products may remainon the machine R and times 7-8 are required for maintenance operations during which themachine must imperatively be empty we would state in our model:
setidletimes(R, 1, 2, 0)
setcapacity(R, (7..8))In this case the execution of task a may start at time 0, whereas task b will again be processed intimes 9-16.

5.7

Enumeration
In the previous scheduling examples we have used the default enumeration for schedulingproblems, invoked by the optimization function cp_schedule. The built-in search strategies usedby the solver in this case are particularly suited if we wish to minimize the completion time of aschedule. With other objectives the built-in strategies may not be a good choice, especially if themodel contains decision variables that are not part of scheduling objects (the built-in strategies
always enumerate first the scheduling objects) or if we wish to maximize an objective. Xpress
Kalis makes it therefore possible to use the standard optimization functions cp_minimize andcp_maximize in models that contain scheduling objects, the default search strategies employed bythese optimization functions being different from the scheduling-specific ones. In addition, theuser may also define his own problem-specific enumeration as shown in the following examples.
User-defined enumeration strategies for scheduling problems may take two different forms:
variable-based and task-based. The former case is the subject of Chapter 4, and we only give asmall example here (Section 5.7.1). The latter will be explained with some more detail by themeans of a job-shop scheduling example.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

102

Scheduling

5.7.1

Variable-based enumeration
When studying the problem solving statistics for the bin packing problem in Section 5.4 we findthat the enumeration using the default scheduling search strategies requires several hundred
nodes to prove optimality. With a problem-specific search strategy we may be able to do better!
Indeed, we shall see that a greedy-type strategy, assigning the largest files first, to the first disk
with sufficient space is clearly more efficient.
5.7.1.1

Using cp_minimize

The only decisions to make in this problem are the assignments of files to disks, that is, choosing avalue for the start time variables of the tasks. The following lines of Mosel code order the tasks indecreasing order of file sizes and define an enumeration strategy for their start times assigningeach the smallest possible disk number first. Notice that the sorting subroutine qsort is definedby the module mmsystem that needs to be loaded with a uses statement at the beginning of themodel.
declarations
Strategy: array(range) of cpbranching
FSORT: array(FILES) of integer
end-declarations
qsort(SYS_DOWN, SIZE, FSORT)! Sort files in decreasing order of size
forall(f in FILES)
Strategy(f):=assign_var(KALIS_SMALLEST_MIN, KALIS_MIN_TO_MAX,{getstart(file(FSORT(f)))})
cp_set_branching(Strategy)
if not cp_minimize(diskuse) then writeln("Problem infeasible"); end-if

The choice of the variable selection criterion (first argument of assign_var) is not really
important here since every strategy Strategyf only applies to a single variable and hence noselection takes place. Equivalently, we may have written
declarations
Strategy: cpbranching
FSORT: array(FILES) of integer
LS: cpvarlist
end-declarations
qsort(SYS_DOWN, SIZE, FSORT)! Sort files in decreasing order of size
forall(f in FILES)
LS+=getstart(file(FSORT(f)))
Strategy:=assign_var(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX, LS)
cp_set_branching(Strategy)
if not cp_minimize(diskuse) then writeln("Problem infeasible"); end-if

With this search strategy the first solution found uses 3 disks, that is, we immediately find an
optimal solution. The whole search terminates after 17 nodes and takes only a fraction of thetime needed by the default scheduling or minimization strategies.
5.7.1.2

Using cp_schedule

The scheduling search consists of a pretreatment (shaving) phase and two main phases(KALIS_INITIAL_SOLUTION and KALIS_OPTIMAL_SOLUTION) for which the user may specify
enumeration strategies by calling cp_set_schedule_search with the corresponding phaseselection. The ‘initial solution’ phase aims at providing quickly a good solution whereas the

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

103

Scheduling‘optimal solution’ phase proves optimality. Any search limits such as maximum number of nodes
apply separately to each phase, an overall time limit (parameter KALIS_MAX_COMPUTATION_TIME)
only applies to the last phase.
The definition of variable-based branching schemes for the scheduling search is done in exactly
the same way as what we have seen previously for standard search with cp_minimize or
cp_maximize, replacing cp_set_strategy by cp_set_schedule_strategy:
cp_set_schedule_branching(KALIS_INITIAL_SOLUTION, Strategy)
if cp_schedule(diskuse)=0 then writeln("Problem infeasible"); end-if

With this search strategy, the optimal solution is found in the ’initial solution’ phase after just 8
nodes and the enumeration stops there since the pretreatment phase has proven a lower boundof 3 which is just the value of the optimal solution.
NB: to obtain an output log from the different phases of the scheduling search set the control
parameter KALIS_VERBOSE_LEVEL to 2, that is, add the following line to your model before thestart of the solution algorithm.
setparam("KALIS_VERBOSE_LEVEL", 2)

5.7.2

Task-based enumeration
A task-based enumeration strategy consists in the definition of a selection strategy choosing thetask to be enumerated, a value selection heuristic for the task durations, and a value selection
heuristic for the task start times.
Consider the typical definition of a job-shop scheduling problem: we are given a set of jobs thateach need to be processed in a fixed order by a given set of machines. A machine executes one
job at a time. The durations of the production tasks (= processing of a job on a machine) and thesequence of machines per job for a 6 × 6 instance are shown in Table 5.3. The objective is tominimize the makespan (latest completion time) of the schedule.
Table 5.3: 6 × 6 job-shop instance from [FM63]
Job
1
2
3
4
5
6

5.7.2.1

Machines
3
2
3
2
3
2

1
3
4
1
2
4

2
5
6
3
5
6

4
6
1
4
6
1

Durations
6
1
2
5
1
5

5
4
5
6
4
3

1
8
5
5
9
3

3
5
4
5
3
3

6
10
8
5
5
9

7
10
9
3
4
10

3
10
1
8
3
4

6
4
7
9
1
1

Model formulation

Let JOBS denote the set of jobs and MACH (MACH = {1, . . . , NM}) the set of machines. Every job j
is produced as a sequence of tasks taskjm where taskjm needs to be finished before taskj,m+1 canstart. A task taskjm is processed by the machine RESjm and has a fixed duration DURjm .
The following model formulates the job-shop scheduling problem.

resources resm (m ∈ MACH = {1, . . . , NM})
tasks taskjm (j ∈ JOBS, m ∈ MACH)
minimize finish

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

104

Schedulingfinish = maximumj∈JOBS (taskj,NM . end)∀m ∈ MACH : resm . capacity = 1∀j ∈ JOBS, m ∈ MACH : taskjm . start, taskjm . end ∈ {0, . . . , MAXTIME}∀j ∈ JOBS, m ∈ {1, . . . , NM − 1} : taskjm . successors = {taskj,m+1 }∀j ∈ JOBS, m ∈ MACH : taskjm . duration = DURjm∀j ∈ JOBS, m ∈ MACH : taskjm . requirementRESjm = 1

5.7.2.2

Implementation

The following Mosel model implements the job-shop scheduling problem and defines atask-based branching strategy for solving it. We select the task that has the smallest remaining
domain for its start variable and enumerate the possible values for this variable starting with thesmallest. A task-based branching strategy is defined in Xpress Kalis with the function
task_serialize, that takes as arguments the user task selection, value selection strategies for theduration and start variables, and the set of tasks it applies to. Such task-based branchingstrategies can be combined freely with any variable-based branching strategies.
model "Job shop (CP)"uses "kalis", "mmsystem"
parameters
DATAFILE = "jobshop.dat"
NJ = 6
NM = 6
end-parameters! Number of jobs
! Number of resources

forward function select_task(tlist: cptasklist): integer
declarations
JOBS = 1..NJ
MACH = 1..NM
RES: array(JOBS,MACH) of integer
DUR: array(JOBS,MACH) of integer
res: array(MACH) of cpresource
task: array(JOBS,MACH) of cptask
end-declarations! Set of jobs
! Set of resources! Resource use of tasks! Durations of tasks! Resources! Tasks

initializations from "Data/"+DATAFILERES DUR
end-initializations
HORIZON:= sum(j in JOBS, m in MACH) DUR(j,m)
forall(j in JOBS) getend(task(j,NM)) <= HORIZON! Setting up the resources (capacity 1)
forall(m in MACH)
set_resource_attributes(res(m), KALIS_UNARY_RESOURCE, 1)! Setting up the tasks (durations, resource used)
forall(j in JOBS, m in MACH)
set_task_attributes(task(j,m), DUR(j,m), res(RES(j,m)))! Precedence constraints between the tasks of every job
forall (j in JOBS, m in 1..NM-1)! getstart(task(j,m)) + DUR(j,m) <= getstart(task(j,m+1))
setsuccessors(task(j,m), {task(j,m+1)})! Branching strategy
Strategy:=task_serialize("select_task", KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX,

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

105

Scheduling

union(j in JOBS, m in MACH | exists(task(j,m))) {task(j,m)})cp_set_branching(Strategy)! Solve the problem
starttime:= gettime
if not cp_minimize(getmakespan) thenwriteln("Problem is infeasible")exit(1)
end-if! Solution printing
cp_show_stats
write(gettime-starttime, "sec ")writeln("Total completion time: ", getsol(getmakespan))
forall(j in JOBS) do
write("Job ", strfmt(j,-2))
forall(m in MACH | exists(task(j,m)))write(strfmt(RES(j,m),3), ":", strfmt(getsol(getstart(task(j,m))),3),"-", strfmt(getsol(getend(task(j,m))),2))
writeln
end-do!*******************************************************************! Task selection for branching
function select_task(tlist: cptasklist): integer
declarations
Tset: set of integer
end-declarations! Get the number of elements of "tlist"
listsize:= getsize(tlist)! Set of uninstantiated tasks
forall(i in 1..listsize)
if not is_fixed(getstart(gettask(tlist,i))) thenTset+= {i}end-ifreturned:= 0! Get a task with smallest start time domain
smin:= min(j in Tset) getsize(getstart(gettask(tlist,j)))forall(j in Tset)if getsize(getstart(gettask(tlist,j))) = smin thenreturned:=j; break
end-ifend-function
end-model

5.7.2.3

Results

An optimal solution to this problem has a makespan of 55. In comparison with the defaultscheduling strategy, our branching strategy reduces the number of nodes that are enumerated
from over 300 to just 105 nodes with a comparable model execution time (however, for larger
instances the default scheduling strategy is likely to outperform our branching strategy). The
default minimization strategy does not find any solution for this problem within several minutes
running time.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

106

Scheduling

Figure 5.8: Solution graph5.7.2.4

Alternative search strategies

Similarly to what we have seen above, we may define a user task selection strategy for thescheduling search. The only modifications required in our model are to replace cp_set_branchingby cp_set_schedule_strategy and cp_minimize by cp_schedule. The definition of the user task
choice function select_task remains unchanged.
! Branching strategy
Strategy:=task_serialize("select_task", KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX,
union(j in JOBS, m in MACH | exists(task(j,m))) {task(j,m)})cp_set_schedule_strategy(KALIS_INITIAL_SOLUTION, Strategy)! Solve the problem
if cp_schedule(getmakespan)=0 thenwriteln("Problem is infeasible")exit(1)
end-ifThis strategy takes even fewer nodes for completing the enumeration than the standard searchwith user task selection.
Instead of the user-defined task selection function select_task it is equally possible to use one ofthe predefined task selection criteria:

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

107

Scheduling

KALIS_SMALLEST_EST / KALIS_LARGEST_EST choose task with the smallest/largest lower boundon its start time (’earliest start time’),
KALIS_SMALLEST_LST / KALIS_LARGEST_LST choose task with the smallest/largest upper boundon its start time (’latest start time’),
KALIS_SMALLEST_ECT / KALIS_LARGEST_ECT choose task with the smallest/largest lower boundon its completion time (’earliest completion time’),
KALIS_SMALLEST_LCT / KALIS_LARGEST_LCT choose task with the smallest/largest upper boundon its completion time (’latest completion time’).
For the present example, the best choice proves to be KALIS_SMALLEST_LCT (terminating thesearch after approximately 60 nodes with both cp_schedule and cp_minimize):
Strategy:=task_serialize(KALIS_SMALLEST_LCT, KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX,
union(j in JOBS, m in MACH | exists(task(j,m))) {task(j,m)})Even more specialized task selection strategies can be defined with the help of group_serialize.
In this case you may decide freely which are the variables to enumerate for a task and in which
order they are to be considered. The scope of group_serialize is not limited to tasks, you may
use this subroutine to define search strategies involving other types of (user) objects.

5.7.3

Choice of the propagation algorithm
The performance of search algorithms for scheduling problems relies not alone on the definitionof the enumeration strategy; the choice of the propagation algorithm for resource constraints
may also have a noticeable impact. The propagation type is set by an optional last argument of
the procedure set_resources_attributes, such as
set_resource_attributes(res, KALIS_DISCRETE_RESOURCE, CAP, ALG)

where ALG is the propagation algorithm choice.
For unary resources we have a choice between the algorithms KALIS_TASK_INTERVALS andKALIS_DISJUNCTIONS. The former achieves stronger pruning at the cost of a larger computational
overhead making the choice of KALIS_DISJUNCTIONS more competitive for small to medium sized
problems. Taking the example of the jobshop problem from the previous section, when using
KALIS_DISJUNCTIONS the default scheduling search is about 4 times faster than with
KALIS_TASK_INTERVALS although the number of nodes explored is slightly larger than with thelatter.
The propagation algorithm options for cumulative resources are KALIS_TASK_INTERVALS andKALIS_TIMETABLING. The filtering algorithm KALIS_TASK_INTERVALS is stronger and relatively slow
making it the preferred choice for hard, medium-sized problems whereas KALIS_TIMETABLING
should be given preference for very large problems where the computational overhead of theformer may be prohibitive. In terms of an example, the binpacking problem we have worked
with in Sections 5.4 and 5.7.1 solves about three times faster with KALIS_TASK_INTERVALS thanwith KALIS_TIMETABLING (using the default scheduling search).

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

108

C HAPTER 6

Hybridization of CP and MP
This chapter introduces the concept of LP/MIP relaxations for problems formulated as CP models
with Xpress Kalis. By means of examples we show how touse automated linear programming relaxations,

work with linear programming relaxations,

configure CP search to be guided by information from LP/MIP relaxations.

Note: The functionality described in this chapter requires Xpress Optimizer to be installed andlicensed in addition to Xpress Kalis.

6.1

Linear relaxations
Constraint Programming and Mathematical Programming (here used for Linear and Mixed
Integer Programming, LP/MIP) are two different approaches to solving optimization problems
that have a number of complementary features. Some problems, or parts of problems, are better
solved by CP, others by LP/MIP techniques. Based on this observation it is possible to devise
various approaches for hybrid CP-MP problem solving. The FICO Xpress Optimization whitepaper’Hybrid MIP/CP solving with Xpress Optimizer and Xpress Kalis’ describes several decomposition
schemes where coordination between MIP and CP models is done on the Mosel level. Xpress Kalis
now provides a built-in linear programming relaxation functionality where communication andcooperation take place directly on the solver level, with optional configuration and userinteraction from the Mosel CP model.
In the context of Xpress Kalis we use the term linear relaxation for sets of linear (in)equality
constraints that are solved by an external LP/MIP solver. In the case of an automatic relaxation
this will be a reformulation of (a subset of) the constraints in the CP problem. A user-defined’linear relaxation’, however, may also include additional information, in which case this namechoice might be somewhat misleading.
Xpress Kalis can build automatically several linear (or mixed integer linear) relaxations of a CP
problem and use Xpress Optimizer to solve them. Xpress Kalis uses a double modeling approach(as in [Hei99a]) by exchanging automatically and in a bidirectional way, information such as
objective bounds, infeasibility, optimal relaxed solutions and reduced costs between the CP solver
and the linear relaxations solver(s) during the search for a solution.
1. Linear relaxations can be generated fully automatically.
2. Alternatively, relaxations can be configured by selecting sets of constraints to form
subproblems and by defining their solving frequency.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

109

Hybridization of CP and MP

3. Relaxation problems can also be defined freely by the user; they may even include
constraints that do not occur in the original CP problem.
These three ways of defining linear relaxations are presented in the following sections.

6.2

Automatic relaxation
When developing a CP model we recommend that you always try the effect of using theautomatic relaxation. Indeed, in many of the examples presented in the previous chapters (suchas examples a4sugar_ka.mos from Section 3.6 or j5tax_ka.mos from Section 3.9) we can simplify
the model formulation by removing the definition of the search strategy and enabling theautomated relaxation by adding the following line before the start of the optimization:
setparam("kalis_auto_relax",true)

whereby in many cases you will observe that the time to the first or optimal solution is shortened,or that optimality is proven faster than with CP-only search.

6.2.1

Integer knapsack problem with side constraint
The following integer knapsack problem with an additional ’all_different’ constraint on its
variables will serve us in this and the following sections to show how to work with linear
relaxations:maximizes. t.

5 · x1 + 8 · x2 + 4 · x3 + x4
xj ∈ {1, 3, 8, 9, 12} for j = 1, 2, 3, 4
3 · x1 + 5 · x2 + 2 · x3 ≤ 50
2 · x1 + x3 + 5 · x4 ≤ 75
all-different(x1 , x2 , x3 , x4 )6.2.2

Implementation
The model implementation shown below is fairly straightforward, with the exception of thesetting of the control parameter KALIS_AUTO_RELAX.
model "Knapsack with side constraints"
uses "kalis"declarations
VALUES = {1,3,8,9,12}
R = 1..4
x: array(R) of cpvar
benefit: cpvar
end-declarations! Decision variables! The objective to minimize! Enable output printing
setparam("kalis_verbose_level", 1)! Setting name of variables for pretty printing
forall(i in R) setname(x(i),"x"+i)setname(benefit,"benefit")! Set initial domains for variables
forall(i in R) setdomain(x(i), VALUES)

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information110Hybridization of CP and MP! Knapsack constraints
3*x(1) + 5*x(2) + 2*x(3) <= 50
2*x(1) + x(3) + 5*x(4) <= 75! Additional global constraint
all_different(union(i in R) {x(i)})! Objective function
benefit = 5*x(1) + 8*x(2) + 4*x(3) + x(4)! Initial propagation
res := cp_propagate! Display bounds on objective after constraint propagation
writeln("Constraints propagation objective ", benefit)! **** Linear relaxation ****
! Enable automatic linear relaxations
setparam("kalis_auto_relax", true)! Solve the problem
if (cp_maximize(benefit)) thencp_show_sol
end-if! Output optimal solution to screen

end-model

6.2.3

Results
Enabling the automatic relaxation for this problem reduces the number of nodes spent by thesearch from 17 to 4. However, more time is spent in every node due to the overhead incurred by
the LP solving. As solving times in this small problem are negligible in all formulations timemeasurements are not really meaningful; in larger problems the effect of using linear relaxations
needs to be tested carefully.

6.3

Configuring automatic relaxations
This section and the remainder of the chapter are addressed at more expert readers who, besides
experience with CP, also have some knowledge of LP/MIP modeling and solving techniques.

6.3.1

Configuration choices
The formulation of a linear relaxation (sub)problem with Xpress Kalis has several components,
namely the problem definition (=statement of variables and constraints), the configuration of alinear relaxation solver, and its insertion into the search strategy of the original CP problem. Hereis a summary of the different steps and configuration choices.
1. Choosing the constraint typeThe following constraints can be relaxed automatically with Xpress Kalis:linear constraints



all-differentoccurrence

distribute

min/max

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

111Hybridization of CP and MPabsolute value

distanceelement



cycle



logical (implies, or, and, equiv)

To obtain an automatic relaxation of the whole problem, Xpress Kalis forms the intersectionof the relaxations of the constraints of the CP model. This relaxation can be retrieved by acall to the function cp_get_linrelax. An optional argument to this function lets you specify
the (set of) constraint types to relax. The relaxation for a specific constraint—as opposed toconstraint type—is obtained with get_linrelax.
2. Choosing the relaxation type
Xpress Kalis generally provides several distinct relaxations for a given constraint. Methods
cp_get_linrelax and get_linrelax take an integer parameter to choose the type of therelaxation (0 for an LP oriented relaxation and 1 for a MIP oriented relaxation). Besides theautomatic relaxations, the user can also freely define his own relaxations of these or otherconstraints of his CP models (see Section 6.4 below).
3. Defining relaxation solvers
To solve a linear relaxation, Xpress Kalis uses relaxation solvers (model objects of the typecplinrelaxsolver) that define for the relaxation:(a) an objective variable,(b) an optimization sense (either minimization or maximization),(c) a configuration of when and what to do with the relaxation,(d) a flag indicating whether to solve the relaxation as a pure LP problem or as a MIP.
The following predefined configurations are implemented within Xpress Kalis:
KALIS_TOPNODE_RELAX_SOLVER This configuration solves the relaxation only at the top nodeand provides bound for the objective variable.
KALIS_TREENODE_RELAX_SOLVER This configuration solves the relaxation at each node of thesearch tree and provides bounds for the objective variable and performs
reduced costs propagation.
KALIS_BILEVEL_RELAX_SOLVER This configuration solves the relaxation whenever all thevariables (by default all the discrete variables such as cpvar) of a user defined
set are instantiated. After the resolution of the relaxation, all the othervariables are instantiated to the optimal value of the relaxation. The mainuse of the bilevel configuration is to decompose simply and automatically the
CP model in a master problem and a slave problem.
In addition to the predefined schemes, the user can take full control of the relaxation solver
by means of callbacks (see Xpress Kalis reference manual for details).
Note: a model can contain several linear relaxations solvers, e.g., for solving different
subproblems or with different configuration options (such as one solver for the top node
and a different relaxation solver for the tree nodes of the CP search).
4. Branching with relaxation information
Certain predefined branching schemes and value and variable selection heuristics in Xpress
Kalis are based on the optimal solution of a relaxation. The information obtained from therelaxations can be used to explore quickly the most promising portions of the search space.
For example, a MIP style branching scheme is defined by

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

112Hybridization of CP and MP

cp_set_branching(assign_and_forbid(KALIS_LARGEST_REDUCED_COST(mysolver),KALIS_NEAREST_RELAXED_VALUE(mysolver)))

where the KALIS_LARGEST_REDUCED_COST variable selection heuristic selects the variable withthe largest reduced cost in the optimal solution of the relaxation in the specified relaxation
solver, and the KALIS_NEAREST_RELAXED_VALUE value selection heuristic selects the value inthe domain of the variable that is the nearest (using L1-Norm) to the value of this variablein the optimal solution of the relaxation in the relaxation solver passed in the argument.

6.3.2

Implementation
The model shown below implements a similar relaxation as the automatic version in the previous
section. This model has two parts: in the beginning we define a standard CP model for ourKnapsack problem and trigger constraint propagation to display the initial bounds on theobjective function. The second part shows how to define and configure a linear relaxation solver.
At first, the model generates the automatic relaxation (and displays it on screen). The argument
value 0 in cp_get_linrelax indicates that we want an LP-oriented relaxation (use 1 for a
MIP-oriented relaxation). The relaxation solver defined with get_linrelax_solver is configured
to maximize the objective benefit, solving the problem as a MIP, and this only once, at the first
node of the CP search. The linear relaxation solver is added to the search process by a call to
cp_add_linrelax_solver (there may be several solvers in a search process). The model definition
is completed by a ‘MIP style’ branching scheme that branches first on the variables with largest
reduced cost, and tests first the values nearest to the optimal solution of the relaxation.
model "Knapsack with side constraints"
uses "kalis", "mmsystem"
declarations
VALUES = {1,3,8,9,12}
R = 1..4
x: array(R) of cpvar
benefit: cpvar
end-declarations! Decision variables! The objective to minimize! Enable output printing
setparam("kalis_verbose_level", 1)! Setting name of variables for pretty printing
forall(i in R) setname(x(i),"x"+i)setname(benefit,"benefit")! Set initial domains for variables
forall(i in R) setdomain(x(i), VALUES)! Knapsack constraints
3*x(1) + 5*x(2) + 2*x(3) <= 50
2*x(1) + x(3) + 5*x(4) <= 75! Additional global constraint
all_different(union(i in R) {x(i)})! Objective function
benefit = 5*x(1) + 8*x(2) + 4*x(3) + x(4)! Initial propagation
res := cp_propagate! Display bounds on objective after constraint propagation
writeln("Constraints propagation objective ", benefit)! **** Linear relaxation ****

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

113

Hybridization of CP and MP

declarations
myrelaxall: cplinrelax
end-declarations! Build an automatic ’LP’ oriented linear relaxation
myrelaxall:= cp_get_linrelax(0)! Output the relaxation to the screen
cp_show_relax(myrelaxall)
mysolver:= get_linrelax_solver(myrelaxall, benefit, KALIS_MAXIMIZE,KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)! Define the linear relaxation
cp_add_linrelax_solver(mysolver)! Define a ’MIP’ style branching scheme using the solution of the relaxation
cp_set_branching(assign_var(KALIS_LARGEST_REDUCED_COST(mysolver),KALIS_NEAREST_RELAXED_VALUE(mysolver)))! Solve the problem
starttime:= gettime
if (cp_maximize(benefit)) thenwrite(gettime-starttime, "sec. ")cp_show_sol! Output optimal solution to screen
end-ifend-model

6.3.3

Results
The formulation of a CP model for this problem is straightforward. However, solving this type ofproblems with pure CP search methods tends to be very time consuming due to the poor qualityof the bounds on the objective variable derived through constraint propagation. Formulating a
MIP model for this problem is a perhaps somewhat more complicated task due to the need tolinearize the ’all_different’ relation. Here the automatic reformulation provided by Xpress Kalis iscertainly helpful. The LP relaxation provides valuable bounds and insight on how to direct the
search. Combining both makes the CP search go straight to the optimal solution and optimality isproven immediatly by the relaxation bounds. The configuration options allow you to tune thebehavior of the combined solution algorithm.
Try to experiment with other settings:
LP or MIP style relaxations (first parameter of cp_get_linrelax),relax only certain constraints, e.g., by specifying KALIS_LINEAR_CONSTRAINTS in
cp_get_linrelax:
cp_get_linrelax(0, {KALIS_LINEAR_CONSTRAINTS})

solving frequency (tree nodes or top node): last argument of get_linrelax_solver,

subproblem type (LP or MIP): 4th argument of get_linrelax_solver.

Note: Instead of displaying the linear relaxation on screen you may also choose to export it to a
file in LP format using procedure export_prob, specifying a linear relaxation solver and a matrix
filename (the extension ".lp" will be appended to the name) as arguments.
export_prob(mysolver, "mymatfile")

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

114

Hybridization of CP and MP

6.4

User-defined relaxations
As an alternative or in addition to the built-in relaxation definitions, linear relaxations (or parts
thereof) can be built up from scratch, similarly to the definition of linear constraints in a pure CP
model. For the representation of linear relaxations, Xpress Kalis provides the types cpauxvar andcpauxlinexp (for variables and linear expressions that do not occur in the original CP model). The
linearization of certain global constraints requires a mapping from integer-valued CP decisionvariables to sets of 0-1 indicator variables in the LP/MIP formulation, where each indicatorvariable is associated with a value in the domain of the CP variable. These indicator variables (oftype cpauxvar) are obtained with function get_indicator. Besides these special variable types,
linear relaxation constraints can also contain variables of type cpvar or cpfloatvar.

6.4.1

Implementation
The implementations below replace the configured definition of a relaxation by a relaxation built
up ’manually’ by stating the constraints one by one. Just like the previous model version, arelaxation solver is defined with get_linrelax_solver. This linear relaxation solver is then added
to the search process by a call to cp_add_linrelax_solver and the model definition is completed
by a ‘MIP style’ branching scheme that branches first on the variables with largest reduced cost,
and tests first the values nearest to the optimal solution of the relaxation.
This model extract selects one by one the constraints to be added to the relaxation:
declarations
myrelax: cplinrelax
end-declarations! Build an ’LP’ oriented linear relaxation
myrelax:= get_linrelax(all_different(union(i in R) {x(i)}), 0)
myrelax += get_linrelax(3*x(1) + 5*x(2) + 2*x(3) <= 50, 0)
myrelax += get_linrelax(2*x(1) + x(3) + 5*x(4) <= 75, 0)
myrelax += get_linrelax(benefit - (5*x(1) + 8*x(2) + 4*x(3) + x(4)) = 0, 0)
mysolver:= get_linrelax_solver(myrelax, benefit, KALIS_MAXIMIZE,KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)! Output the relaxation to the screen (after creation of solver to see all!)cp_show_relax(myrelax)! Define the linear relaxation
cp_add_linrelax_solver(mysolver)! Define a ’MIP’ style branching scheme using the solution of the relaxation
cp_set_branching(assign_var(KALIS_LARGEST_REDUCED_COST(mysolver),KALIS_NEAREST_RELAXED_VALUE(mysolver)))! Solve the problem
starttime:= gettime
if (cp_maximize(benefit)) thenwrite(gettime-starttime, "sec. ")cp_show_sol! Output optimal solution to screen
end-ifWhen adding linear constraints to the relaxation we have the choice to add them directly, or byusing the function get_linrelax as in the model extract above. When using this function we canspecify through its second argument whether to disregard the integrality condition on any
variables the linear constraint.
If we do not want to use any of the built-in relaxation functionality, we can also state therelaxations ’manually’. In the example below the linear relaxation is formulated entirely with thebinary indicators for domain values, leaving out the variables xi that are present in all the

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

115

Hybridization of CP and MP

automated relaxation versions we have seen so far.
declarations
myrelax: cplinrelax
end-declarations! Build a user-defined linear relaxation! Formulation of ’alldifferent’:
forall(val in VALUES)
myrelax += sum(i in R | contains(x(i),val)) get_indicator(x(i), val) <= 1
forall(i in R)
myrelax += sum(val in VALUES | contains(x(i),val)) get_indicator(x(i), val) = 1! Reformulation of linear constraints
myrelax +=3*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +5*sum(val in VALUES | contains(x(2),val)) val*get_indicator(x(2), val) +2*sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) <= 50
myrelax +=2*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) +2*sum(val in VALUES | contains(x(4),val)) val*get_indicator(x(4), val) <= 75
myrelax += benefit (5*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +8*sum(val in VALUES | contains(x(2),val)) val*get_indicator(x(2), val) +4*sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) +sum(val in VALUES | contains(x(4),val)) val*get_indicator(x(4), val)) = 0
mysolver:= get_linrelax_solver(myrelax, benefit, KALIS_MAXIMIZE,KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)

6.4.2

Results
When comparing the program output obtained from the two formulations above, it appears thatthe automatic formulation provides better guidance to the CP search (that is, less nodes are
required to terminate the enumeration) than the ’manual’ formulation that works exclusively
with the binary indicator variables. There often are different possibilities for formulating linear
relaxations and some experimentation is required to determine which is the best choice.
General recommendations for the formulation of linear relaxations are (a) to be careful to definea relaxation that makes sense and (b) to make sure that the relaxation is connected to theoriginal problem (through variables shared by both formulations) so to obtain the desired
benefits from information exchange between the two views of the problem.
Note: Xpress Kalis also makes accessible additional configuration options for the underlying
LP/MIP solver; the interested reader is referred to the documentation of
set_linrelax_solver_attribute in the the Xpress Kalis Reference manual.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

116Appendix

A PPENDIX A

Trouble shootingNo license found: to work with Kalis for Mosel, the Xpress licensing system, and the Xpress
Kalis module must be installed. You need to copy the license file that you will receive fromyour software vendor into the Xpress installation directory and set the environment variable
XPRESSDIR to point to this directory.



The Xpress Kalis module is not found: if the file kalis.dso is not installed in the directorydso of the Mosel distribution, then the environment variable MOSEL_DSO must be definedwith the location of this file.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

118

A PPENDIX B

Glossary of CP terms
Some terms commonly used in CP might require some explanation for readers with an Operations
Research background. The following list is an extract from [Hei99b].
Finite domain constraint problem/constraint satisfaction problem (CSP): defined by a finite set ofvariables taking values from finite domains and a (conjunctive) set of constraints on thesevariables. The objective may be either finding one solution (any or an optimal) or all solutions(consistent assignment of values to the variables so that all the constraints are satisfied
simultaneously) for the given instance. The term constraint network is frequently employed todenote CP problems in allusion to the graphical representation as a hyper graph (constraintgraph), where nodes represent variables, and constraints are (hyper) arcs linking several nodes.
There is no standard problem representation in CP.
Model: a CP model specifies all variables, their domains and their declarative meaning andconceptual constraints imposed on them (as opposed to actual constraints that are used to
implement the properties of the solution and the search process). In CP in general, a model
preserves much problem-specific knowledge about variables and the relations between them.
This allows the development and application of more efficient specialized solution strategies.
Variable: object that has a name and a domain (also referred to as decision variable).
Domain: the set of values (also: labels) a variable may take. In Xpress Kalis, it may consist of
discrete values, or intervals of integers. When solving CP problems active use of the domain
concept is made. At any stage, the domain of a variable is the set of values that cannot be proved
to be inconsistent (with the constraints on this variable) using the available consistency checking
methods. Assigning or restricting domains is often interpreted as unary constraints on thecorresponding variables.
Instantiation of a set of variables is an assignment of a value to each variable from its domain,
also called labeling of each variable with a value from its domain.
Consistent instantiation of a constraint network is an instantiation of the variables such that theconstraints between variables are satisfied, also called admissible/satisfied instantiation,
consistent assignment of values, or consistent labeling. Solution is often used as a synonym forconsistent instantiation, but may also denote the result after applying any (local/partial)
consistency algorithm.
Constraint: a relation over a set of variables limiting the combination of values that thesevariables can take; constraints may also be interpreted as mappings from the domains of thevariables onto the Boolean values true and false. A (conceptual) constraint can sometimes be
implemented in different ways enforcing various levels of consistency (see below) with different
computational overhead. So-called global constraints subsume a set of other constraints (forinstance an ‘all-different’ relation on a set of variables replaces pair wise disequality constraints).
Global constraints use specific propagation/consistency algorithms that render them more
efficient than the set of constraints they replace.
Redundant constraints: a constraint is redundant with respect to a set of constraints, if it isFair Isaac Corporation and Artelys SA Confidential and Proprietary Information

119Glossary of CP terms

satisfied when the set of constraints is satisfied. Although redundant constraints do not change
the set of solutions (consistent instantiations) of a problem, in practice it may be useful to add
redundant constraints to the model formulation because they can help CP solution procedures,
particularly by achieving more powerful constraint propagation.
System of constraints: a conjunctive set of constraints, usually built up incrementally.
Constraint solving: deciding the consistency or satisfiability of a system of constraints.
Solution methods: finite domain CP problems are usually solved by tree search methods(Branch-and-Bound for optimization, Branch-and-Prune for decision problems) that enumerate
the possible values of the variables coupled with consistency algorithms. In tree search methods
with consistency checking the local consistency algorithm is triggered by the propagation of thedomain changes of the branching variable. For optimization usually a cost constraint isintroduced that propagates to the variables. It is updated (in the case of minimization: bounded
to be smaller than the solution value) each time a new solution is found.
Consistency techniques and constraint propagation: Consistency algorithms remove inconsistentvalues from the domains of variables. Informally speaking, a consistency algorithm is ‘stronger’
than another one if it reduces the domains further, i.e., it establishes a higher level of consistency.
In finite domain CP, typically local consistency algorithms are used. Local or partial consistency
signifies that only subsets of the constraints of a system of constraints are simultaneously
satisfied. A locally consistent (according to some notion of consistency, such as arc-consistency)
constraint network can be obtained by propagating iteratively the effects of each constraint toall other constraints it is connected to through its variables until a stable state is reached. This
process is referred to as constraint propagation. Propagation properties of constraints vary, e.g.,
due to their implementation, or the types of variables used. Possible events triggering theirevaluation may be variable instantiation, modification of domain bounds, removing of value(s)from a domain, etc.
Backtrack search augmented by constraint propagation:
while not solved and not infeasible
check/establish (local) consistency
if a dead end is detected
then backtrack to the first open nodeelse
select a variableselect a value for the variable
Search algorithms/strategies: The values for variables come out of an enumeration process.
‘Intelligent’ enumeration strategies adapted to special types of constraints and variables are acentral issue in CP. The search is controlled by problem specific heuristics, strategies fromMathematical Programming or the expert’s knowledge; fixing variables to trial values is possible.
One can distinguish variable and value selection heuristics. Due to the way the backtracking
mechanism works, usually depth-first search is used.
Constraint solver: (Also: constraint engine.) Distinction between exact and incomplete solvers.
Exact solvers guarantee the satisfiability of the system of constraints at any stage of thecomputations, they usually work on rational numbers (trees of rationals and linear constraints).
Incomplete solvers are designed for more complex domains such as integers where checking andmaintaining consistency of the overall system is too expensive or not possible with presently
known algorithms. These solvers work with simplified calculations establishing some sort ofpartial (local) consistency among constraints; usually simply stating constraints does not produce
a solution, an enumeration phase (searching for solutions) is necessary.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

120

Bibliography[FM63]

H. Fisher and J. F. Muth. Probalistic Learning Combinations of Local Job-Shop Scheduling Rules. In J. F. Muth and
G. L. Thompson, editors, Industrial Scheduling, pages 225—251, Englewood Cliffs, N. J., 1963. Prentice Hall.

[Hei99a] S. Heipcke. Combined Modelling and Problem Solving in Constraint Programming and Mathematical
Programming. PhD thesis, University of Buckingham, 1999.
[Hei99b] S. Heipcke. Comparing Constraint Programming and Mathematical Programming Approaches to Discrete
Optimisation. The Change Problem. Journal of the Operational Research Society, 50(6):581—595, 1999.

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

121

IndexSymbols
+, 11
;, 8
A
abs, 18, 27
all-different, 119
all-different constraint, 30
all_different, 18, 26
and, 37
array
definition, 7
assign_var, 16, 62
assignment problem, 65
AUTO_PROPAGATE, 72
Bbacktrack search, 120
backtrackable number, 70
binary constraint, 52
binpacking, 83
bottleneck machine, 30
bottleneck problem, 65
bound
default, 13
lower, 68
upper, 68
Branch-and-Bound, 120
branching scheme, 16, 37, 48, 54, 62
branching strategy, 2, 48, 54
Ccallback, 29, 64
ceil, 38
choice point, 72
comments, 8compile model, 8
condition
loop, 12conflict analysis, 71
consistency
local, 120partial, 120
consistency algorithm, 119, 120
consistent instantiation, 3
constraint, 2, 45, 119absolute value, 18, 27
actual, 119
all-different, 18, 30, 43, 45, 119
automatical posting, 20
cardinality, 38
conceptual, 119

cumulative, 18
cycle, 18, 50, 54
declaration, 20
definition, 7, 20
disequality, 18
disjunction, 34
disjunctive, 18, 34
distance, 18, 27
distribute, 39, 40, 59
element, 18, 38
equivalence, 18, 44
explicit posting, 21, 78
generic binary, 18, 52
global, 1, 119
global cardinality, 40, 59
implication, 18, 44
implicit, 75
linear, 18
logic, 18, 37, 44
maximum, 15, 18
minimum, 18
name, 20
nonlinear, 18
occurrence, 18, 38, 40
or, 34propagation, 21
redundant, 119unary, 119constraint branching, 37
constraint engine, 120
constraint network, 119Constraint Programming, 1
constraint propagation, 2, 120
constraint satisfaction problem, 119constraint solver, 120
constraint solving, 120
contains, 69
continuous variable, 17
cost function, 3CP, see Constraint Programming
cp_find_next_sol, 7, 21, 25
cp_minimize, 21
cp_post, 21, 78
cp_propagate, 21, 77
cp_reset_search, 29, 64
cp_schedule, 76
cp_shave, 77
cp_show_prob, 11
cp_show_stats, 11, 69
cpbranching, 29
cpctr, 20
cpfloatvar, 7, 17

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

122

Indexcp_infeas_analysis, 72
cpresource, 75
cp_restore_state, 72
cpreversible, 70
cpreversiblearray, 70
cp_save_state, 72
cp_set_schedule_search, 103
cptask, 75
cpvar, 7
cpvarlist, 68
create, 13
critical path, 77
CSP, see constraint satisfaction problem
cumulative, 18
cumulative scheduling, 83
cycle, 18D
data
input from file, 11
sparse, 13data file, 11, 13
data format
sparse, 13
debugging, 11decision variable, 2, 6, 119
declaration, 7
dynamic array, 13
list, 68
lower bound, 68
name, 11
test domain value, 69
upper bound, 68
declarations, 7, 25
default bound, 13
DEFAULT_LB, 13
DEFAULT_UB, 13
disequality constraint, 7
disjunction
implicit, 79
disjunctive, 18, 34
disjunctive scheduling, 79
distance, 18, 27
distribute, 18, 39, 40, 59
div, 53
domain, 2, 119
definition, 7
domain value
next, 68
previous, 68
test, 69
domain variable, 2dynamic array, 13
dynamic set, 13Eelement, 18, 38, 45
element constraint
2-dimensional, 45
empty line, 8

end, 33
end-model, 7
enumeration, 3
constraints, 62
decision variables, 62
task-based, 102variable-based, 102
enumeration strategy, 2equiv, 18, 44
equivalence constraint, 18, 44
execute, 9
execute model, 8exists, 14
exit, 8F
feasible solution, 3
finite domain constraint problem, 119
finite domain Constraint programming, 2
forall, 7
formating, 8
forward, 25function, 53, 68
G
generic binary constraint, 52
generic_binary_constraint, 18, 53
getlb, 68
getnext, 68
getparam, 25, 64
getprev, 68
getsol, 8getub, 68
getvar, 68
global constraint, 1
group_serialize, 108Iif, 25if-then, 25
implication constraint, 18, 44
implicit constraint, 75
implies, 18, 44
incrementality, 2
indentation, 8
infeasibility, 71
instantiation, 119consistent, 119K
kalis, 1
Kalis for Mosel, 1
KALIS_AUTO_PROPAGATE, 21
KALIS_COMPUTATION_TIME, 25
KALIS_DISCRETE_RESOURCE, 83
KALIS_DISJUNCTIONS, 108
KALIS_FORWARD_CHECKING, 26
KALIS_GEN_ARC_CONSISTENCY, 26
KALIS_INPUT_ORDER, 62
KALIS_LARGEST_ECT, 108
KALIS_LARGEST_EST, 107

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

123IndexKALIS_LARGEST_LCT, 108
KALIS_LARGEST_LST, 108
KALIS_LARGEST_MAX, 62, 67
KALIS_LARGEST_MIN, 62
KALIS_MAX_BACKTRACKS, 64
KALIS_MAX_COMPUTATION_TIME, 64
KALIS_MAX_DEGREE, 29, 62
KALIS_MAX_DEPTH, 64
KALIS_MAX_NODES, 64
KALIS_MAX_SOLUTIONS, 64
KALIS_MAX_TO_MIN, 54, 63, 67
KALIS_MAXREGRET_LB, 62
KALIS_MAXREGRET_UB, 62
KALIS_MIDDLE_VALUE, 63
KALIS_MIN_TO_MAX, 16, 63
KALIS_NEAREST_VALUE, 63
KALIS_NODES, 25
KALIS_OPT_ABS_TOLERANCE, 64
KALIS_OPT_REL_TOLERANCE, 64
KALIS_OPTIMIZE_WITH_RESTART, 64
KALIS_RANDOM_VALUE, 63
KALIS_RANDOM_VARIABLE, 62
KALIS_SMALLEST_DOMAIN, 16, 63
KALIS_SMALLEST_ECT, 108
KALIS_SMALLEST_EST, 107
KALIS_SMALLEST_LCT, 108
KALIS_SMALLEST_LST, 108
KALIS_SMALLEST_MAX, 38, 63
KALIS_SMALLEST_MIN, 54, 63, 67
KALIS_TASK_INTERVALS, 108
KALIS_TIMETABLING, 108
KALIS_UNARY_RESOURCE, 80
KALIS_WIDEST_DOMAIN, 63
KALIS_INITIAL_SOLUTION, 103
KALIS_MAX_COMPUTATION_TIME, 104
KALIS_OPTIMAL_SOLUTION, 103
KALIS_VERBOSE_LEVEL, 104Lline break, 8
linear relaxation, 109
list of variables, 68
entry, 68load model, 8loop, 7lower bound, 68Mmakespan, 30
MAX_COMPUTATION_TIME, 29
maximin problem, 65
maximization, 15
maximum, 18, 80
maximum constraint, 15
maximum regret, 68
minimization, 15
minimum, 18
mod, 53
model, 119
compile, 8

data driven, 13
execute, 8
execution, 8load, 8run, 8structure, 49
model, 7
model parameter, 54
modulelisting, 25
parameters, 25
Mosel, 1
Mosel debugger, 11
Mosel language, 1
Mosel module, 1N
nameconstraint, 20
variable, 11
next domain value, 68Oobjective function, 3
occurrence, 18, 38, 40
optimal solution, 3
optimization, 15, 120
or, 34, 37
output, 8, 10Pparameters, 54
posting constraints, 20, 21, 78
preemptive scheduling, 100
previous domain value, 68
probe_assign_var, 54, 62
probe_settle_disjunction, 62
problemsolving, 7
procedure, 25, 31, 35, 41
producer-consumer constraint, 90
propagating constraints, 21
propagation, 119, 120
propagation algorithm, 26
pruning, 26
Rrange set, 7relaxation solver, 112
resource
discrete, 83
non-renewable, 86
renewable, 86
unary, 79
resusage, 96
returned, 68
reversible number, 70
run model, 8
Sscheduling

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

124

Index

cumulative, 83
disjunctive, 79
searchexhaustive, 62
incomplete, 62
resetting, 29, 64, 67
restart, 29, 64, 67
time limit, 29
search methods, 120
search strategy, 2, 29, 120
user defined, 68
set
definition, 7
range, 7
set_resource_attributes, 80
set_task_attributes, 80
setcapacity, 99, 100
setdomain, 7, 13
setidletimes, 100
setnamett, 11
setparam, 21, 64
setpredecessors, 78
setsetuptimes, 93
setsuccessors, 78
settarget, 63
settle_disjunction, 37, 62
setup time, 92
solution, 119
feasible, 3
optimal, 3
printing, 8solution callback, 29, 64
solver statistics, 69
solving, 7space, 8
sparse array, 14
split_domain, 48, 62
stopping criteria, 63
sub-cycle elimination, 44
subroutine, 25, 31, 35, 41, 49, 53
sum
condition, 12
symmetry breaking, 29, 86
system of constraints, 120

user constraint, 52
user graph, 56
user search, 68
uses, 7
V
value selection strategy, 16, 63
user defined, 68
variable, 119
default bounds, 13
variable domain, 2variable selection strategy, 16, 62
user defined, 68
variable-based
enumeration, 102
Wwhile, 25
Workbench, 2
starting, 9write, 8writeln, 8X
Xpress Kalis, 1
Xpress Mosel, see Mosel
Xpress Optimizer, 109
Xpress Workbench, see WorkbenchTtarget value, 63task
predecessor, 78
resource profile, 97
successor, 78
task selection, 107
task-based
enumeration, 102
task_serialize, 62, 105
time limit, 29
Uupper bound, 68

Fair Isaac Corporation and Artelys SA Confidential and Proprietary Information

125