| 1. |
- Hellstrand, Johan, et al.
(författare)
-
A characterization of the uncapacitated network design polytope
- 1992
-
Ingår i: Operations Research Letters. - 0167-6377 .- 1872-7468. ; 12:3, s. 159-163
-
Tidskriftsartikel (refereegranskat)abstract
- The uncapacitated network design problem is considered. We show that the feasible polytope of the continuous relaxation of this problem has the property that any path along the edges of the convex hull of its integer points is also a path along the edges of the polytope itself. This property may be of computational interest since it implies the possibility of solving the uncapacitated network design problem by a pivoting scheme. © 1992.
|
|
| 2. |
- Bauer, Joanna, et al.
(författare)
-
A fast local search method for minimum energy broadcast in wireless ad hoc networks
- 2009
-
Ingår i: OPERATIONS RESEARCH LETTERS. - : Elsevier BV. - 0167-6377. ; 37:2, s. 75-79
-
Tidskriftsartikel (refereegranskat)abstract
- Local search methods are often used to reduce the power consumption of broadcast routing in wireless networks. For a classic method, sweep, the best available time complexity result is O(vertical bar V vertical bar(4)). We present an O(vertical bar V vertical bar(2))-time method, which exhaustively removes unnecessary transmissions yielding a solution comparable to that of sweep.
|
|
| 3. |
- Ding, Xiao-song, et al.
(författare)
-
A joint pricing and inventory control problem under an energy buy-back program
- 2012
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 40:6, s. 516-520
-
Tidskriftsartikel (refereegranskat)abstract
- The demand for power keeps rising with rapid economic development and growth of industrialization. The frequent mismatch created between demand and supply can be mitigated by the use of energy buyback programs. This paper models a buy-back program using a periodic review joint pricing and inventory model, incorporating compensations and setup cost over finite planning horizons. It is shown that an (s, S, A, P∗) policy is optimal for the decision maker for maximizing the expected total profit.
|
|
| 4. |
- Fogelklou, Oswald, et al.
(författare)
-
On the global stability of a peer-to-peer network model
- 2012
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 40:3, s. 190-194
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we analyze the stability properties of a system of ordinary differential equations describing the thermodynamic limit of a microscopic and stochastic model for file sharing in a peer-to-peer network introduced by Kesidis et al. We show, under certain assumptions, that this BitTorrent-like system has a unique locally attracting equilibrium point which is also computed explicitly. Local and global stability are also shown.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- Lindensjö, Kristoffer
(författare)
-
A regular equilibrium solves the extended HJB system
- 2019
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 47:5, s. 427-432
-
Tidskriftsartikel (refereegranskat)abstract
- Control problems not admitting the dynamic programming principle are known as time-inconsistent. The game-theoretic approach is to interpret such problems as intrapersonal dynamic games and look for subgame perfect Nash equilibria. A fundamental result of time-inconsistent stochastic control is a verification theorem saying that solving the extended HJB system is a sufficient condition for equilibrium. We show that solving the extended HJB system is a necessary condition for equilibrium, under regularity assumptions. The controlled process is a general Ito diffusion.
|
|
| 8. |
- Mastrolilli, Monaldo, et al.
(författare)
-
Minimizing the sum of weighted completion times in a concurrent open shop
- 2010
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 38:5, s. 390-395
-
Tidskriftsartikel (refereegranskat)abstract
- We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if not equal NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. (C) 2010 Elsevier B.V. All rights reserved.
|
|
| 9. |
- Pavon-Marino, P., et al.
(författare)
-
On total traffic domination in non-complete graphs
- 2011
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377. ; 39, s. 40-43
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract in Undetermined Given an undirected graph g(V, E), a set of traffic matrices H and one additional traffic matrix h, we say that H totally dominates h if, for each capacity reservation u supporting H, u also supports h using the same routing pattern. It has been shown that if vertical bar H vertical bar = 1 = (H = {(h) over cap}, say) and g, is a complete graph, H totally dominates h if, and only if, (h) over cap >= h component-wise. In this paper we give a generalized condition for vertical bar H vertical bar >= 1 and any undirected graph.
|
|
| 10. |
- 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.
|
|
