Persistency in quadratic 0-1 optimization

Persistency in quadratic 0-1 optimization

0.00 Avg rating0 Votes
Article ID: iaor1993723
Country: Netherlands
Volume: 54
Issue: 1
Start Page Number: 115
End Page Number: 119
Publication Date: Feb 1992
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: programming: quadratic
Abstract:

This paper is concerned with persistency properties which allow the evaluation of some variables at all maximizing points of a quadratic pseudo-Boolean function. Hammer, Hansen and Simeone have proposed to determine these variables using a procedure described by Balinski for computing a strongly complementary pair of optimal primal and dual solution for arbitrary linear programs. The authors propose a linear time algorithm for determining these variables from a ‘best roof’ of f, i.e. from a lowest upper linear bound of f.

Reviews

Required fields are marked *. Your email address will not be published.