AN INTERIOR POINT ALGORITHM TO SOLVE COMPUTATIONALLY DIFFICULT SET COVERING PROBLEMS

被引:36
作者
KARMARKAR, N
RESENDE, MGC
RAMAKRISHNAN, KG
机构
[1] Mathematical Sciences Research Center, AT and T Bell Laboratories, Murray Hill, 07974, NJ
关键词
INTEGER PROGRAMMING; INTERIOR POINT METHOD; STEINER TRIPLE SYSTEMS; SET COVERING;
D O I
10.1007/BF01582907
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We present an interior point approach to the zero-one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.
引用
收藏
页码:597 / 618
页数:22
相关论文
共 27 条
[21]  
Nemhauser G. L., 1988, INTEGER COMBINATORIA
[22]   METHODS FOR GLOBAL CONCAVE MINIMIZATION - A BIBLIOGRAPHIC SURVEY [J].
PARDALOS, PM ;
ROSEN, JB .
SIAM REVIEW, 1986, 28 (03) :367-379
[23]  
PARDALOS PM, 1987, LECTURE NOTES COMPUT, V268
[25]   SMOOTHING BY SPLINE FUNCTIONS .2. [J].
REINSCH, CH .
NUMERISCHE MATHEMATIK, 1971, 16 (05) :451-&
[26]  
Sahni S., 1974, SIAM Journal on Computing, V3, P262, DOI 10.1137/0203021
[27]  
Schrijver A., 1998, THEORY LINEAR INTEGE