Browsing by Author "Gondzio, J"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A New Warmstarting Strategy for the Primal-Dual Column Generation Method
    (Springer, 2015) Gondzio, J; González-Brevis, P
    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additionally, the strategy ensures that the duality gap of the warmstart is bounded by the old duality gap multiplied with a (small) constant, which depends on the relation between the old and modified problems. Computational experiments demonstrate the gains achieved when compared to a coldstart approach.
  • Thumbnail Image
    Item
    Base Station Location Optimization for Minimal Energy Consumption in Wireless Networks
    (Vehicular Technology Conference, 2011) González-Brevis, P; Gondzio, J; Fan, Y; Poor, H.; Thompson, J.; Krikidis, I; Chung, P.
    This paper studies the combined problem of base station location and optimal power allocation, in order to optimize the energy efficiency of a cellular wireless network. Recent work has suggested that moving from a network of a small number of high power macrocells to a larger number of smaller microcells may improve the energy efficiency of the network. This paper investigates techniques to optimize the number of base stations and their locations, in order to minimize energy consumption. An important contribution of the paper is that it takes into account non-uniform user distributions across the coverage area, which is likely to be encountered in practice. The problem is solved using approaches from optimization theory that deal with the facility location problem. Stochastic programming techniques are used to deal with the expected user distributions. An example scenario is presented to illustrate how the technique works and the potential performance gains that can be achieved.
  • Thumbnail Image
    Item
    Large-scale Optimization with the Primal-Dual Column Generation Method
    (2016) Gondzio, J; González-Brevis, P; Munari, P
    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems.
  • Thumbnail Image
    Item
    New Developments in the Primal-Dual Column Generation Technique
    (2013) Gondzio, J; González-Brevis, P; Munir, P
    The optimal solutions of the restricted master problems typically leads to an unstable behavior of the standard column generation technique and, consequently, originates an unnecessarily large number of iterations of the method. To overcome this drawback, variations of the standard approach use interior points of the dual feasible set instead of optimal solutions. In this paper, we focus on a variation known as the primal–dual column generation technique which uses a primal–dual interior point method to obtain well-centered non-optimal solutions of the restricted master problems. We show that the method converges to an optimal solution of the master problem even though non-optimal solutions are used in the course of the procedure. Also, computational experiments are presented using linear-relaxed reformulations of three classical integer programming problems: the cutting stock problem, the vehicle routing problem with time windows, and the capacitated lot sizing problem with setup times. The numerical results indicate that the appropriate use of a primal–dual interior point method within the column generation technique contributes to a reduction of the number of iterations as well as the running times, on average. Furthermore, the results show that the larger the instance, the better the relative performance of the primal–dual column generation technique.

Implementado por OpenGeek Services