Journal of Optimization Theory and Applications, to appear, 2012

Abstract: We propose a novel generalization of the Canonical Difference of Convex problem (CDC), and we study the convergence of outer approximation algorithms for its solution, which use an approximated oracle for checking the global optimality conditions. Although the approximated optimality conditions are similar to those of CDC, this new class of problems is shown to significantly differ from its special case. Indeed, outer approximation approaches for CDC need be substantially modified in order to cope with the more general problem, bringing to new algorithms. We develop a hierarchy of conditions that guarantee global convergence, and we build three different cutting plane algorithms relying on them.

Keywords: Single Reverse Polar Problems, Approximate Optimality Conditions, Cutting Plane Algorithms

SIAM Journal on Optimization 21(4), p. 1418 - 1438, 2011

Abstract: We present a bundle method for convex nondifferentiable minimization where the model is a piecewise quadratic convex approximation of the objective function. Unlike standard bundle approaches, the model only needs to support the objective function from below at a properly chosen (small) subset of points, as opposed to everywhere. We provide the convergence analysis for the algorithm, with a general form of master problem which combines features of trust-region stabilization and proximal stabilization, taking care of all the important practical aspects such as proper handling of the proximity parameters and of the bundle of information. Numerical results are also reported.

Keywords: NonDifferentiable Optimization, Bundle methods, Quadratic model.

Computers & Operations Research 38(12), p. 1805 - 1815, 2011

Abstract: This paper concerns the problem of minimizing the maximum link utilization of IP telecommunication networks under the joint use of traditional IGP routing protocols, such as IS-IS and OSPF, and the more sophisticated MPLS-TE technology. It is shown that the problem of choosing the optimal routing, both under working conditions and under single link failure scenarios, can be casted as a Linear Program of reasonable size. The proposed model is validated by a computational experimentation performed on synthetic and real networks: the obtained results show that the new approach considerably reduces the maximum link utilization of the network with respect to simply optimizing the IGP weights, at the cost of adding a limited number of label switched paths (LSPs). Optimizing the set of IGP weights within the overall approach further improves performances. The computational time needed to solve the models matches well with real-time requirements, and makes it possible to consider network design problems.

Keywords: Routing problems, LP models, Robustness

Mathematical Programming, to appear, 2011

Abstract: One of the foremost difficulties in solving Mixed Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pumps algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pumps algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pumps algorithms is that, unlike most previous successive projection methods from the literature, projection is ``naturally'' taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performances of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm.

Keywords: Feasibility Pump, MINLP, Global Optimization, nonconvex NLP.

Mathematical Programming, to appear, 2011

Abstract: We discuss an algorithmic scheme, which we call the stabilized structured Dantzig-Wolfe decomposition method, for solving large-scale structured linear programs. It can be applied when the subproblem of the standard Dantzig-Wolfe approach admits an alternative master model amenable to column generation, other than the standard one in which there is a variable for each of the extreme points and extreme rays of the corresponding polyhedron. Stabilization is achieved by the same techniques developed for the standard Dantzig-Wolfe approach and it is equally useful to improve the performance, as shown by computational results obtained on an application to the multicommodity capacitated network design problem.

Keywords: Dantzig-Wolfe Decomposition Method, Structured Linear Program, Multicommodity Capacitated Network Design Problem, Reformulation, Stabilization

Operations Research 59(5), p. 1225 - 1232, 2011

Abstract: The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed Integer Non Linear Programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed Integer Second Order Cone Program (provided that the original objective function is SOCP-representable), or as a Semi-Infinite MINLP. In this paper, we show that under some further assumptions (rather restrictive, but satisfied in several practical applications), the PR of a Mixed Integer Quadratic Program can also be reformulated as a piecewise quadratic problem, ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, then this structure is typically preserved in the reformulation, thus allowing the construction of specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a quadratic-cost (single-commodity) network design problem.

Keywords: Mixed Integer Non Linear Problems, Semicontinuous Variables, Perspective Relaxation, Sensor Placement Problem, Network Design Problem

International Journal of Electrical Power and Energy Systems 33, p. 585 - 593, 2011

Abstract: The short-term Unit Commitment (UC) problem in hydro-thermal power generation is a fundamental problem in short-term electrical generation scheduling. Historically, Lagrangian techniques have been used to tackle this large-scale, difficult Mixed-Integer NonLinear Program (MINLP); this requires being able to efficiently solve the Lagrangian subproblems, which has only recently become possible (efficiently enough) for units subject to significant ramp constraints. In the last years, alternative approaches have been devised where the nonlinearities in the problem are approximated by means of piecewise-linear functions, so that UC can be approximated by a Mixed-Integer Linear Program (MILP); in particular, using a recently developed class of valid inequalities for the problem, called "Perspective Cuts", significant improvements have been obtained in the efficiency and effectiveness of the solution algorithms. These two different approaches have complementary strengths; Lagrangian ones provide very good lower bounds quickly, but they require sophisticated heuristics—which may need to be changed every time that the mathematical model changes—for producing actual feasible solutions. MILP approaches have been shown to be able to provide very good feasible solutions quickly, but their lower bound is significantly worse. We present a sequential approach which combines the two methods, trying to exploit each one's strengths; we show, by means of extensive computational experiments on realistic instances, that the sequential approach may exhibit significantly better efficiency than either of the two basic ones, depending on the degree of accuracy requested to the feasible solutions.

Keywords: Hydro-Thermal Unit Commitment, Mixed-Integer NonLinear Program Formulations, Lagrangian Relaxation

Technical Report 11-08, Dipartimento di Informatica, Università di Pisa, 2011

Abstract: We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are "easy", that is, they are Lagrangian functions of explicitly known convex programs with "few" variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In this case one can insert in the master problem a suitably modified representation of the original convex subproblem, as an alternative to iteratively inner-approximating it by means of the produced extreme points, thus providing the algorithm with exact information about a part of the objective function, possibly leading to performance improvements. This is shown to happen in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems.

