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 条
[11]  
Hall M., 1967, COMBINATORIAL THEORY
[12]   EFFICIENT HEURISTIC PROCEDURES FOR INTEGER LINEAR PROGRAMMING WITH AN INTERIOR [J].
HILLIER, FS .
OPERATIONS RESEARCH, 1969, 17 (04) :600-&
[13]  
IBARAKI T, 1974, MATH PROGRAMMING STU, V2, P115
[14]   EXPERIMENTAL RESULTS ON HILLIERS LINEAR SEARCH [J].
JEROSLOW, RG ;
SMITH, THC .
MATHEMATICAL PROGRAMMING, 1975, 9 (03) :371-376
[15]   PENALTY FOR ZERO-ONE INTEGER EQUIVALENT PROBLEM [J].
KALANTARI, B ;
ROSEN, JB .
MATHEMATICAL PROGRAMMING, 1982, 24 (02) :229-232
[16]  
Karmarkar N., 1990, P MATH PROGRAMMING S, P351
[17]  
Levenberg KA., 2018, Q APPL MATH, V2, P436, DOI [DOI 10.1090/QAM/10666, 10.1016/j.healun.2011.11.021, 10.1090/qam/10666]
[18]   AN ALGORITHM FOR LEAST-SQUARES ESTIMATION OF NONLINEAR PARAMETERS [J].
MARQUARDT, DW .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1963, 11 (02) :431-441
[19]  
MORE J, 1978, P DUNDEE C NUMERICAL
[20]   COMPUTING A TRUST REGION STEP [J].
MORE, JJ ;
SORENSEN, DC .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1983, 4 (03) :553-572