Large-Scale Multiobjective Static Test Generation for Web-Based Testing with Integer Programming

Web-based testing has become a ubiquitous self-assessment method for online learning. One useful feature that is missing from today's web-based testing systems is the reliable capability to fulfill different assessment requirements of students based on a large-scale question data set. A promising approach for supporting large-scale web-based testing is static test generation (STG), which generates a test paper automatically according to user specification based on multiple assessment criteria. And the generated test paper can then be attempted over the web by users for assessment purpose. Generating high-quality test papers under multiobjective constraints is a challenging task. It is a 0-1 integer linear programming (ILP) that is not only NP-hard but also need to be solved efficiently. Current popular optimization software and heuristic-based intelligent techniques are ineffective for STG, as they generally do not have guarantee for high-quality solutions of solving the large-scale 0-1 ILP of STG. To that end, we propose an efficient ILP approach for STG, called branch-and-cut for static test generation (BAC-STG). Our experimental study on various data sets and a user evaluation on generated test paper quality have shown that the BAC-STG approach is more effective and efficient than the current STG techniques.