Keywords: Nondifferentiable Optimization, Bundle methods, Lagrangian Relaxation, Partial Dantzig-Wolfe Decomposition, Multicommodity Network Design.

Operations Research Letters 39(1), p. 36 - 39, 2011

Abstract: This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.

Keywords: Robust Optimization, Network Design, Hose Model

in Lecture Notes in Computer Science vol. 6683, 5^th Learning and Intelligent OptimizatioN Conference - LION 5, C.A. Coello Coello ed., p. 407 - 422, Springer-Verlag, 2011

G. Bigi, A. Frangioni, Q.H. Zhang

Journal of Global Optimization 46(2), p. 163 - 189, 2010

Abstract: The paper discusses a general framework for outer approximation type algorithms for the canonical DC optimization problem. The algorithms rely on a polar reformulation of the problem and exploit an approximated oracle in order to check global optimality. Consequently, approximate optimality conditions are introduced and bounds on the quality of the approximate global optimal solution are obtained. A thorough analysis of properties which guarantee convergence is carried out; two families of conditions are introduced which lead to design six implementable algorithms, whose convergence can be proved within a unified framework.

Keywords: DC problems, Polar Set, Approximate Optimality Conditions, Cutting Plane Algorithms

in Lecture Notes in Computer Science vol. 6049, 9^th International Symposium on Experimental Algorithms - SEA 2010, P. Festa ed., Springer-Verlag, p. 350 - 360, 2010

Abstract: We present a new Feasibility Pump algorithm tailored for nonconvex Mixed Integer Nonlinear Programming problems. Differences with the previously proposed Feasibility Pump algorithms and difficulties arising from nonconvexities in the models are extensively discussed. The main methodological innovations of this variant are: (a) the first subproblem is a nonconvex continuous Nonlinear Program, which is solved using global optimization techniques; (b) the solution method for the second subproblem is complemented by a tabu list. We exhibit computational results showing the good performance of the algorithm on instances taken from the MINLPLib.

Keywords: Mixed-Integer Nonlinear Programming, nonconvex, heuristic method, experiments.

Operations Research Letters 38, p. 341 - 345, 2010

Abstract: Interval-gradient cuts are (nonlinear) valid inequalities derived from continuously differentiable nonconvex constraints. In this paper we define interval-subgradient cuts, a generalization to nondifferentiable constraints, and show that no-good cuts with 1-norm are a special case of interval-subgradient cuts. We then briefly discuss what happens if other norms are used.

Technical Report 10-02, Dipartimento di Informatica, Università di Pisa, 2010

Abstract: We consider multi-iterative techniques of multigrid type for the numerical solution of large linear systems with (weighted) structure of graph. We combine proper coarser-grid operators with auxiliary techniques. We show that the most effective smoothers have to be of Krylov type with spanning tree preconditioners, while the projectors have to be designed for maintaining as much as possible the structure of graph matrix at the inner levels. Some necessary and sufficient conditions are proved; in this framework it is possible to explain why the classical projectors inherited from differential equations are good in the differential context and why they behave unsatisfactorily for unstructured graphs. Several numerical experiments have been conducted showing that our approach is effective even in very difficult cases where the known approaches are rather slow.

Keywords: Graph Matrices, Multigrid, Conditioning and Preconditioning

Proceedings of the European Workshop on Mixed Integer Nonlinear Programming 2010 (EWMINLP10), P. Bonami, L. Liberti, A.J. Miller, A. Sartenaer editors, Marseille, April 12-16 2010

Abstract: The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed-Integer NonLinear Problems with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed-Integer Second-Order Cone Program, provided that the original objective function is SOCP-representable, or as a Semi-Infinite MINLP. We show that under some further assumptions-rather restrictive, but satisfied in several practical applications-the PR of Mixed-Integer Quadratic Programs can also be reformulated as a piecewise linear-quadratic problem of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, this is typically preserved in the reformulation, allowing to construct specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a Quadratic-cost (single-commodity) network design problem.

Keywords: Mixed-Integer Quadratic Problems, Perspective Relaxation

in Complex Systems Design & Management: Proceedings of the First International Conference on Complex Systems Design & Management CSDM 2010, M. Aiguier, F. Bretaudeau and D. Krob eds., Springer-Verlag, p. 85 - 97, 2010

Abstract: Complex, hierarchical, multi-scale industrial and natural systems generate increasingly large mathematical models. I-DARE is a structure-aware modeling-reformulating-solving environment based on Declarative Programming, that allows the construction of complex structured models. The main aim of the system is to produce models that can be automatically and algorithmically reformulated to search for the "best" formulation, intended as the one for which the most efficient solution approach is available. This requires exploration of a high-dimensional space comprising all (structured) reformulations of a given instance, all available solvers for (each part of) the formulation, and all possible configurations of the relevant algorithmic parameters for each solver. A fundamental pre-requisite for this exploration is the ability to predict the efficiency of a given (set of) algorithm(s), considering their configuration(s), for a given instance; this is, however, a vastly nontrivial task. This article describes how the I-DARE system organizes the information on the instance at hand in order to make the search in the (formulation, solver, configuration) space possible with several different exploration techniques. In particular, we propose a way to combine general machine learning mechanisms and ad-hoc methods, where available, in order to effectively compute the "objective function" of the search, i.e., the prediction of the effectiveness of a point in the space. We also discuss how this mechanism can take upon itself part of the exploration, the one in the sub-space of configurations, thus simplifying the task to the rest of the system by reducing the dimensionality of the search space it has to traverse.

Keywords: Mathematical Models, Machine Learning, Automatic Algorithm Selection, Reformulation

Discrete Applied Mathematics 157(6), p. 1167 - 1184, 2009

