Zero-one programming using non-binary tree-search

N. Christofides

The Computer Journal · 1971 · 16 citations · 0 references

DOIFull text

Open access

Concepts

Abstract

The paper gives a method for minimising a linear function of zero-one variables subject to constraints. The method is based on a non-binary tree search, whose primary objective is to achieve feasibility. The search is limited by calculating bounds at each stage using concepts from the theory of graphs. The algorithm promises to be computationally efficient and a 12-variable problem is solved as an example to illustrate its effectiveness.