Network optimisation is a core problem domain in operations research, as well as in computer science, applied mathematics and many fields of engineering and management.

Many important combinatorial and numerical problems can be cast as a requirement to find a (or an optimal) solution satisfying a set of constraints

Constraint programming languages treat constraints as fundamental building blocks and are thus well suited to solving such problems

Students will learn how to use basic network models in a variety of applications.

Students will gain an appreciation of the methods and applications of constraint programming techniques

Students should cover the network model types

• minimum cost flows
• shortest paths
• maximum flows
• the assignment problem
• matchings
• minimum spanning trees
• convex cost flows
• generalised flows
• multicommodity flows
• travelling salesman problem
• network design

Students should learn enough about the ‘network simplex’ algorithm to appreciate its advantages

Students will have a practical level of knowledge of one particular constraint programming language

Students will be able to apply constraint programming techniques to simpler constraint problems

Students will have sufficient theoretical background to further explore the techniques necessary for more complex constraint problems

For the network component, you will need to have completed an introductory course in operations research; mainly what we need is some familiarity with linear programming

For the constraint programming component, you will need a reasonable level of mathematical maturity and an ability to think abstractly

nil

Munro J, ‘Network Analysis’ (printed notes for the unit); applications are largely chosen from the areas of transport and communication

Marriott K & Stuckey PJ, ‘Programming with Constraints’, MIT Press, 1998

The course consists of one three hour session per week, normally organised as approximately 2 hours lecture and 1 hour tutorial/laboratory session.

Approximately four assignments of approximately equal weighting

Constraint programming assignments will normally be submitted electronically by the use of the submit program.

Each piece of assessable material to be submitted electronically will contain complete instructions as to how the submission is to be made.

Note that where given, file names must be exactly as specified, or the submit program will not accept them.

Network theory assignments will normally be submitted as hard copy, and handed in through the school helpdesk before the nominated time.

Written assignments can be submitted only through the helpdesk, and will not be accepted by lecturers.

Departmental policy is that students may not place or remove anything from a staff member's mail box.

Assignments will be handed out in class at the times shown on the schedule and will also be published on the web pages.

The assignments will be due at the times shown on the schedule.

We aim to return the marked assignments to you in class within two weeks of the due date.

Please note that the due time is 5:00pm on the due date.

All exercises and assignments must be submitted before the due time.

Late submission is acceptable only if accompanied by a medical certificate.

A new due time may be arranged in that case.

You should expect to spend approximately one hour, outside of class time, for each percentage point of assessment.

Some parts of the assignments may take the form of reports. These reports must be in a legible format and must be written in comprehensible Australian English. It is expected that you will make use of document processing tools available to you, such as spelling checkers.

All material not the work of the student submitting some assessable work must be clearly indicated and referenced, with one citation for each quotation, and the quotations clearly delimited either by block indentations for a paragraph, or by quotation marks, for a sentence or two quoted inside a paragraph.

Where the material is not directly quoted, the text must clearly attribute the ideas to the author.

In the case of computer programs and similar items, those parts which are the work of others must be clearly indicated, and their source given.

All submitted material must contain a statement to the effect that except where otherwise indicated, the work is solely that of the student submitting the work.

The wording of the declaration is as follows:

For written submissions, this statement will appear on the cover sheet, and will be signed by the student. For Electronic submissions, the declaration appearing above must appear in the submitted work itself.

The penalties for plagiarism are very severe. If a student is accused of plagiarism to the university, there is a formal process involved, and if the student is found guilty, the student may fail the subject, may be barred from enrolling in the subject again for a period, or may be excluded from the university.

As a professional (current or in training), you are expected to make appropriate provision to guard against equipment and administrative failures.

You are responsible for ensuring that your work is ready for submission in time; failure of school equipment such as computers or networks will not be taken into account

You are responsible for backing up your materials. You should keep a current backup while you are developing your assignments, to protect against loss of work.

You should keep a copy of all materials submitted, to guard against accidental loss. It is particularly important that you retain the receipt given to you on submission of any assignments through the helpdesk.

Lecture and Lab period: 4pm - 7pm, Wednesdays

Bob McKay will be available for consultation in my office for six hours per week - the times are posted on his door

John Munro’s primary consultation method is via e-mail. It may be possible to arrange specific meeting times on Wednesdays

All assignments will be deposited in the course home page, which may be accessed via the departmental home page. Lecture notes for constraint programming, and useful web addresses, will also be held there.

Please check the pages regularly to keep up to date with the latest information.