Abstract: Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be solved. Although succesfully employed in many applications, these approaches suffer from well-known instability issues that somewhat limit their efficiency. Building on the theory developed for nondifferentiable optimization algorithms, a large class of stabilized column generation algorithms can be defined which avoid the instability issues by using an explicit stabilizing term in the dual; this amounts at considering a (generalized) augmented Lagrangian of the primal master problem. Since the theory allows for a great degree of flexibility in the choice and in the management of the stabilizing term, one can use piecewise-linear or quadratic functions that can be efficiently dealt with off-the-shelf solvers. The effectiveness in practice of this approach is demonstrated by extensive computational experiments on large-scale Vehicle and Crew Scheduling problems. Also, the results of a detailed computational study on the impact of the different choices in the stabilization term (shape of the function, parameters), and their relationships with the quality of the initial dual estimates, on the overall effectiveness of the approach are reported, providing practical guidelines for selecting the most appropriate variant in different situations.

Keywords: Column Generation, Proximal Point methods, Bundle methods, Vehicle and Crew Scheduling problems

Optimization Methods and Software 25(1), p. 19 - 27, 2009

Abstract: In this paper we study approximate optimality conditions for the Canonical DC (CDC) optimization problem and their relationships with stopping criteria for a large class of solution algorithms for the problem. In fact, global optimality conditions for CDC are very often restated in terms of a nonconvex optimization problem, that has to be solved each time the optimality of a given tentative solution has to be checked. Since this is in principle a costly task, it makes sense to only solve the problem approximately, leading to an inexact stopping criteria and therefore to approximate optimality conditions. In this framework, it is important to study the relationships between the approximation in the stopping criteria and the quality of the solutions that the corresponding approximated optimality conditions may eventually accept as optimal, in order to ensure that a small tolerance in the stopping criteria does not lead to a disproportionally large approximation of the optimal value of the CDC problem. We develop conditions ensuring that this is the case; these turn out to be closely related with the well-known concept of regularity of a CDC problem, actually coinciding with the latter if the reverse-constraint set is a polyhedron.

Keywords: DC problems, Approximate Optimality Conditions, Value Function, Lipschitz Property

in Proceedings of the 7^th International Workshop on the Design of Reliable Communication Networks (DRCN 2009), D. Medhi, J. Doucette and D. Tipper editors, IEEE, p. 273 - 280, October 25-28 2009

Abstract: The paper describes an optimization model which aims at minimizing the maximum link utilization of IP telecommunication networks under the joint use of the traditional IGP protocols and the more sophisticated MPLS-TE technology. The survivability of the network is taken into account in the optimization process implementing the path restoration scheme. This scheme benefits of the Fast Re-Route (FRR) capability allowing service providers to offer high availability and high revenue SLAs (Service Level Agreements). The hybrid IGP/MPLS approach relies on the formulation of an innovative Linear Programming mathematical model that, while optimizing the network utilization, provides optimal user performance, efficient use of network resources, and 100% survivability in case of single link failure. The possibility of performing an optimal exploitation of the network resources throughout the joint use of the IGP and MPLS protocols provides a flexible tool for the ISP (Internet Service Provider) networks traffic engineers. The efficiency of the proposed approach is validated by a wide experimentation performed on synthetic and real networks. The obtained results show that a small number of LSP tunnels have to be set up in order to significantly reduce the congestion level of the network while at the same time guaranteeing the survivability of the network.

Keywords: Network Reliability, Optimal Design, Path Restoration, Routing

SIAM Journal on Optimization 20(1), p. 357 - 386, 2009

Abstract: Subgradient methods for nondifferentiable optimization benefit from deflection, i.e., defining the search direction as a combination of the previous direction and the current subgradient. In the constrained case they also benefit from projection of the search direction onto the feasible set prior to computing the steplength, that is, from the use of conditional subgradient techniques. However, combining the two techniques is not straightforward, especially if an inexact oracle is available which can only compute approximate function values and subgradients. We present a convergence analysis of several different variants, both conceptual and implementable, of approximate conditional deflected subgradient methods. Our analysis extends the available results in the literature by using the main stepsize rules presented so far while allowing deflection in a more flexible way. Furthermore, to allow for (diminishing/square summable) rules where the stepsize is tightly controlled a-priori, we propose a new class of deflection-restricted approaches where it is the deflection parameter, rather than the stepsize, which is dynamically adjusted using the "target value" of the optimization sequence. For both Polyak-type and diminishing/square summable stepsizes, we propose a "correction" of the standard formula which shows that, in the inexact case, knowledge about the error computed by the oracle (which is available in several practical applications) can be exploited in order to strengthen the convergence properties of the method. The analysis allows for several variants of the algorithm; at least one of them is likely to show numerical performances similar to these of "heavy ball" subgradient methods, popular within backpropagation approaches to train neural networks, while possessing stronger convergence properties.

Keywords: Convex Programming, Nondifferentiable Optimization, Subgradient Methods, Convergence Analysis, Lagrangian relaxation, Backpropagation

Discrete Applied Mathematics 157(6), p. 1229 - 1241, 2009

Abstract: We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and another based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.

Keywords: Multicommodity Capacitated Network Design, Reformulation, Valid Inequalities, Cutting-Plane Method, Column Generation

Operations Research Letters 37(3), p. 206 - 210, 2009

Abstract: The Perspective Reformulation is a general approach for constructing tight approximations to MINLP problems with semicontinuous variables. Two different reformulations have been proposed for solving it, one resulting in a Second-Order Cone Program, the other based on representing the perspective function by (an infinite number of) cutting planes. We compare the two reformulations on two sets of MIQPs to determine which one is most effective in the context of exact or approximate Branch-and-Cut algorithms.

Keywords: Mixed-Integer Non Linear Programs, Reformulations, Second-Order Cone Programs, Valid Inequalities, Unit Commitment problem, Portfolio Optimization

