Statistical mechanics of the multi-constraint continuous knapsack problem

DOI10.1088/0305-4470/30/4/008MaRDI QIDQ4783652zbMATH OpenOpenAlexFDO

Authors Jun-Ichi Inoue

Publication date 8 December 2002

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9708147

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Neural nets applied to problems in time-dependent statistical mechanics (82C32)

Abstract: We apply the replica analysis established by Gardner to the multi-constraint continuous knapsack problem,which is one of the linear programming problems and a most fundamental problem in the field of operations research (OR). For a large problem size, we analyse the space of solution and its volume, and estimate the optimal number of items to go into the knapsack as a function of the number of constraints. We study the stability of the replica symmetric (RS) solution and find that the RS calculation cannot estimate the optimal number of items in knapsack correctly if many constraints are required.In order to obtain a consistent solution in the RS region,we try the zero entropy approximation for this continuous solution space and get a stable solution within the RS ansatz.On the other hand, in replica symmetry breaking (RSB) region, the one step RSB solution is found by Parisi's scheme. It turns out that this problem is closely related to the problem of optimal storage capacity and of generalization by maximum stability rule of a spherical perceptron.

Recommendations

• Statistical mechanics of the knapsack problem
• A statistical analysis of the knapsack problem
• Statistical mechanics analysis of generalized multi-dimensional knapsack problems
• A stochastic linear knapsack problem
• Random knapsacks with many constraints

Cited in

(3)

• Computing Optimized Path Integrals for Knapsack Feasibility
• Statistical mechanics analysis of generalized multi-dimensional knapsack problems
• Dual mean field search for large scale linear and quadratic knapsack problems

This page was built for publication: Statistical mechanics of the multi-constraint continuous knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4783652)