What is recorded here?
Gomory derives an integer-valid constraint from a fractional row of a linear-programming tableau, excluding the current fractional answer while retaining integer solutions. His 1958 announcement outlines an integer-programming algorithm but defers its full termination rule and proof. A linear optimizer may recommend half a machine or a fraction of a shipment when the decision must be a whole number. Simply rounding can break other constraints. Gomory instead derives a new constraint from the fractional parts of an existing equation. This cut removes the current fractional answer while preserving every integer answer allowed by that equation. The linear problem can then be optimized again with the new constraint. The note explains why the cut is valid and reports tests on small problems. It also makes a crucial distinction: the special choices that guarantee eventual termination, and their complete proof, are deferred to a longer treatment. The contribution recorded here is the automatic integer-valid cut construction and the algorithm announcement, rather than a complete proof of every cutting strategy or a modern mixed-integer solver.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
Exact 1958 Bulletin AMS 64(5), 275-278 announcement; Damaged tableau notation and computer-model text are not certified transcriptions. The displayed construction uses nonnegative integer variables, including objective and slack variables; modern mixed-integer cuts are a different target. Page 276 and page 278 explicitly defer the complete termination-enforcing choices and finiteness proof to a longer paper. The supplied cut-validity explanation does not make arbitrary row-selection heuristics convergent. Earlier manually constructed cuts by Dantzig/Fulkerson/Johnson and Markowitz/Manne are acknowledged. The largest reported small test had at most seven variables; no modern solver benchmark or general efficiency claim is established. Row selection is nonunique and the suggested deepest-fraction rule is heuristic. A. Tucker communicated the note and Princeton-IBM supplied institutional support; neither role is coauthorship. Later complete algorithms, mixed-integer variants and branch-and-cut implementations remain separate.
Read the original work
- Gomory: cutting away a fractional answer without losing integer solutions; exact original technical paper
- Publisher-deposited identity for gomory-fractional-integer-cuts-1958
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Ralph E. Gomory
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Gomory: cutting away a fractional answer without losing integer solutions
Gomory derives an integer-valid constraint from a fractional row of a linear-programming tableau, excluding the current fractional answer while retaining integer solutions. His 1958 announcement outlines an integer-programming algorithm but defers its full termination rule and proof.
A linear optimizer may recommend half a machine or a fraction of a shipment when the decision must be a whole number. Simply rounding can break other constraints. Gomory instead derives a new constraint from the fractional parts of an existing equation. This cut removes the current fractional answer while preserving every integer answer allowed by that equation. The linear problem can then be optimized again with the new constraint. The note explains why the cut is valid and reports tests on small problems. It also makes a crucial distinction: the special choices that guarantee eventual termination, and their complete proof, are deferred to a longer treatment. The contribution recorded here is the automatic integer-valid cut construction and the algorithm announcement, rather than a complete proof of every cutting strategy or a modern mixed-integer solver.
Scientific scope
Exact 1958 Bulletin AMS 64(5), 275-278 announcement; Damaged tableau notation and computer-model text are not certified transcriptions. The displayed construction uses nonnegative integer variables, including objective and slack variables; modern mixed-integer cuts are a different target. Page 276 and page 278 explicitly defer the complete termination-enforcing choices and finiteness proof to a longer paper. The supplied cut-validity explanation does not make arbitrary row-selection heuristics convergent. Earlier manually constructed cuts by Dantzig/Fulkerson/Johnson and Markowitz/Manne are acknowledged. The largest reported small test had at most seven variables; no modern solver benchmark or general efficiency claim is established. Row selection is nonunique and the suggested deepest-fraction rule is heuristic. A. Tucker communicated the note and Princeton-IBM supplied institutional support; neither role is coauthorship. Later complete algorithms, mixed-integer variants and branch-and-cut implementations remain separate.
People and systems
Ralph E. Gomory