Proceedings of the 4^th International Network Optimization Conference (INOC2009), G. Bigi, A. Frangioni and M.G. Scutellà editors, paper MD3-1, Pisa, April 26-29, 2009

Abstract: The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed-Integer NonLinear Problems with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed-Integer Second-Order Cone Program (provided that the original objective function is SOCP-representable), or as a Semi-Infinite MINLP. While these reformulations significantly improve the lower bound and the running times of the corresponding enumerative approaches, they may spoil some valuable structure of the problem, such as the presence of network constraints. In this paper, we show that under some further assumptions the PR of a Mixed-Integer Quadratic Program can also be reformulated as a piecewise linear-quadratic problem, ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation and where the (network) structure of the original problem is safeguarded. We apply this approach to a quadratic-cost single-commodity network design problem, comparing the newly developed algorithm with those based on both the standard continuous relaxation and the two usual variants of PR relaxation.

Keywords: Mixed-Integer NonLinear Problems, Semicontinuous Variables, Perspective Relaxation, Nonlinear Network Design Problem

IEEE Transactions on Power Systems 24(1), p. 105 - 113, 2009

Abstract: The short-term Unit Commitment (UC) problem in hydro-thermal power generation is a large-scale, Mixed-Integer NonLinear Program (MINLP), which is difficult to solve efficiently, especially for large-scale instances. It is possible to approximate the nonlinear objective function of the problem by means of piecewise-linear functions, so that UC can be approximated by a Mixed-Integer Linear Program (MILP); applying the available efficient general-purpose MILP solvers to the resulting formulations, good quality solutions can be obtained in a relatively short amount of time. We build on this approach, presenting a novel way to approximating the nonlinear objective function based on a recently developed class of valid inequalities for the problem, called "Perspective Cuts". At least for many realistic instances of a general basic formulation of UC, a MILP-based heuristic obtains comparable or slightly better solutions in less time when employing the new approach rather than the standard piecewise linearizations, while being not more difficult to implement and use. Furthermore, "dynamic" formulations, whereby the approximation is iteratively improved, provide even better results if the approximation is appropriately controlled.

Keywords: Hydro-Thermal Unit Commitment, Mixed-Integer Linear Program Formulations, Valid Inequalities

Technical Report 09-13, Dipartimento di Informatica, Università di Pisa, 2009

Abstract: Complex, hierarchical, multi-scale industrial and natural systems generate increasingly large mathematical models. Practitioners are usually able to formulate such models in their "natural" form; however, solving them often requires finding an appropriate reformulation to reveal structures in the model which make it possible to apply efficient, specialized approaches. I-DARE is a structure-aware modeling-reformulation-solving environment based on Declarative Programming. It allows the construction of complex structured models, that can be automatically and algorithmically reformulated to search for the best formulation, intended as the one for which the most efficient solution approach is available. In order to accommodate (potentially) all possible specialized solution methods, it defines a general software framework for solvers, that are "registered" to specific problem structures. This article describes in details the application of Artificial Intelligence in the modeling and reformulation modules of I-DARE, showing how Declarative Programming can be used to design a structure-aware modeling environment that allows for a new automatic reformulation methodology.

Keywords: Mathematical Models, Optimization Problems, Artificial Intelligence, Declarative Programming

Proceedings of the 4^th International Network Optimization Conference (INOC2009), G. Bigi, A. Frangioni and M.G. Scutellà editors, paper TC2-2, Pisa, April 26-29, 2009

Abstract: When designing or upgrading a communication network, operators are faced with a major issue, as uncertainty on communication demands makes it difficult to correctly provision the network capacity. When a probability on traffic matrices is given, finding the cheapest capacity allocation that guarantees, within a prescribed level of confidence, that each arc can support the traffic demands peaks turns out to be, in general, a difficult non convex optimization problem belonging to the class of chance constrained problems. Drawing from some very recent results in the literature we highlight the relationships between chance constrained network design problems and robust network optimization. We then compare several different ways to build uncertainty sets upon deviation measures, comprised the recently proposed backward and forward deviation measures that capture possible asymmetries of the traffic demands distribution. We report results of a computational study aimed at comparing the performance of different models when built upon the same set of historical traffic matrices.

Keywords: Chance Constraint, Robust Optimization, Network Design, Deviation Measures, Routing.

Chapter 30 of Scienza delle decisioni in Italia: applicazioni della ricerca operativa a problemi aziendali, G. Felici e A. Sciomachen eds., EGIC Genova, p. 429 - 442, 2008

Abstract: Molti problemi reali di schedulazione di veicoli e personale possono essere formulati come varianti di problemi di Set Partitioning, con vincoli complicanti, di grandissime dimensioni. Questi problemi possono essere risolti mediante tecniche basate sulla generazione di colonne, utilizzando sottoproblemi di tipo cammino minimo vincolato. M.A.I.O.R. utilizza da molti anni questo tipo di tecnologie per i propri clienti che operano nell'ambito del trasporto su gomma urbano ed extraurbano, aereo e ferroviario. Recentemente, nella suite degli strumenti M.A.I.O.R. sono stati introdotti alcuni miglioramenti algoritmici che hanno portato a consistenti miglioramenti dell'efficacia degli approcci in tutte le applicazioni. In questo capitolo descriviamo tali miglioramenti ed il loro impatto sulle prestazioni degli algoritmi in diverse applicazioni reali, focalizzandoci in particolare su quei problemi in cui la necessità di risolvere formulazioni nonstandard e/o con molti vincoli complicanti rendeva il precedente approccio scarsamente funzionale, mentre le nuove tecniche permettono di ottenere risultati di buona qualità.

International Journal of Electrical Power and Energy Systems 30, p. 316 - 326, 2008

Optimization Methods and Software 22(4), p. 573 - 585, 2007

