Exact and approximate methods for a one-dimensional minimax bin-packing problem

Michael J. Brusco, Hans Friedrich Koehn, Douglas Steinley

Research output: Contribution to journalArticle

Abstract

One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.

Original languageEnglish (US)
Pages (from-to)611-626
Number of pages16
JournalAnnals of Operations Research
Volume206
Issue number1
DOIs
StatePublished - Jul 1 2013

Fingerprint

Bin packing
Minimax
Integer linear programming
Assignment
Discrimination
Psychometrics
Simulated annealing
Heuristics
Psychology
Software
Simulated annealing algorithm
Statistics
Mathematical programming

Keywords

  • Combinatorial optimization
  • Integer programming
  • One-dimensional bin-packing
  • Simulated annealing
  • Test splitting

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this

Exact and approximate methods for a one-dimensional minimax bin-packing problem. / Brusco, Michael J.; Koehn, Hans Friedrich; Steinley, Douglas.

In: Annals of Operations Research, Vol. 206, No. 1, 01.07.2013, p. 611-626.

Research output: Contribution to journalArticle

@article{769a0b4d5ad9400ba44941934fc9e3eb,
title = "Exact and approximate methods for a one-dimensional minimax bin-packing problem",
abstract = "One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.",
keywords = "Combinatorial optimization, Integer programming, One-dimensional bin-packing, Simulated annealing, Test splitting",
author = "Brusco, {Michael J.} and Koehn, {Hans Friedrich} and Douglas Steinley",
year = "2013",
month = "7",
day = "1",
doi = "10.1007/s10479-012-1175-5",
language = "English (US)",
volume = "206",
pages = "611--626",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Exact and approximate methods for a one-dimensional minimax bin-packing problem

AU - Brusco, Michael J.

AU - Koehn, Hans Friedrich

AU - Steinley, Douglas

PY - 2013/7/1

Y1 - 2013/7/1

N2 - One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.

AB - One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.

KW - Combinatorial optimization

KW - Integer programming

KW - One-dimensional bin-packing

KW - Simulated annealing

KW - Test splitting

UR - http://www.scopus.com/inward/record.url?scp=84879410139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879410139&partnerID=8YFLogxK

U2 - 10.1007/s10479-012-1175-5

DO - 10.1007/s10479-012-1175-5

M3 - Article

AN - SCOPUS:84879410139

VL - 206

SP - 611

EP - 626

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -