A Monte-Carlo approach for 0-1 programming problems
type: Item
instance of: scholarly article
title: A Monte-Carlo approach for 0-1 programming problems
zbMATH Open document ID: 0764.65032
DOI: 10.1007/BF02238637
author: J. Sobczynska
author: Marida Bertocchi
author: Luca Brandolini
author: Leon Slominski
published in: Computing
publication date: 1993-01-11T00:00:00Z
review text: A two-phase global random search procedure for solving NP-hard \(0-1\) optimization problems, in which both the feasible domains and the objective functions are described by algebraic separable functions, is proposed. The quality of the random search results is derived from analysis of non-asymptotic order statistics and distribution-free intervals. Computational experiments on linear \(0-1\) multi-knapsack problems are presented showing that the procedure can obtain a solution within a few percentage from the true optimal solution.
reviewed by: Florica Luban
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 62G30
zbMATH DE Number: 86188
zbMATH Keywords: Monte-Carlo search
zbMATH Keywords: discrete optimization
zbMATH Keywords: computational experiments
zbMATH Keywords: two-phase global random search procedure
zbMATH Keywords: NP-hard \(0-1\) optimization problems
zbMATH Keywords: order statistics
zbMATH Keywords: linear \(0-1\) multi-knapsack problems
MaRDI profile type: Publication
cites work: Q3347121
cites work: Q4162318
description: scientific article; zbMATH DE number 86188