Integer programming models for the multidimensional assignment problem with star costs

Jose L. Walteros, Chrysafis Vogiatzis, Eduardo L. Pasiliao, Panos M. Pardalos

Research output: Contribution to journalArticlepeer-review


We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented.

Original languageEnglish (US)
Pages (from-to)553-568
Number of pages16
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Jun 16 2014
Externally publishedYes


  • Branch and price
  • Combinatorial optimization
  • Graph partitioning
  • Multi-sensor multi-target tracking problem
  • Multidimensional assignment problem
  • Star covering

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Integer programming models for the multidimensional assignment problem with star costs'. Together they form a unique fingerprint.

Cite this