A Monte-Carlo approach for 0-1 programming problems (Q1195974)

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.