In my daily job, I’m involved in a project around adaptive testing. Basically, items are presented in an order that is dependent upon the estimated level of ability of the respondent. Parameters estimation can be done on the fly (time consuming) or can rely on more subtle computation based on overall test information and additional constraints (distributed content or thematics, etc.). Moreover, items can be collapsed into so-called items bundles. Taking into account such constraints during the building up of items sequence calls for linear programming resources. However, it has been shown that linear programming models are not always applicable as some constraints cannot be satisfied simultaneously with some other constraints. Most of the initial work on tailored testing in educational measurement has been pioneered by ETS researchers(1,2).
Swanson and Stocking propose to use a weighted deviation model relying on LP with several constraints for the selection of items. Such constraints generally involve maximization of item information, restriction to selected topics or distributed content, minimization of item exposure, etc. In this view, these constraints shall be viewed as desirable properties rather than external conditions. Of course, bayesian techniques(3) have been proposed as well. An on-line tutorial is available on Lawrence M. Rudner’s website. Note also that applications embedding a CAT approach don’t restrict to education but also covered wide biomedical assessments(4).
While I was looking for LP facilities within R, I found three related packages (see the CRAN website for details): glpk, Rglpk, and linprog.
The former rely on the GNU Linear Programming Kit, while the linprog package implements the simplex algorithm for solving linear optimisation problems. I know there is also LP tools with the Matlab optimization toolbox but I don’t use Matlab since I left my previous lab. However, I found a free implementation when googling for LP code, linprog.m. It is Octave-compatible, and I happen to test it using a very simple problem.
Before starting with R, I take a look at GLPK on GNU website. Starting using these tools was a little confusing as it is not a standalone C program taking as argument matrices and vectors describing the linear system, as usual, but the program glpsol relies on an external description file. Hereafter is a little demonstration of its use. Before that, we have to talk about the underlying modeling language, which is derived from the original AMPL language. A free chapter of the official AMPL book is available to download.
At a glance, GLPK can handle several kind of problems using the simplex method, the primal-dual interior point method, and the branch-and-bound method. There are also some additional facilities (translation from GNU MathProg, API, stand-alone LP/MIP solver). GNU MathProg is a subset of the AMPL language. It can be installed on Mac OS X using Fink, or even compiled by hand. GLPK is a library of functions written in C and is entirely devoted to linear and integer programming. In addition, it includes a standard LP/IP solver, glpsol, and a modeling language, GMPL. There is, however, no graphical interface, and all is done using text file and the shell command line. A simple session would look like:
$ glpsol --model model1.txt --output results1.txt
Here model1.txt is an input file containing the required instructions in the GNU MathProg language. If the input file is ok, glpsol will process it. The interested reader is referred to this two-parts tutorial on IBM website.
Overall, several books have been published during the past 20 years(5), but there is an extensive overview of adaptive testing aims and numerical realizations in Computerized Adaptive Testing, W.J. van der Linden and C.A.W. Glas (Kluwer, 2000). This book is divided in 15 chapters which cover 5 overlapping parts:
Also, here is a short talk (PDF) I gave about CAT systems (in French).