An interior point algorithm to solve computationally difficult set covering problems

DOI10.1007/BF01582907zbMath0753.90046MaRDI QIDQ1181917

K. G. Ramakrishnan, Mauricio G. C. Resende, Narendra K. Karmarkar

Publication date: 27 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

ellipsoidfeasible pointsinner point methodnonconvex potentials

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (29)

An exact algorithm for the maximum stable set problem ⋮ Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach ⋮ Improved solutions to the Steiner triple covering problem ⋮ An algorithm for large scale 0-1 integer programming with application to airline crew scheduling ⋮ Matrix representation and gradient flows for NP-hard problems ⋮ An approach to guided learning of Boolean functions ⋮ Potential reduction algorithms for structured combinatorial optimization problems ⋮ Solving real-world linear ordering problems using a primal-dual interior point cutting plane method ⋮ A potential reduction approach to the frequency assignment problem ⋮ On the minimum number of logical clauses inferred from examples ⋮ Trust region affine scaling algorithms for linearly constrained convex and concave programs ⋮ Solving hard set covering problems ⋮ The design of a 0-1 integer optimizer and its application in the Carmen system ⋮ Constraint Orbital Branching ⋮ Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem ⋮ Solving combinatorial optimization problems using Karmarkar's algorithm ⋮ A continuous approach to inductive inference ⋮ A biased random-key genetic algorithm for the Steiner triple covering problem ⋮ An intelligent algorithm for mixed-integer programming models ⋮ A continuous approch for globally solving linearly constrained quadratic ⋮ An efficient mean field approach to the set covering problem ⋮ Solving large Steiner Triple Covering Problems ⋮ Models and solution techniques for frequency assignment problems ⋮ A random-key GRASP for combinatorial optimization ⋮ Computational experience with an interior point algorithm on the satisfiability problem ⋮ Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid ⋮ Investigation of path-following algorithms for signomial geometric programming problems ⋮ Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT ⋮ Interior-point algorithms for global optimization

Uses Software

• GQTPAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothing by spline functions. II
• Constrained global optimization: algorithms and applications
• A probabilistic heuristic for a computationally difficult set covering problem
• Penalty for zero–one integer equivalent problem
• Computing a Trust Region Step
• Methods for Global Concave Minimization: A Bibliographic Survey
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• A note on some computationally difficult set covering problems
• Interior Path Methods for Heuristic Integer Programming Procedures
• Computing Optimal Locally Constrained Steps
• Experimental results on Hillier's linear search
• An Improved Implicit Enumeration Approach for Integer Programming
• On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
• Efficient Heuristic Procedures for Integer Linear Programming with an Interior
• Technical Note—A Note on Zero-One Integer and Concave Programming
• Concave Programming Applied to a Special Class of 0-1 Integer Programs
• A method for the solution of certain non-linear problems in least squares

This page was built for publication: An interior point algorithm to solve computationally difficult set covering problems