A primal all-integer algorithm based on irreducible solutions (Q1424268): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10107-003-0384-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1989905452 / rank | |||
Normal rank |
Latest revision as of 21:55, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A primal all-integer algorithm based on irreducible solutions |
scientific article |
Statements
A primal all-integer algorithm based on irreducible solutions (English)
0 references
11 March 2004
0 references
A primal augmentation algorithm for linear integer programs is given. First it is shown how a feasible solution of the IP (or a basis of slack variables) is turned into a basic feasible solution of an appropriate simplex tableau. Then nonbasic columns of the tableau are replaced by other columns to obtain ``proper reformulations'' of the tableau, so that every feasible direction w.r.t the basic feasible solution can be represented by the new non-basic variables. The integral basis method then performs these reformulations until either optimality is proved or an improving direction (an augmentation vector) is found. It is proved that each reformulation step is finite and that the algorithm is finite. A variant of the algorithm that uses discrete relaxations of the integer program is given and its correctness shown. Three types of such relaxations are studied in more detail. These are irreducible solutions from Gomory cuts, from primitive partition identities, and from strengthened 0/1 knapsack relaxations. They differ in the tradeoff between the strength of the relaxation and the cost of computing the irreducible solutions. At the end of the paper notes on implementation of the integral basis method and computational results are mentioned.
0 references
integer programming
0 references
primal augmentation algorithm
0 references
integral basis method
0 references