| 1. |
- Forsgren, Anders, et al.
(författare)
-
On the existence of a short pivoting sequence for a linear program
- 2020
-
Ingår i: Operations Research Letters. - : Elsevier B.V.. - 0167-6377 .- 1872-7468. ; 48:6, s. 697-702
-
Tidskriftsartikel (refereegranskat)abstract
- We show that given a feasible primal–dual pair of linear programs in canonical form, there exists a sequence of pivots, whose length is bounded by the minimum dimension of the constraint matrix, leading from the origin to the optimum. The sequence of pivots give a sequence of square and nonsingular submatrices of the constraint matrix. Solving two linear equations involving such a submatrix give primal–dual optimal solutions to the corresponding linear program in canonical form.
|
|
| 2. |
- Larsson, Torbjörn, et al.
(författare)
-
Column generation extensions of set covering greedy heuristics
- 2022
-
Ingår i: Operations Research Letters. - : Elsevier. - 0167-6377 .- 1872-7468. ; 50:6, s. 738-744
-
Tidskriftsartikel (refereegranskat)abstract
- Large-scale set covering problems are often approached by constructive greedy heuristics, and many selection criteria for such heuristics have been considered. These criteria are typically based on measures of the cost of setting an additional variable to one in relation to the number of yet unfulfilled constraints that it will satisfy. We show how such greedy selections can be performed on column-oriented set covering models, by using a fractional optimization formulation and solving sequences of ordinary column generation problems for the application at hand.
|
|
| 3. |
- Salman, Raad, 1989, et al.
(författare)
-
Branch-and-bound for the precedence constrained generalized traveling salesman problem
- 2020
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377. ; 48:2, s. 163-166
-
Tidskriftsartikel (refereegranskat)abstract
- The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 hours.
|
|
