Name
Abstract | ||
|---|---|---|
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 poly- tope 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. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BF01582907 | Math. Program. |
Keywords | Field | DocType |
interior point algorithm,set covering.,interior point method,integer programming,computationally difficult set,steiner triple systems,quadratic program,set,interior point,set covering problem,set cover,incidence matrix,steiner triple system | Discrete mathematics,Mathematical optimization,Rounding,Integer programming,Polytope,Quadratic programming,Interior point method,Linear inequality,Mathematics,Covering problems,Algebraic interior | Journal |
Volume | Issue | ISSN |
52 | 3 | 0025-5610 |
Citations | PageRank | References |
32 | 7.32 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Narendra Karmarkar | 1 | 1670 | 490.93 |
| Mauricio G. C. Resende | 2 | 3729 | 336.98 |
| K. G. Ramakrishnan | 3 | 587 | 98.53 |