Abstract: Interior Point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the KKT systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex "multiple crash start" routine for the combinatorial ones. We report our experiments about allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some "difficult" instances.

Keywords: Min Cost Flow problems, Interior Point Algorithms, Relaxation Method, Crossover

Computational Optimization and Applications, 36(2-3), p. 271 - 287, 2007

Abstract: Support-graph preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the KKT systems that must be solved at each iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners extract a proper triangulated subgraph, with ``large'' weight, of the original graph: in practice, trees and Brother-Connected Trees (BCTs) of depth two have been shown to be the most computationally efficient families of subgraphs. In the literature, approximate versions of the Kruskal algorithm for maximum-weight spanning trees have most often been used for choosing the subgraphs; Prim-based approaches have been used for trees, but no comparison have ever been reported. We propose Prim-based heuristics for BCTs, which require nontrivial modifications w.r.t. the previously proposed Kruskal-based approaches, and present a computational comparison of the different approaches, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones.

Keywords: Min Cost Flow problems, Interior Point Algorithms, Preconditioned Conjugated Gradient method, Prim Algorithm

Operations Research Letters 35(2), p. 181 - 185, 2007

Abstract: Perspective cuts are a computationally effective family of valid inequalities, belonging to the general family of disjunctive cuts, for Mixed-Integer Convex NonLinear Programming problems with a specific structure. The required structure can be forced upon models that would not originally display it by decomposing the Hessian of the problem into the sum of two positive semidefinite matrices, a generic and a diagonal one, so that the latter is "as large as possible". We compare two ways for computing the diagonal matrix: an inexpensive approach requiring a minimum eigenvalue computation and a more costly procedure which require the solution of a SemiDefinite Programming problem. The latter dramatically outperforms the former at least upon instances of the Mean-Variance problem in portfolio optimization.

Keywords: Mixed-Integer Quadratic Programs, Valid Inequalities, SemiDefinite Programming, Portfolio Optimization

Mathematical Programming 106(2), p. 225 - 236, 2006

Abstract: We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive "perspective cuts", a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch-and-Cut approaches for at least two models that, either "naturally" or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization.

Keywords: Mixed-Integer Programs, Valid Inequalities, Unit Commitment Problem, Portfolio Optimization

Operations Research 54(4), p. 767 - 775, 2006

Abstract: We present a dynamic programming algorithm for solving the single-Unit Commitment (1UC) problem with ramping constraints and arbitrary convex cost function. The algorithm is based on a new approach for efficiently solving the single-unit Economic Dispatch (ED) problem with ramping constraints and arbitrary convex cost functions, improving on previously known ones that were limited to piecewise-linear functions. For simple convex functions, such as the quadratic ones typically used in applications, the solution cost of all the involved (ED) problems, comprised that of finding an optimal primal and dual solution, is O(n³). Coupled with a "smart" visit of the state-space graph in the dynamic programming algorithm, this enables one to solve (1UC) in O(n³) overall.

Keywords: Dynamic Programming, Unit Commitment Problem, Ramping Constraints

in Proceedings of the 19^th Mini-EURO Conference in Operational Research Models and Methods in the Energy Sector (ORMMES 2006), Coimbra, 6-8 September 2006

INFORMS Journal On Computing 18(1), p. 61 - 70, 2006

Abstract: In the last two decades, a number of algorithms for the linear single-commodity Min Cost Flow problem (MCF) have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving "from scratch" instances of (MCF), of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of (MCF) have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one which minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for (MCF) under cost reoptimization in the context of decomposition algorithms for the Multicommodity Min Cost Flow problem (MMCF), showing that for some classes of instances the relative performances of the codes doing "from scratch" optimization do not accurately predict the relative performances when reoptimization is used. Since the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for (MCF) problem solvers that we have proposed and implemented.

Keywords: Min Cost Flow problem, Multicommodity Min Cost Flow Problem, Reoptimization.

Annals of Operations Research 139, p. 163 - 193, 2005

Abstract: It is well-known that the Lagrangian dual of an Integer Linear Program (ILP) provides the same bound as a continuous relaxation involving the convex hull of all the optimal solutions of the Lagrangian relaxation. It is less often realized that this equivalence is effective, in that basically all known algorithms for solving the Lagrangian dual either naturally compute an (approximate) optimal solution of the "convexified relaxation", or can be modified to do so. After recalling these results we elaborate on the importance of the availability of primal information produced by the Lagrangian dual within both exact and approximate approaches to the original (ILP), using three optimization problems with different structure to illustrate some of the main points.

Keywords: Lagrangian dual, Integer Linear Programs

Proceedings of the 2^nd International Network Optimization Conference (INOC2005), L. Gouveia and C. Mourao editors, Vol. B1, p. 38 - 43, Lisbon, 20-23 March 2005

Abstract: We study 0-1 reformulations of the Network Loading problem, a capacitated network design problem which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. This result yields three strategies to compute the same lower bound on the optimal value of the problem: 1) A Dantzig-Wolfe (DW) approach applied to the model with general integer variables; 2) A cutting-plane algorithm based on the residual capacity inequalities; 3) A Structured DW method that solves the 0-1 reformulation with extended linking inequalities by variables and constraints generation.

Keywords: Capacitated Network Design, Network Loading, Reformulation, Dantzig-Wolfe Decomposition

Mathematical Programming 104(2-3), p. 375 - 388, 2005

Abstract: The semimetric polytope is an important polyhedral structure lying at the heart of hard combinatorial problems. Therefore, linear optimization over the semimetric polytope is crucial for a number of relevant applications. Building on some recent polyhedral and algorithmic results about a related polyhedron, the rooted semimetric polytope, we develop and test several approaches, mainly based over Lagrangian relaxation and application of Non Differentiable Optimization algorithms, for linear optimization over the semimetric polytope. We show that some of these approaches can obtain very accurate primal and dual solutions in a small fraction of the time required for the same task by state-of-the-art general purpose linear programming technology. In some cases, good estimates of the dual optimal solution (but not of the primal solution) can be obtained even quicker.

