PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 10401928

Solving linear integer programming problems by a novel neural model.

S Cavalieri
View original source ↗Export metadata ↓

Abstract

The paper deals with integer linear programming problems. As is well known, these are extremely complex problems, even when the number of integer variables is quite low. Literature provides examples of various methods to solve such problems, some of which are of a heuristic nature. This paper proposes an alternative strategy based on the Hopfield neural network. The advantage of the strategy essentially lies in the fact that hardware implementation of the neural model allows for the time required to obtain a solution so as not depend on the size of the problem to be solved. The paper presents a particular class of integer linear programming problems, including well-known problems such as the Travelling Salesman Problem and the Set Covering Problem. After a brief description of this class of problems, it is demonstrated that the original Hopfield model is incapable of supplying valid solutions. This is attributed to the presence of constant bias currents in the dynamic of the neural model. A demonstration of this is given and then a novel neural model is presented which continues to be based on the same architecture as the Hopfield model, but introduces modifications thanks to which the integer linear programming problems presented can be solved. Some numerical examples and concluding remarks highlight the solving capacity of the novel neural model.

Explore related subjects

Linear ModelsNeural Networks, ComputerSoftwareJournal Article

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

S Cavalieri. 1999. Solving linear integer programming problems by a novel neural model.. https://doi.org/10.1142/s0129065799000046

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2025

A robust transfer learning approach for high-dimensional linear regression to support integration of multi-source gene expression data.

Transfer learning aims to integrate useful information from multi-source datasets to improve the learning performance of target data. This can be effectively applied in genomics when we learn the gene associations in a target tissue, and data from other tissues can be integrated. However, heavy-tail distribution and outliers are common in genomics data, which poses challenges to the effectiveness of current transfer learning approaches. In this paper, we study the transfer learning problem under high-dimensional linear models with t-distributed error (Trans-PtLR), which aims to improve the estimation and prediction of target data by borrowing information from useful source data and offering robustness to accommodate complex data with heavy tails and outliers. In the oracle case with known transferable source datasets, a transfer learning algorithm based on penalized maximum likelihood and expectation-maximization algorithm is established. To avoid including non-informative sources, we propose to select the transferable sources based on cross-validation. Extensive simulation experiments as well as an application demonstrate that Trans-PtLR demonstrates robustness and better performance of estimation and prediction when heavy-tail and outliers exist compared to transfer learning for linear regression model with normal error distribution. Data integration, Variable selection, T distribution, Expectation maximization algorithm, Genotype-Tissue Expression, Cross validation.

Linear Models↗
PubMed2000

A recurrent neural network for solving linear projection equations.

Linear projection equations arise in many optimization problems and have important applications in science and engineering. In this paper, we present a recurrent neural network for solving linear projection equations in real time. The proposed neural network has two layers and is amenable to parallel implementation with simple hardware. In the theoretical aspect, we prove that the proposed neural network can converge globally to the solution set of the problem when the matrix involved in the problem is positive semidefinite and can converge exponentially to a unique solution when the matrix is positive definite. In addition, we analyze the stability of the related dynamic system in detail. As an application, we show that the proposed neural network can be used directly to solve linear and convex quadratic programming problems and linear complementary problems with positive semidefinite matrices. The validity and transient behavior of the neural network are demonstrated by using three numerical examples.

Linear Models↗