A simple strategy for solving a class of 0-1 integer programming models

DOI10.1016/0305-0548(86)90076-6MaRDI QIDQ1090232zbMATH OpenOpenAlexFDO

Authors G. Edward Fox, Gary D. Scudder

Publication date 1986

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(86)90076-6

zbMATH Keywords

cutting planegeneralized set packingheuristiclinear programming relaxation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Large-scale problems in mathematical programming (90C06) Boolean programming (90C09) Integer programming (90C10)

Review text

A strategy is proposed for solving certain generalized set packing models. The strategy is based on using a recently developed heuristic coupled with the solution of the linear programming relaxation of the model. The strategy is programmed, and execution times required for it to obtain optimal solutions to randomly generated models are compared to those required for an implementation of the Gomory cutting plane algorithm. The Cray 1 computer was used for all computations. Computational experience thus gained indicates that the proposed strategy is superior to the Gomory algorithm, and that it seems to perform relatively better on models with relatively higher-density constraint coefficient matrices.

Recommendations

• A heuristic 0-1 integer programming method
• Zero-one integer programs with few constraints - Efficient branch and bound algorithms
• Solving Large-Scale Zero-One Linear Programming Problems
• scientific article; zbMATH DE number 3894836
• A heuristic with tie breaking for certain 0–1 integer programming models

Cites work

• A heuristic with tie breaking for certain 0–1 integer programming models
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• scientific article; zbMATH DE number 3427118 (Why is no real title available?)
• scientific article; zbMATH DE number 3724172 (Why is no real title available?)
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Outline of an algorithm for integer solutions to linear programs

Cited in

(7)

• A heuristic 0-1 integer programming method
• Investigation of solutions of randomly generated integer programming problems with 0-1 variables
• Algorithms for solving the mixed integer two-level linear programming problem
• An analysis of six greedy selection rules on a class of zero-one integer programming models
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• A heuristic with tie breaking for certain 0–1 integer programming models
• An algorithm of internal feasible directions for linear integer programming

This page was built for publication: A simple strategy for solving a class of 0-1 integer programming models

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