Keywords: Semimetric Polytope, Lagrangian Methods, Max-Cut, Network Design

Journal of Combinatorial Optimization 8, p. 195 - 220, 2004

Abstract: We propose new local search algorithms for minimum makespan machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of VRP (Thompson and Psaraftis, 1993) and of CMST (Ahuja, Orlin and Sharma, 1998). Several algorithms for searching the neighborhood are suggested. We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. The minimum makespan machine scheduling problem with identical machines has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. The obtained results are very interesting. On some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms proved to dominate, in gap and in time, competitive benchmark heuristics.

Keywords: Production/scheduling, Approximations/heuristic: Multi-Exchange Neighborhood. Networks/graphs, Flow Algorithms: Disjoint Cycle Computation

in Integer Programming and Combinatorial Optimization - IPCO 2004, D. Bienstock and G. Nemhauser eds., Lecture Notes in Computer Science Vol. 3064, Springer-Verlag, p. 431 - 443, 2004

SIAM Journal on Optimization 14(3), p. 894 - 913, 2004

Abstract: We propose a new set of preconditioners for the iterative solution, via a Preconditioned Conjugate Gradient (PCG) method, of the KKT systems that must be solved at each iteration of an Interior Point (IP) algorithm for the solution of linear Min Cost Flow (MCF) problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We define a new class of triangulated graphs, called Brother-Connected Trees (BCT), and discuss some fast heuristics for finding BCTs of "large" weight. Computational experience shows that the new preconditioners can complement tree preconditioners, outperforming them both in iterations count and in running time on some classes of graphs.

Keywords: Min Cost Flow problems, Interior Point Algorithms, Preconditioned Conjugated Gradient method, Triangulated Graphs.

IEEE Transactions on Power Systems, 18(1), p. 313 - 323, 2003

Abstract:The paper presents a simple and effective Lagrangian relaxation approach for the solution of the optimal short-term unit commitment problem in hydrothermal power-generation systems. The proposed approach, based on a disaggregated Bundle method for the solution of the dual problem, with a new warm-starting procedure, achieves accurate solutions in few iterations. The adoption of a disaggregated Bundle method not only improves the convergence of the proposed approach but also provides information that are suitably exploited for generating a feasible solution of the primal problem and for obtaining an optimal hydro scheduling. A comparison between the proposed Lagrangian approach and other ones, based on subgradient and Bundle methods, is presented for a simple yet reasonable formulation of the Hydrothermal Unit Commitment problem.

Keywords: Power Generation Operation, Hydrothermal Unit Commitment, Power Generation Dispatch, Lagrangian Relaxation, Bundle Methods

in Proceedings IEEE 2003 Powerteck Bologna Conference, A. Borghetti, C.A. Nucci and M. Paolone editors, Paper n. 547, 2003

Abstract: The paper describes a procedure developed to assist a generating company in choosing the most convenient bidding strategies for a day-ahead electricity energy market. According to the proposed method, the profit maximization problem is transformed into a minimization problem that can be solved by a traditional hydro-thermal unit commitment program after implementing a few modifications. The paper describes the modifications introduced in a unit commitment program based on the Lagrangian relaxation approach and on a disaggregated Bundle method for the solution of the dual problem. It also presents some results obtained for a realistic data set of hydrothermal power plants. The results are discussed in order to emphasize how the method can be applied to assess the bidding strategy choice of a given company.

Keywords: Unit Commitment, Electricity Market, Bidding Strategies

INFORMS Journal on Computing 15(4), p. 369 - 384, 2003

Abstract: We study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited.

Keywords: Networks-Graphs, Multicommodity; Programming, Large-Scale Systems; Programming, Nondifferentiable

Atti della Scuola CIRO 2002, A. Agnetis and G. Di Pillo editors, p. 159 - 264, Pitagora Editrice, 2003

Abstract: Una tecnica molto diffusa per costruire rilassamenti di problemi di Programmazione Lineare Intera (PLI) o mista, ed anche per risolvere problemi di Programmazione Lineare (PL) di grande dimensione, è quella del rilassamento Lagrangiano. È ben noto che il duale Lagrangiano di un problema di PL è equivalente al duale lineare del problema, e quindi al problema stesso, mentre il duale Lagrangiano di un problema di PLI è equivalente al "rilassamento convessificato" del problema in cui appare l'inviluppo convesso dei punti interi che soddisfano i vincoli non rilassati, ossia una rappresentazione poliedrale della regione ammissibile del rilassamento Lagrangiano. È forse meno noto che gli algoritmi utilizzati per risolvere duali Lagrangiani calcolano automaticamente, o possono farlo con modifiche minori, una soluzione (approssimata) del rilassamento convessificato, fornendo quindi informazione primale che può risultare molto utile quando queste tecniche sono utilizzate all'interno di approcci, esatti o euristici, per risolvere il problema di PLI originale. Mostreremo come questo sia il caso per l'algoritmo dei piani di taglio, noto nel contesto della PL come metodo di decomposizione di Dantzig-Wolfe, e per molte sue varianti, così come per i più recenti algoritmi del tipo subgradiente. Discuteremo poi il possibile uso dell'informazione primale così ottenuta all'interno di approcci per la PLI.

Keywords: Tecniche di Decomposizione, Rilassamenti Lagrangiani, Programmazione Lineare Intera.

Journal of Computational Biology, 10(5), p. 791 - 802, 2003

