A Monte-Carlo approach for 0-1 programming problems (Q1195974)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A Monte-Carlo approach for 0-1 programming problems |
scientific article |
Statements
A Monte-Carlo approach for 0-1 programming problems (English)
0 references
11 January 1993
0 references
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.
0 references
Monte-Carlo search
0 references
discrete optimization
0 references
computational experiments
0 references
two-phase global random search procedure
0 references
NP-hard \(0-1\) optimization problems
0 references
order statistics
0 references
linear \(0-1\) multi-knapsack problems
0 references
