A Monte-Carlo approach for 0-1 programming problems

DOI10.1007/BF02238637MaRDI QIDQ1195974zbMATH OpenFDO

Authors J. Sobczynska, Marida Bertocchi, Luca Brandolini, Leon Slominski

Publication date 11 January 1993

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02238637

zbMATH Keywords

computational experimentsdiscrete optimizationlinear \(0-1\) multi-knapsack problemsMonte-Carlo searchNP-hard \(0-1\) optimization problemsorder statisticstwo-phase global random search procedure

Mathematics Subject Classification ID

Order statistics; empirical distribution functions (62G30) Monte Carlo methods (65C05) Numerical mathematical programming methods (65K05) Boolean programming (90C09)

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.

Recommendations

• scientific article; zbMATH DE number 4097132
• Mixed integer programming for the 0--1 maximum probability model.
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Stochastic Discrete Optimization
• Probabilistic approach to assessment of heuristics in 0?1 linear programming

Cited in

(9)

• Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming
• On polynomial complexity of a stochastic algorithm for mixed zero-one programs.
• Mixed integer programming for the 0--1 maximum probability model.
• A new filled function method for nonlinear integer programming problem
• Satisfying the customer
• scientific article; zbMATH DE number 4097132 (Why is no real title available?)
• Monte-Carlo approximation algorithms for enumeration problems
• An approximate algorithm for nonlinear integer programming
• A discrete dynamic convexized method for nonlinear integer programming

This page was built for publication: A Monte-Carlo approach for 0-1 programming problems

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