Abstract: Genes belonging to the same organism are called paralogs when they show a significant similarity in the sequences, even if they have a different biological function. It is an emergent biological paradigm that the families of paralogs in a genome derive from a mechanism of iterated gene duplication-with-modification. In order to investigate the evolution of organisms, it can be useful to infer the duplications that have taken place starting from an hypothetical original gene, and that have led to the current paralog genes family. This information can naturally be represented in a paralogy tree. Here we present a method, called PaTre, to generate a paralogy tree from a family of paralog genes. PaTre uses new techniques motivated by the specific application. The reliability of the inferential process is tested by means of a simulator that implements different hypotheses on the duplication-with-modification paradigm, and checked on real data.

Keywords: Paralog Genes, Paralogy Trees, Transformation Distance, Lightest Spanning Arborescence

SIAM Journal on Optimization 13(1), p. 117 - 156, 2002

Abstract: We study a class of generalized bundle methods for which the stabilizing term can be any closed convex function satisfying certain properties. This setting covers several algorithms from the literature that have been so far regarded as distinct. Under a different hypothesis on the stabilizing term and/or the function to be minimized, we prove finite termination, asymptotic convergence, and finite convergence to an optimal point, with or without limits on the number of serious steps and/or requiring the proximal parameter to go to infinity. The convergence proofs leave a high degree of freedom in the crucial implementative features of the algorithm, i.e., the management of the bundle of subgradients (β-strategy) and of the proximal parameter (t-strategy). We extensively exploit a dual view of bundle methods, which are shown to be a dual ascent approach to one nonlinear problem in an appropriate dual space, where nonlinear subproblems are approximately solved at each step with an inner linearization approach. This allows us to precisely characterize the changes in the subproblems during the serious steps, since the dual problem is not tied to the local concept of ε-subdifferential. For some of the proofs, a generalization of inf-compactness, called *-compactness, is required; this concept is related to that of asymptotically well-behaved functions.

Keywords: Nondifferentiable Optimization, Bundle Methods

in Proceedings IEEE 2001 Powerteck Porto Conference, J.T. Saraiva and M.A. Matos editors, Vol. 3, Paper n. PSO5-397, 2001

Abstract: The paper deals with the solution of the optimal short-term unit commitment (UC) problem in an electric power system. The optimization model takes into account the main operating constraints and physical characteristics of the power generation system. A comparison between Lagrangian heuristics and Tabu Search techniques on different classes of realistic instances is presented. Such a comparison is aimed at highlighting the strong features and the weaknesses of each technique, in view of their application in computer models for competitive electricity markets in progressive evolution. The comparison may provide insights for the construction of hybrid techniques that incorporate the best of both approaches.

Keywords: Lagrangian Relaxation, Optimization Methods, Power Generation Dispatch, Tabu Search, Unit Commitment

in Lecture Notes in Computer Science vol. 1981, Vector and Parallel Processing - VECPAR 2000, J.M. Palma. J. Dongarra and V. Hernandez eds., Springer-Verlag, p. 301 - 315, 2001

Abstract: A parallel implementation of the specialized interior-point algorithm for multicommodity network fows introduced in [5] is presented. In this algorithm, the positive defnite systems of each iteration are solved through a scheme that combines direct factorization and a preconditioned conjugate gradient (PCG) method. Since the solution of at least k independent linear systems is required at each iteration of the PCG, k being the number of commodities, a coarse-grained parallellization of the algorithm naturally arises, where these systems are solved on different processors. Also, several other minor steps of the algorithm are easily parallelized by commodity. An extensive set of computational results on a shared memory machine is presented, using problems of up to 2.5 million variables and 260,000 constraints. The results show that the approach is especially competitive on large, diffcult multicommodity flow problems.

Keywords: Multicommodity Flows, Interior-Point Algorithms, Preconditioned Conjugate Gradient (PCG) Method, Parallel Computing

SIAM Journal on Matrix Analysis and Applications 23(2), p. 339 - 348, 2001

Abstract: We study the extreme singular values of incidence graph matrices, obtaining lower and upper estimates that are asymptotically tight. This analysis is then used for obtaining estimates on the spectral condition number of some weighted graph matrices. A short discussion on possible preconditioning strategies within interior-point methods for network flow problems is also included.

Keywords:Graph Matrices, Conditioning and Preconditioning

Discrete Applied Mathematics, 112(1-3), p. 73 - 99, 2001

Abstract:To efficiently derive bounds for large-scale instances of the capacitated fixed-charge network design problem, Lagrangian relaxations appear promising. This paper presents the results of comprehensive experiments aimed at calibrating and comparing bundle and subgradient methods applied to the optimization of Lagrangian duals arising from two Lagrangian relaxations. This study substantiates the fact that bundle methods appear superior to subgradient approaches because they converge faster and are more robust relative to different relaxations, problem characteristics, and selection of the initial parameter values. It also demonstrates that effective lower bounds may be computed efficiently for large-scale instances of the capacitated fixed-charge network design problem. Indeed, in a fraction of the time required by a standard simplex approach to solve the linear programming relaxation, the methods we present attain very high quality solutions.

Keywords: Multicommodity Capacitated Fixed-Charge Network Design, Lagrangian Relaxation, Subgradient Methods, Bundle Methods

Technical Report 00-09, Dipartimento di Informatica, Università di Pisa, 2000

Abstract: An effective Branch and Bound algorithm based on Lagrangian heuristic is presented, which aims at reducing the gap between the lower and upper bounds. The Branch and Bound method proposed exploits the information gathered while going down in the enumeration tree in order to solve effciently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangian dual. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is used as a benchmark to validate the effciency of the method proposed. Such model simultaneously locates obnoxious facilities and routes obnoxious materials between a set of built-up areas and the facilities. Obnoxious facilities are those facilities which cause nuisance to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. OFLR is a particular case of the Obnoxious Network Design problem which occurs when also an obnoxious network has to be designed such as the case of electric power supplier networks. These are meaningful problems given the industrial development and the increasing importance of environmental issues in our society. The use of the B&B to solve this latter problem is under development.

