Export to Refworks Export to EndNote Email
Report an Issue

A neural computation approach to the set covering problem [electronic resource].

Published:
Washington, D.C. : United States. Dept. of Energy, 1995.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description:
8 pages : digital, PDF file
Additional Creators:
Los Alamos National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It

Finding items...

Restrictions on Access:
Free-to-read Unrestricted online access
Summary:
This paper presents a neural network algorithm which is capable of finding approximate solutions for unicost set covering problems. The network has two types of units (neurons), with different dynamics and activation functions. One type represents the objects to be covered (the rows in the matrix representation of the problem) and another represents the ``covering`` sets (the 0,1 variables). They are connected as a bipartite graph which represents the incidence relations between objects and sets (i.e the 0,1 adjacency matrix). When the parameters of the units are correctly tuned, the stable states of the system correspond to the minimal covers. I show that in its basic mode of operation, descent dynamics, when the network is set in an arbitrary initial state it converges in less than 2n steps (where n is the number of variables), to a stable state which represents a valid solution. In this mode, the network implements a greedy heuristic in which the choice function is based on the unit inputs (which are determined by the activation functions and the network state). On top of the basic network dynamics, the algorithm applies an adaptive restart procedure which helps to search more effectively for ``good`` initial states and results in better performance.
Report Numbers:
E 1.99:la-ur--95-1823
E 1.99: conf-9511123--1
conf-9511123--1
la-ur--95-1823
Subject(s):
Other Subject(s):
Note:
Published through SciTech Connect.
07/01/1995.
"la-ur--95-1823"
" conf-9511123--1"
"DE95015316"
Neural information processing systems, Denver, CO (United States), Nov 1995.
Grossman, T.
Funding Information:
W-7405-ENG-36
View MARC record | catkey: 14350113