On chv
tal's cutting planes in integer linear programming
Author:
I.G. Rosenberg a
| Affiliation: | a Centre de recherches math matiques, Universit de Montr al, Qu , Canada |
DOI:
10.1080/02331887508801232
Publication Frequency:
6 issues per year
Subjects:
Mathematical Statistics;
Statistical Theory & Methods;
Statistics;
Statistics for the Biological Sciences;
Stochastic Models & Processes;
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
A new class of cutting planes (for integar linear programs) recently introduced by V. Chv
tal is discussed. It is shown that Gomary's fundamental cuts are special cases of these cuts. A formula for the depth of a cut with respect to the cone is found. For cuts formed from from binding inequalities only, the optimal choice is reduced to a system of non-linear integar programs. It is shown that under special circumstances Chv tal's cuts formed from all inequalities can be replaced by cuts formed from binding inequalities without decreasing the depth. The above results re applied to fundamental cuts.
|
| view references (7) |

Download Citation


matiques, Universit
tal is discussed. It is shown that Gomary's fundamental cuts are special cases of these cuts. A formula for the depth of a cut with respect to the cone is found. For cuts formed from from binding inequalities only, the optimal choice is reduced to a system of non-linear integar programs. It is shown that under special circumstances Chv
CiteULike
Del.icio.us
BibSonomy
Connotea