Chapter 1 in Telecommunications Network Planning, P. Soriano and B. Sanso editors, Kluwer Academics Publisher, p. 1 - 19, 1999

Abstract: This paper presents a comprehensive survey of models and algorithms for multicommodity capacitated network design problems, which are mostly encountered in telecommunications and transportation network planning. These problems are important not only due to the major relevance of their applications, but also because they pose considerable modeling and algorithmic challenges. We present a general arc-based model, describe useful alternative formulations and survey the literature on simplex-based cutting plane and Lagrangian relaxation approaches. We then focus on our own contributions that develop and compare several relaxation methods for a particular case of this model, the fixed-charge problem. These methods are based on Lagrangian relaxation and nondifferentiable optimization techniques, namely, the subgradient and bundle approaches. Our experimental results, while very encouraging, indicate that solving effciently these diffcult problems requires a judicious combination of cutting planes, Lagrangian relaxation methods and sophisticated heuristics. In addition, due to their inherent decomposition properties, these techniques can be adapted to parallel computing environments, which is highly desirable in order to solve realistically sized instances.

Keywords: Multicommodity Capacitated Network Design, Cutting Planes, Lagrangian Relaxation, Nondifferentiable Optimization, Parallel Computing

INFORMS Journal On Computing 11(4), p. 370 - 393, 1999

Abstract: We present a Cost Decomposition approach for the linear Multicommodity Min-Cost Flow problem, where the mutual capacity constraints are dualized and the resulting Lagrangian Dual is solved with a dual-ascent algorithm belonging to the class of Bundle methods. Although decomposition approaches to block-structured Linear Programs have been reported not to be competitive with general-purpose software, our extensive computational comparison shows that, when carefully implemented, a decomposition algorithm can outperform several other approaches, especially on problems where the number of commodities is "large" with respect to the size of the graph. Our specialized Bundle algorithm is characterized by a new heuristic for the trust region parameter handling, and embeds a specialized Quadratic Program solver that allows the efficient implementation of strategies for reducing the number of active Lagrangian variables. We also exploit the structural properties of the single-commodity Min-Cost Flow subproblems to reduce the overall computational cost. The proposed approach can be easily extended to handle variants of the problem.

Keywords: Multicommodity Flows, Bundle methods, Decomposition Methods, Lagrangian Dual

Technical Report 99-05, Dipartimento di Informatica, Università di Pisa, 1999

Abstract: We propose some techniques, based on minimum cost flow computations, for efficiently computing lower bounds for the Capacitated Minimum Spanning Tree problem (CMST). With respect to other methods proposed in the literature, our approaches often provide comparable bounds, with a substantially lower computational cost. For this reason, and for other features discussed in the paper, the proposed methods may be particularly promising in the context of exact algorithms for CMST.

Keywords: Capacitated Minimum Spanning Tree, Minimum Cost Flow, Lagrangian Relaxations

Computers & Operations Research 23(11), p. 1099 - 1118, 1996

Abstract: Bundle methods for Nondifferentiable Optimization are widely recognised as one of the best choices for the solution of Lagrangian Duals; one of their major drawbacks is that they require the solution of a Semidefinite Quadratic Programming subproblem at every iteration. We present an active-set method for the solution of such problems, that enhances upon the ones in the literature by distinguishing among bases with different properties and exploiting their structure in order to reduce the computational cost of the basic step. Furthermore, we show how the algorithm can be adapted to the several needs that arises in practice within Bundle algorithms; we describe how it is possible to allow constraints on the primal direction, how special (box) constraints can be more efficiently dealt with and how to accommodate changes in the number of variables of the nondifferentiable function. Finally, we describe the important implementation issues, and we report some computational experience to show that the algorithm is competitive with other QP codes when used within a Bundle code for the solution of Lagrangian Duals of large-scale (Integer) Linear Programs.

Keywords: Nondifferentiable Optimization, Bundle Methods, Quadratic Programming, Least Squares

Ricerca Operativa, XXV, n. 74, p. 5 - 49, 1995

Abstract: Among practical methods for large-scale Nondifferentiable Optimization (NDO), Bundle methods are widely recognized to play a relevant role; despite thier potential, however, they are not often utilized for maximization of polyhedral functions, that appears in many different contexts such as Lagrangian Duals and decomposition algorithms, since simpler-to-program but less efficient approaches like subgradient methods are preferred. The aim of this work is to provide an applications-oriented survey of the theory of Bundle methods when applied to problems arising in continuous and combinatorial optimization, with an introduction to the several variants of Bundle approaches that can be built up by using a limited set of basic concepts and tools.

Keywords: Nondifferentiable Optimization, Bundle methods, Lagrangian Duals

European Journal of Operational Research 82(3), p. 615 - 646, 1995

Abstract: We extend some known results about the Bilevel Linear Problem (BLP), a hierarchical two-stage optimization problem, showing how it can be used to reformulate any Mixed Integer (Linear) Problem; then, we introduce some new concepts, which might be useful to fasten almost all the known algorithms devised for BLP. As this kind of reformulation appears to be somewhat artificial, we define a natural generalization of BLP, the Bilevel Linear/Quadratic Problem (BL/QP), and show that most of the exact and/or approximate algorithms originally devised for the BLP, such as GSA or K-th Best, can be extended to this new class of Bilevel Programming Problems. For BL/QP, more "natural" reformulations of MIPs are available, leading to the use of known (nonexact) algorithms for BLP as (heuristic) approaches to MIPs: we report some contrasting results obtained in the Network Design Problem case, showing that, although the direct application of our (Dual) GSA algorithm is not of any practical use, we obtain as a by-product a good theoretical characterization of the optimal solutions set of the NDP, along with a powerful scheme for constructing fast algorithms for the Minimum Cost Flow Problem with piecewise convex linear cost functions.

Keywords: Bilevel Problems, Integer Programming, Network Programming