Hybrid Maximum Clique Algorithm Using Parallel Integer Programming for Uniform Test Assembly

Fuchimoto, Kazuma and Ishii, Takatoshi and Ueno, Maomi (2022) Hybrid Maximum Clique Algorithm Using Parallel Integer Programming for Uniform Test Assembly. IEEE Transactions on Learning Technologies, 15 (2). pp. 252-264. ISSN 19391382

Abstract

Educational assessments often require uniform test forms, for which each test form has equivalent measurement accuracy but with a different set of items. For uniform test assembly, an important issue is the increase of the number of assembled uniform tests. Although many automatic uniform test assembly methods exist, the maximum clique algorithm (MCA)-based method is known to assemble the greatest number of uniform tests with the highest measurement accuracy based on the item response theory. In that method, the graph is constructed by sequentially adding a randomly formed test as a vertex without considering the graph structure. However, an important difficulty is its high space complexity, which interrupts search cliques with more than a hundred thousand vertices. To overcome this difficulty, this article proposes a new uniform test assembly algorithm: hybrid maximum clique algorithm using parallel integer programming. The first step searches a maximum clique that is as large as possible up to computer memory limitations using a state-of-the-art MCA with low time complexity but with high space complexity. The second step repeatedly searches a vertex connected with all vertices of the current maximum clique from the remaining vertices using integer programming with low space complexity but with high time complexity. The proposed method constructs a larger number of tests than the traditional methods do. Finally, we use simulation and actual data experiments to demonstrate the effectiveness of the proposed method. Results show that our method assembles a 1.5-2.7 times greater number of uniform tests than traditional methods can.

Item Type:	Article
Identification Number:	10.1109/TLT.2022.3163360
Uncontrolled Keywords:	E-testing,integer programming (IP),item response theory (IRT),maximum clique problem (MCP),uniform test assembly
Depositing User:	Unnamed user with username chikyta
Date Deposited:	17 May 2024 01:41
Last Modified:	17 May 2024 01:41
URI:	http://repository.ub.ac.id/id/eprint/219422

Text Hybrid Maximum Clique Algorithm Using Parallel Integer Programming for Uniform Test Assembly.pdf Download (1MB)

Actions (login required)

View Item