A note on solving large-scale zero-one programming problems

Jos J. Adema

Research output: Book/ReportReportOther research output

21 Downloads (Pure)

Abstract

A heuristic for solving large-scale zero-one programming problems is provided. The heuristic is based on the modifications made by H. Crowder et al. (1983) to the standard branch-and-bound strategy. First, the initialization is modified. The modification is only useful if the objective function values for the continuous and the zero-one programming problems are close to each other. Given the initialization, the branch-and-bound method is stopped when a feasible solution to the problem is found. The heuristic also uses the reduced costs to fix non-basic variables to 1 or 0. An example taken from achievement test construction illustrates the efficiency of the proposed heuristic. Several test construction problems were implemented and solved by the proposed heuristic for item banks with 400 items. Modifications were introduced in the LANDO computer program. A table illustrates that the central processing unit times for solving the zero-one programming problem were close to the times needed to solve the continuous problem.
Original languageUndefined
Place of PublicationEnschede, the Netherlands
PublisherUniversity of Twente, Faculty Educational Science and Technology
Publication statusPublished - 1988

Publication series

NameOMD research report
PublisherUniversity of Twente, Faculty of Educational Science and Technology
No.88-4

Keywords

  • Programing
  • Problem Solving
  • Achievement Tests
  • Item Banks
  • Test Construction
  • Computer Assisted Testing
  • Test Reliability
  • Testing Problems
  • Heuristics
  • IR-104170

Cite this