Initializing help system before first use

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 the model file with every change of the data set. Instead, we are now going to see how to read data from a text file.

This is a description of the problem we want to solve (example taken from Section 14.4 of the book `Applications of optimization with Xpress-MP').

A technical university needs to schedule the exams at the end of the term for a course with several 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 take place at the same time because they have to be taken by the same students is shown in Table Incompatibilities between different exams.

Table 2.1: Incompatibilities between different exams
DA NA C++ SE PM J GMA LP MP S DSE
DA – X – – X – X – – X X
NA X – – – X – X – – X X
C++ – – – X X X X – X X X
SE – – X – X X X – – X X
PM X X X X – X X X X X X
J – – X X X – X – X X X
GMA X X X X X X – X X X X
LP – – – – X – X – – X X
MP – – X – X X X – – X X
S X X X X X X X X X – X
DSE 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 constraints in a loop instead of writing them out one by one.

∀ e ∈ EXAM: plane ∈ {1,...,8}
∀ d,e ∈ EXAM, INCOMPde=1: pland ≠ plane

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          ! Time slot for exam
 end-declarations

 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) then
  writeln("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-do

end-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 are marked 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]

Results

The model prints out the following results. Only the first seven time slots are used for scheduling exams.

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:

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 the model. 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 no need to write out explicitly the contents of the set EXAM—Mosel will automatically populate this set with the index values read in for the array INCOMP. In addition, the data file now contains a value 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 by stating their types, which turns them into dynamic sets (as opposed to their previous constant definition by stating their values). As a consequence, the array of decision variables plan is declared 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 created explicitly (using the Mosel procedure create) once the indices are known. Before creating the variables, 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, 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 sparse arrays (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          ! Time slot for exam
 end-declarations

 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) then
  writeln("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-do

end-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 important to 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

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

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.