CSC5240
Combinatorial Search and
Optimization with Constraints
Tutorial Notes 1
1
Teacher and Tutor

Prof. Jimmy Lee



Email : jlee <at> cse.cuhk.edu.hk
Office : SHB 1009
Kobi Lei


Email : kmlei <at> cse.cuhk.edu.hk
Office : SHB 1005
2
Assessment Scheme

Assignments
30%

Paper Presentation
30%

Project + Report
40%

Final Examination
3
CSC5240 Tutorial 1

Assignment 1

ILOG Solver 6.7

CSE UNIX Connection

Course Newsgroup
4
Sudoku
5
9
8
1
4
8
1
3
6
6
1
9
7
5

5
9
8
2
7
1
6
4
2
7
1
4
3
6
8
9
5
7
6
4
8
1
9
5
2
3
7
8
2
4
6
7
5
1
3
9
8
2
6
1
8
2
9
7
4
3
5
6
3
9
5
2
6
8
7
4
1
4
6
3
3
7
3
5
2
6
7
5
4
3
8
2
6
1
9
1
4
9
2
3
6
5
1
4
7
8
9
5
8
1
6
7
4
9
5
2
3
3
Fill a partially completed Sudoku with digits 1-9
so that each row, each column and each 3 x 3
box contains different digits
5
Hardest Sudoku
Try to solve it using the
program of your assignment 1
Q2 and see how much time is
needed to solve the HARDEST
Sudoku.
6
ABC Path

Fill a 4x4 grid with letters A-P such that each
letter touches the previous one either
horizontally, vertically or diagonally and each
letter should appear exactly once.
7
ABC Path

A letter touches previous letter either
horizontally, vertically or diagonally
A locates in one
of these 8 cells.
A locates in one
of these 3 cells.
8
ABC Path

A letter should appear exactly once in the grid
✓
9
ABC Path
desired position

total payoff = 5
Objective function:
10
ABC Path

Your program should print the resulting
grid for both models as follows:
Align the result in a 4 x 4
grid, with each number
representing the
corresponding letter.
11
Submission Instructions

Written Part:
 Question 1, 2(a) and 3(b). Please also write down your
observation of the comparison in 3(b).
 Submit your softcopy (PDF file) to me

Programming Part:
 Question 2(a)
 Filename: sudoku.cpp
 Usage: sudoku
 Question 3
 Filename: abc_path.cpp
 Usage: abc_path <model>
 Using model in 3(a): abc_path 1
 Using your model in 3(b): abc_path 2
12
Submission Instructions

Programming Part (cont’d):

Add proper comments to source files

Show sample outputs enclosed as comments at the end
of the source files

Attach 1 pdf file and 2 cpp files and send to
[email protected] with the subject:


CSC5240 Asg1 [studentID]
e.g. CSC5240 Asg1 01234567
13
Constraint Programming Systems

Embedding constraints into high-level
programming languages

Declarative Programming

Logic Programming


Functional Programming:


CHIP, ECLiPSe, GNU-Prolog, SICStus Prolog
Alice (Standard ML), Facile (OCaml), Pecos (Lisp)
Object-Oriented Programming

ILOG Solver (C++), ILOG JSolver (Java), Koalog (Java)
14
ILOG Solver 6.7

C++ Library for solving CSPs

Supports various constraint domains


Integer, Boolean, Finite set of integer, Real
Based on ILOG Concert Technology
15
ILOG Concert Technology 2.9

Allows to model problems independently of the
algorithms used

Supports algorithms for both


Constraint programming (ILOG Solver)
Mathematical programming (ILOG CPLEX)


only linear, quadratic, piecewise-linear, and logical
expressions can be used in models
Combination of the two (ILOG Hybrid)
16
Setting up

Machine


Please use the linux workstations offered by the
department
Environment variable: ILOG_LICENSE_FILE
setenv ILOG_LICENSE_FILE /research/microlab/ilog/ilm/access_academic.ilm

Makefile


Replace “filename” with the filename of the target file
makefile32: for 32-bit debian (linux1 – 4)


makefile64: for 64-bit debian (linux5 – 17)


http://www.cse.cuhk.edu.hk/csci5240/makefile32
http://www.cse.cuhk.edu.hk/csci5240/makefile64
Header file for integer domains
<ilsolver/ilosolverint.h>
17
IloEnv and IloModel

First step in using ILOG Concert Technology is to
create an environment and a model

Class IloEnv handles output, memory management
for modelling objects, etc.

Class IloModel is a container for modelling objects

Examples of modelling objects are variables,
constraints, etc.
18
IloEnv and IloModel
int main() {
IloEnv env;
try {
IloModel model( env );
// Build CSP model and call solver
} catch ( IloException& ex ) {
cout << "Error: " << ex << endl;
}
env.end();
return 0;
}
19
IloIntVar

(Constrained) integer variables with finite set of
integers as domain

Constructor:
public IloIntVar( IloEnv env,
IloInt vmin,
IloInt vmax,
const char* name )
20
IloIntVar
Example:

[1..9] for S, M, [0..9] for E, N, D, O, R, Y
IloIntVar
IloIntVar
IloIntVar
IloIntVar
IloIntVar
IloIntVar
IloIntVar
IloIntVar
S(
M(
E(
N(
D(
O(
R(
Y(
env,
env,
env,
env,
env,
env,
env,
env,
1,
1,
0,
0,
0,
0,
0,
0,
9,
9,
9,
9,
9,
9,
9,
9,
”S”
”M”
”E”
”N”
”D”
”O”
”R”
”Y”
);
);
);
);
);
);
);
);
21
IloExpr

Combine integer values and integer
variables to form integer expressions





Addition: operator +
Subtraction: operator Multiplication: operator *
Integer Division: IloDiv
etc.
22
IloExpr

Example: SEND + MORE = MONEY
IloExpr SEND( env ), MORE( env ), MONEY( env );
SEND = ( 1000*S + 100*E + 10*N + D );
MORE = ( 1000*M + 100*O + 10*R + E );
MONEY = ( 10000*M + 1000*O + 100*N + 10*E + Y );
23
IloConstraint

Combine integer expressions to form
integer constraints






Equality: operator ==
Not equal to: operator !=
Less than: operator <
Less than or equal to: operator <=
Greater than: operator >
Greater than or equal to: operator >=
24
IloConstraint

Example: SEND + MORE = MONEY
IloConstraint puzzle;
puzzle = ( SEND + MORE == MONEY );
25
Adding Constraints to Model

Constraint must be explicitly added to the model

Example: SEND + MORE = MONEY
model.add(puzzle);
SEND.end(); MORE.end(); MONEY.end();

Constraint can also be added directly:
model.add(
1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E
== 10000*M + 1000*O + 100*N + 10*E + Y );
26
IloIntVarArray

Arrays of IloIntVar

Example: { S, E, N, D, M, O, R, Y }
IloInt numVars = 8;
IloIntVarArray vars(
vars[0] = S; vars[1]
vars[2] = N; vars[3]
vars[4] = M; vars[5]
vars[6] = R; vars[7]
env, numVars );
= E;
= D;
= O;
= Y;
27
Disequality Constraints

Example:
x  y for x , y  { S , E , N , D , M , O , R , Y }, x  y
int i,j;
for ( i=0; i<numVars-1; i++ ) {
for ( j=i+1; j<numVars; j++ ) {
model.add( vars[i] != vars[j] );
}
}
28
IloAllDiff

A single constraint for pair-wise disequalities

Example: all_different(S, E, N, D, M, O, R, Y)
model.add( IloAllDiff( env, vars ) );
29
IloSolver

Use ILOG Solver to solve the given model

Example:
IloSolver solver( model );
if ( solver.solve() ) {
solver.out() << “Solution:”;
solver.out() << “ S=”
<< (IloInt) solver.getValue( S );
// ...
solver.out() << “ Y=”
<< (IloInt) solver.getValue( Y );
solver.out() << endl;
}
30
Optimization Problems

Objective function
IloObjective myObj;

Maximization:
myObj = IloMaximize( env, M+O+N+E+Y );

Minimization:
myObj = IloMinimize( env, S+E+N+D );

Remember to add the objective function to the
model
model.add(myObj);
31
Exercise

Play around with the sample program for
SEND + MORE = MONEY


http://www.cse.cuhk.edu.hk/csci5240/sendmory.cpp
Write ILOG programs to solve the
following problems discussed in lectures


The n-queens problem
The Zebra Puzzle
32
Reference

IBM ILOG CP 1.5



Solver 6.7 user’s manual
Solver 6.7 reference manual
http://lia.deis.unibo.it/Courses/AI/applications
AI2009-2010/materiale/cp15doc/
33
CSE UNIX Connection

When you are outside the University ...

Login to the system using your favorite ssh client to
gw.cse.cuhk.edu.hk

When you are outside CSE network, but inside CUHK ...





ClassNet (classrooms)
ResNet (Hostel)
ERGWAVE (ERG building)
CUHK wireless network
Login to the system using your favorite ssh client to
cugw.cse.cuhk.edu.hk
34
CSE UNIX Connection
Find “putty” at
http://www.chiark.greenend.org.
uk/~sgtatham/putty/
35
CSE UNIX Connection

You are now in the CSE network

When you see <myHome>, you need to ssh again to a
linuxN machine (N is from 1 to 19)[1]

Type “ssh linuxN” and password

You are now connected to UNIX!

[1] http://wiki.cse.cuhk.edu.hk/tech/system/linux
36
Course Newsgroup

Please check course newsgroup frequently!

news://news.erg.cuhk.edu.hk/cuhk.cse.csci5240

When you are outside the university, remember
you need to connect VPN before checking course
newsgroup

http://www.cuhk.edu.hk/itsc/chinese/network/vpn/
vpn.html
37
Assignment 1 deadline
15 October 2012 11:59pm
38
END
39
Descargar

Slide 1