| 1. |
- Almgren, Torgny, 1962, et al.
(author)
-
Optimization models for improving periodic maintenance schedules by utilizing opportunities
- 2012
-
In: Proceedings of 4th Production and Operations Management World Conference, July 2012.
-
Conference paper (peer-reviewed)abstract
- We present mathematical models for finding optimal opportunistic maintenance schedules for systems, in which components are assigned maximum replacement intervals. Our mod- els are applied to safety-critical components in an aircraft engine, for which maintenance opportunities naturally arise since entire modules are sent to the workshop when mainte- nance is required on one or more components. Case study results illustrate the advantage of the mathematical models over simpler policies, the benefit of coordinating the maintenance in economically dependent systems, and that our models can be utilized also for strategic investment decision support.
|
|
| 2. |
- Almgren, Torgny, 1962, et al.
(author)
-
Optimization of opportunistic replacement activities: A case study in the aircraft industry
- 2007
-
Other publication (other academic/artistic)abstract
- In the aircraft industry maximizing availability is essential. Maintenance schedules must therefore be opportunistic, incorporating preventive maintenance activities within the scheduled as well as the unplanned ones. At the same time, the maintenance contractor should utilize opportunistic maintenance to enable the minimization of the total expected cost to have a functional aircraft engine and thus to provide attractive service contracts. This paper provides an opportunistic maintenance optimization model which has been constructed and tested together with Volvo Aero Corporation in Trollhättan, Sweden for the maintenance of the RM12 engine. The model incorporates components with deterministic as well as with stochastic lives. The replacement model is shown to have favourable properties; in particular, when the maintenance occasions are fixed the remaining problem has the integrality property, the replacement polytope corresponding to the convex hull of feasible solutions is full-dimensional, and all the necessary constraints for its definition are facet-inducing. We present an empirical crack growth model that estimates the remaining life and also a case study that indicates that a non-stationary renewal process with Weibull distributed lives is a good model for the recurring maintenance occasions. Using one point of support for the distribution yields a deterministic replacement model; it is evaluated against classic maintenance policies from the literature through stochastic simulations. The deterministic model provides maintenance schedules over a finite time period that induce fewer maintenance occasions as well as fewer components replaced.
|
|
| 3. |
|
|
| 4. |
- Almgren, Torgny, 1962, et al.
(author)
-
The opportunistic replacement problem: analysis and case studies
- 2011
-
Other publication (other academic/artistic)abstract
- We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem generalizes that of Dickman, Epstein, and Wilamowsky [21] and is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic. We show that this basic opportunistic replacement problem is NP-hard. We show that the convex hull of the set of feasible replacement schedules is full-dimensional, and that all the necessary inequalities also are facet-inducing. We show that when maintenance occasions are fixed, the remaining problem can be stated as a linear program; when maintenance costs are monotone with time, the latter is solvable through a greedy procedure. Results from a series of case studies performed in the areas of aircraft engine and wind turbine maintenance are also reported. These illustrate the advantages of utilizing opportunistic maintenance activities based on a complete optimization model, as compared to simpler policies.
|
|
| 5. |
- Almgren, Torgny, 1962, et al.
(author)
-
The opportunistic replacement problem: theoretical analyses and numerical tests
- 2012
-
In: Mathematical Methods of Operations Research. - : Springer Science and Business Media LLC. - 1432-2994 .- 1432-5217. ; 76:3, s. 289-319
-
Journal article (peer-reviewed)abstract
- We consider a model for determining optimal opportunistic maintenance schedules with respect to a maximum replacement interval. This problem generalizes that of Dickman et al. (J Oper Res Soc India 28:165–175, 1991) and is a natural starting point for modelling replacement schedules of more complex systems. We show that this basic opportunistic replacement problem is NP-hard, that the convex hull of the set of feasible replacement schedules is full-dimensional, that all the inequalities of the model are facet-inducing, and present a new class of facets obtained through a {0,1/2}-Chvátal–Gomory rounding. For costs monotone with time, a class of elimination constraints is introduced to reduce the computation time; it allows maintenance only when the replacement of at least one component is necessary. For costs decreasing with time, these constraints eliminate non-optimal solutions. When maintenance occasions are fixed, the remaining problem is stated as a linear program and solved by a greedy procedure. Results from a case study on aircraft engine maintenance illustrate the advantage of the optimization model over simpler policies. We include the new class of facets in a branch-and-cut framework and note a decrease in the number of branch-and-bound nodes and simplex iterations for most instance classes with time dependent costs. For instance classes with time independent costs and few components the elimination constraints are used favorably. For fixed maintenance occasions the greedy procedure reduces the computation time as compared with linear programming techniques for all instances tested.
|
|
| 6. |
- Almgren, Torgny, 1962, et al.
(author)
-
The replacement problem: A polyhedral and complexity analysis. The complete version
- 2009
-
Other publication (other academic/artistic)abstract
- We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem, which generalizes that of Dickman et al., is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic, whence a mathematical study of the model is of large interest. We show that the convex hull of the set of feasible replacement schedules is full-dimensional, and that all the necessary inequalities are facet-inducing. Additional facets are then provided through Chvatal-Gomory rounding. We show that when maintenance occasions are fixed, the remaining problem reduces to a linear program; in some cases the latter is solvable through a greedy procedure. We further show that this basic replacement problem is NP-hard.
|
|
| 7. |
|
|
| 8. |
- Asadi Bagloee, Saeed, et al.
(author)
-
Tradable mobility permit with Bitcoin and Ethereum – A Blockchain application in transportation
- 2019
-
In: Internet of Things (Netherlands). - : Elsevier BV. - 2542-6605. ; 8
-
Journal article (peer-reviewed)abstract
- Blockchain and its underlying technology have intrigued researchers with its promising applications and implications as “the second internet”. There is a wide range of Blockchain applications in transportation and logistics. In this paper, we present the basic principle of cryptocurrencies and Blockchain as well as Ethereum. This is followed by the potential applications of Blockchain in transportation, logistics, and supply chain industries in which the concept of a tradable mobility permit (TMP) to combat traffic congestion is formulated and numerically tested. We then discuss the deployment of the TMP scheme based on a Blockchain platform and its by-products such as dynamic toll pricing, priority for emergency vehicles, heavy truck platooning, as well as connected vehicles.
|
|
| 9. |
- Bagloee, Saeed Asadi, et al.
(author)
-
A hybrid branch-and-bound and Benders decomposition algorithm for the network design problem
- 2017
-
In: Computer-Aided Civil and Infrastructure Engineering. - : Wiley. - 1093-9687 .- 1467-8667. ; 32:4, s. 319-343
-
Journal article (peer-reviewed)abstract
- Given a set of candidate road projects associated with costs, finding the best subset with respect to a limited budget is known as the network design problem (NDP). The NDP is often cast in a bilevel programming problem which is known to be NP-hard. In this study, we tackle a special case of the NDP where the decision variables are integers. A variety of exact solutions has been proposed for the discrete NDP, but due to the combinatorial complexity, the literature has yet to address the problem for large-size networks, and accounting for the multimodal and multiclass traffic flows. To this end, the bilevel problem is solved by branch-and-bound. At each node of the search tree, a valid lower bound based on system optimal (SO) traffic flow is calculated. The SO traffic flow is formulated as a mixed integer, non-linear programming (MINLP) problem for which the Benders decomposition method is used. The algorithm is coded on a hybrid and synchronized platform consisting of MATLAB (optimization engine), EMME 3 (transport planning module), MS Access (database), and MS Excel (user interface). The proposed methodology is applied to three examples including Gao's network, the Sioux-Falls network, and a real size network representing the city of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels have shown promising results.
|
|
| 10. |
|
|
| 11. |
- Bagloee, Saeed Asadi, et al.
(author)
-
A hybrid machine-learning and optimization method to solve bi-level problems
- 2018
-
In: Expert Systems with Applications. - : Elsevier BV. - 0957-4174. ; 95, s. 142-152
-
Journal article (peer-reviewed)abstract
- © 2017 Elsevier Ltd Bi-level optimization has widespread applications in many disciplines including management, economy, energy, and transportation. Because it is by nature a NP-hard problem, finding an efficient and reliable solution method tailored to large sized cases of specific types is of the highest importance. To this end, we develop a hybrid method based on machine-learning and optimization. For numerical tests, we set up a highly challenging case: a nonlinear discrete bi-level problem with equilibrium constraints in transportation science, known as the discrete network design problem. The hybrid method transforms the original problem to an integer linear programing problem based on a supervised learning technique and a tractable nonlinear problem. This methodology is tested using a real dataset in which the results are found to be highly promising. For the machine learning tasks we employ MATLAB and to solve the optimization problems, we use GAMS (with CPLEX solver).
|
|
| 12. |
- Bagloee, S. A., et al.
(author)
-
A Mixed User-Equilibrium and System-Optimal Traffic Flow for Connected Vehicles Stated as a Complementarity Problem
- 2017
-
In: Computer-Aided Civil and Infrastructure Engineering. - : Wiley. - 1093-9687 .- 1467-8667. ; 32:7, s. 562-580
-
Journal article (peer-reviewed)abstract
- Connected vehicles (CVs), be they autonomous vehicles or a fleet of cargo carriers or Uber, are a matter of when they become a reality and not if. It is not unreasonable to think that CV technology may have a far-reaching impact, even to the genesis of a completely new traffic pattern. To this end, the literature has yet to address the routing behavior of the CVs, namely traffic assignment problem (TAP) (perhaps it is assumed, they ought to follow the traditional shortest possible paths, known as user equilibrium [UE]). It is possible that real-time data could be derived from the vehicles' communications that in turn could be used to achieve a better traffic circulation. In this article, we propose a mathematical formulation to ensure the CVs are seeking the system optimal (SO) principles, while the remainder continue to pursue the old-fashioned UE pattern. The model is formulated as a nonlinear complementarity problem (NCP). This article contributes to the literature in three distinct ways: (i) mathematical formulation for the CVs' routing, stated as a mixed UE-SO traffic pattern, is proposed; (ii) a variety of realistic features are explicitly considered in the solution to the TAP including road capacity, elastic demand, multiclass and asymmetric travel time; and (iii) formal proof of the existence and uniqueness of the solutions are also presented. The proposed methodology is applied to the networks of Sioux-Falls and Melbourne.
|
|
| 13. |
|
|
| 14. |
- Bagloee, S. A., et al.
(author)
-
Minimization of water pumps' electricity usage: A hybrid approach of regression models with optimization
- 2018
-
In: Expert Systems with Applications. - : Elsevier BV. - 0957-4174. ; 107, s. 222-242
-
Journal article (peer-reviewed)abstract
- Due to pervasive deployment of electricity-propelled water-pumps, water distribution systems (WDSs) are energy-intensive technologies which are largely operated and controlled by engineers based on their judgments and discretions. Hence energy efficiency in the water sector is a serious concern. To this end, this study is dedicated to the optimal operation of the WDS which is articulated as minimization of the pumps' energy consumption while maintaining flow, pressure, and tank water levels at a minimum level, also known as pump scheduling problem (PSP). This problem is proved to be NP-hard (i.e. a difficult problem computationally). We therefore develop a hybrid methodology incorporating machine-learning techniques as well as optimization methods to address real-life and large-sized WDSs. Other main contributions of this research are (i) in addition to fixed-speed pumps, the variable-speed pumps are optimally controlled, (ii) and operational rules such as water allocation rules can also be explicitly considered in the methodology. This methodology is tested using a large dataset in which the results are found to be highly promising. This methodology has been coded as a user-friendly software composed of MS-Excel (as a user interface), MS-Access (a database), MATLAB (for machine-learning), GAMS (with CPLEX solver for solving optimization problem) and EPANET (to solve hydraulic models). (C) 2018 Elsevier Ltd. All rights reserved.
|
|
| 15. |
- Bagloee, S.A., et al.
(author)
-
Minimization of water pumps' electricity usage: a machine-learning approach
- 2017
-
Reports (other academic/artistic)abstract
- Due to pervasive deployment of electricity-propelled water-pumps, water distribution systems (WDSs) are energy-intensive technologies which are largely operated and controlled by engineers based on their judgments and discretions. Hence energy efficiency in the water sector is a serious concern. To this end, this study is dedicated to the optimal operation of the WDS which is articulated as minimization of the pumps’ energy consumption while maintaining flow, pressure, and tank water levels at a minimum level, also known as pump scheduling problem (PSP). This problem is proved to be of the most difficult problem (namely NP-hard). To this end, we develop a hybrid methodology consists of machine learning techniques as well as optimization methods, that is to address real life and large sized WDSs. Other main contributions of this research are (i) also, variable speed pumps can be modeled and optimally controlled, (ii) operational rules such as water allocation rules can also be explicitly considered in the methodology. This methodology is tested using a large sized dataset in which the results are found to be highly promising. This methodology has been coded as a user-friendly software composed of MS-Excel (as a user interface), MS-Access (a database), MATLAB (for machine learning), GAMS (with CPLEX solver for solving optimization problem) and EPANET (to solve hydraulic models).
|
|
| 16. |
- Bagloee, Saeed Asadi, et al.
(author)
-
Optimization for Roads' Construction: Selection, Prioritization, and Scheduling
- 2018
-
In: Computer-Aided Civil and Infrastructure Engineering. - : Wiley. - 1093-9687 .- 1467-8667. ; 33:10, s. 833-848
-
Journal article (peer-reviewed)abstract
- Computer-Aided Civil and Infrastructure Engineering Limited resources (budget, labor, machinery) have a significant toll on the roads' construction. The question of interest is: given variations of resources over a lengthy construction time, what would be the best construction scheduling plan, or how to optimize the Gantt chart while considering two highly challenging features (1) prerequisite conditions and (2) the interdependency of the benefit of the projects’ completions. We formulate it as a bilevel problem where the objective function is to minimize generalized costs and the lower level accounts for the drivers’ route choice. We employ a solution algorithm based on a supervised learning technique (a linear regression model of machine-learning) and an integer programming problem and it is applied to the datasets of Winnipeg and Chicago. The regression model was found to be a tight approximation which resulted in an efficient algorithm (the CPU time is almost a linear function of the number of iterations). Moreover, the proposed methodology can render promising results (at least locally optimal solutions). This article is the first to formulate the Gantt chart using linear binary constraints and optimize it tailored to real-life case studies.
|
|
| 17. |
- Bangalore, Pramod, 1983, et al.
(author)
-
An artificial neural network based condition monitoring method for wind turbines, with application to the monitoring of the gearbox
- 2017
-
In: Wind Energy. - : Wiley. - 1099-1824 .- 1095-4244. ; 20:8, s. 1421-1438
-
Journal article (peer-reviewed)abstract
- Major failures in wind turbines are expensive to repair and cause loss of revenue due to long downtime. Condition-based maintenance, which provides a possibility to reduce maintenance cost, has been made possible because of the successful application of various condition monitoring systems in wind turbines. New methods to improve the condition monitoring system are continuously being developed. Monitoring based on data stored in the supervisory control and data acquisition (SCADA) system in wind turbines has received attention recently. Artificial neural networks (ANNs) have proved to be a powerful tool for SCADA-based condition monitoring applications. This paper first gives an overview of the most important publications that discuss the application of ANN for condition monitoring in wind turbines. The knowledge from these publications is utilized and developed further with a focus on two areas: the data preprocessing and the data post-processing. Methods for filtering of data are presented, which ensure that the ANN models are trained on the data representing the true normal operating conditions of the wind turbine. A method to overcome the errors from the ANN models due to discontinuity in SCADA data is presented. Furthermore, a method utilizing the Mahalanobis distance is presented, which improves the anomaly detection by considering the correlation between ANN model errors and the operating condition. Finally, the proposed method is applied to case studies with failures in wind turbine gearboxes. The results of the application illustrate the advantages and limitations of the proposed method.
|
|
| 18. |
- Bangalore, Pramod, 1983, et al.
(author)
-
Analysis of SCADA data for early fault detection with application to the maintenance management of wind turbines
- 2016
-
In: CIGRE Session 46. - : CIGRE. ; , s. 1-10
-
Conference paper (peer-reviewed)abstract
- During the past decade wind turbines have proven to be a promising source of renewable power. Wind turbines are generally placed in remote locations and are subject to harsh environmental conditions throughout their lifetimes. Consequently, the failures in wind turbines are expensive to repair and cause loss of revenue due to long down times. Asset management in wind turbines can aid in assessing and improving the reliability and availability of wind turbines, thereby making them more competitive. Maintenance policies play an important role in asset management and different maintenance models have been developed for wind turbine applications. Typically, mathematical models for maintenance optimization provide either an age based or a condition based preventive maintenance schedule. Age based preventive maintenance schedules provide the owner with the possibility to financially plan for maintenance activities for the entire lifetime of the wind turbine by providing the expected number of replacements for each component. However, age based preventive maintenance schedule may not consume the operating life of the wind turbine components to the maximum. Condition based maintenance scheduling has the advantage of better utilizing the operating life of the components. This paper proposes a wind turbine maintenance management framework which utilizes operation and maintenance data from different sources to combine the benefits of age based and condition based maintenance scheduling. This paper also presents an artificial neural network (ANN) based condition monitoring method which utilizes data from supervisory control and data acquisition (SCADA) system to detect failures in wind turbine components and systems. The procedures to construct ANN models for condition monitoring application are outlined. In order to demonstrate the effectiveness of the ANN based condition monitoring method it is applied to case studies from real wind turbines. Furthermore, a mathematical model called preventive maintenance schedule with interval costs (PMSPIC) is discussed and its application to a case study within the maintenance management framework is presented. The case study demonstrates the advantage of combining both the age based and condition based maintenance scheduling methods.
|
|
| 19. |
- Bar-Gera, Hillel, et al.
(author)
-
Computational precision of traffic equilibria sensitivities in automatic network design and road pricing
- 2013
-
In: Transportation Research Part B: Methodological. - : Elsevier BV. - 0191-2615 .- 1879-2367. ; 57, s. 485-500
-
Journal article (peer-reviewed)abstract
- Recent studies demonstrate the importance of computational precision of user equilibrium traffic assignment solutions for scenario comparisons. When traffic assignment is hierarchically embedded in a model for network design and/or road pricing, not only the precision of the solution itself becomes more important, but also the precision of its derivatives with respect to the design parameters should be considered. The main purpose of this paper is to present a method for precise computations of equilibrium derivatives. Numerical experiments are used for two evaluations: (1) precision of computed equilibrium derivatives for a medium-size network (Anaheim); and (2) the impact of precise derivatives on capacity-expansion solution quality for a small network (Sioux Falls).
|
|
| 20. |
|
|
| 21. |
|
|
| 22. |
- Besnard, Francois, 1983, et al.
(author)
-
A stochastic model for opportunistic maintenance planning of offshore wind farms
- 2011
-
In: 2011 IEEE PES Trondheim PowerTech: The Power of Technology for a Sustainable Society, POWERTECH 2011; Trondheim; 19 June 2011 through 23 June 2011. - 9781424484195
-
Conference paper (peer-reviewed)abstract
- A sound maintenance planning is of crucial importance for wind power farms, and especially for offshore locations. This paper presents a stochastic optimization model for opportunistic service maintenance of offshore wind farms. The model takes advantage of 7 days wind production ensemble forecast and opportunities at corrective maintenance activities in order to perform the service maintenance tasks at the lowest cost. The model is based on a rolling horizon, i.e. the optimization is performed on a daily basis to update the maintenance planning based on the updated production and weather forecasts. An example based on real wind data is used to demonstrate the value of the proposed approach. In this example, it is shown that 32% of the cost for production losses and transportation could be saved. © 2011 IEEE.
|
|
| 23. |
- Besnard, Francois, et al.
(author)
-
An Optimization Framework for Opportunistic Maintenance of Offshore Wind Power System
- 2009
-
In: 2009 IEEE BUCHAREST POWERTECH, VOLS 1-5. - NEW YORK : IEEE. - 9781424422340 ; , s. 2970-2976
-
Conference paper (peer-reviewed)abstract
- A sound maintenance planning is of crucial importance for wind power farms, and especially for offshore locations. There is a large potential in cost savings by maintenance optimization to make the projects more cost-efficient. This paper presents an opportunistic maintenance optimization model for offshore wind power system. The model takes advantage of wind forecasts and corrective maintenance activities in order to perform preventive maintenance tasks at low costs. The approach is illustrated with an example to demonstrate the value of the optimization. In this example 43% of the cost to perform preventive maintenance could be saved using the proposed method.
|
|
| 24. |
- Connors, R., et al.
(author)
-
Sensitivity analysis of welfare, equity, and acceptability level of transport policies
- 2015
-
In: Springer Proceedings in Mathematics and Statistics. - Cham : Springer International Publishing. - 2194-1017 .- 2194-1009. - 9783319185668 - 9783319185675 ; 130, s. 39-65
-
Conference paper (peer-reviewed)abstract
- Transport planners face a major challenge to devise policies to meet multiple expectations and objectives. While we know that transport networks are complex, multi-modal, and spatially distributed systems, there is now a long history of mathematical tools which assist planners in understanding travel movements. However, the objectives that they are asked to achieve do not always admit such a quantification, and so there is a potential mismatch between seemingly qualitatively driven objectives and quantitatively expressed models of the transport system. In the present chapter we address this mismatch, by focusing on three objectives that we believe represent the typical interests of a planner. These are namely: is the policy economically justifiable (efficient), is it “fair” (equitable), and is it justifiable to a democratic society (acceptable)? We provide mathematical representations of these three objectives and link them to mathematical theory of transport networks, in which we may explore the sensitivity of travel behaviour (and hence the objectives) to various multi-modal transport policies. The detailed steps for representing the policy objectives and sensitivities in the network are set out, and the results of a case study reported in which road tolls, road capacities, and bus fares are the policy variables. Overall, the chapter sets out a systematic method for planners to choose between multi-modal policies based on these three objectives.
|
|
| 25. |
|
|
| 26. |
- Cromvik, Christoffer, 1980, et al.
(author)
-
On the robustness of global optima and stationary solutions to stochastic mathematical programs with equilibrium constraints, Part II: Applications
- 2010
-
In: Journal of Optimization Theory and Applications. - : Springer Science and Business Media LLC. - 0022-3239 .- 1573-2878. ; 144:3, s. 479-500
-
Journal article (peer-reviewed)abstract
- In a companion paper (Cromvik and Patriksson, Part I, J. Optim. Theory Appl., 2010), the mathematical modeling framework SMPEC was studied; in particular, global optima and stationary solutions to SMPECs were shown to be robust with respect to the underlying probability distribution under certain assumptions. Further, the framework and theory were elaborated to cover extensions of the upper-level objective: minimization of the conditional value-at-risk (CVaR) and treatment of the multiobjective case. In this paper, we consider two applications of these results: a classic traffic network design problem, where travel costs are uncertain, and the optimization of a treatment plan in intensity modulated radiation therapy, where the machine parameters and the position of the organs are uncertain. Owing to the generality of SMPEC, we can model these two very different applications within the same framework. Our findings illustrate the large potential in utilizing the SMPEC formalism for modeling and analysis purposes; in particular, information from scenarios in the lower-level problem may provide very useful additional insights into a particular application.
|
|
| 27. |
- Daneva (Mitradjieva), Maria, et al.
(author)
-
A Comparison of Feasible Direction Methods for the Stochastic Transportation Problem
- 2010
-
In: Computational optimization and applications. - : Springer Science and Business Media LLC. - 0926-6003 .- 1573-2894. ; 46:3, s. 451-466
-
Journal article (peer-reviewed)abstract
- The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.
|
|
| 28. |
- Daneva (Mitradjieva), Maria, et al.
(author)
-
A Sequential Linear Programming Algorithm with Multi-dimensional Search : Derivation and Convergence
- 2007
-
Journal article (other academic/artistic)abstract
- We present a sequential linear programming, SLP, algorithm in which the traditional line-search step is replaced by a multi-dimensional search. The algorithm is based on inner approximations of both the primal and dual spaces, which yields a method which in the primal space combines column and constraint generation. The algorithm does not use a merit function, and the linear programming subproblem of the algorithm differs from the one obtained in traditional methods of this type, in the respect that linearized constraints are taken into account only implicitly in a Lagrangiandual fashion. Convergence to a point that satisfies the Karush-Kuhn-Tucker conditions is established. We apply the new method to a selection of the Hoch-Schittkowski’s nonlinear test problems and report a preliminary computational study in a Matlab environment. Since the proposed algorithmcombines column and constraint generation, it should be advantageous with large numbers of variables and constraints.
|
|
| 29. |
|
|
| 30. |
- Fotedar, Sunney, 1989, et al.
(author)
-
Mathematical optimization of the tactical allocation of machining resources for an efficient capacity utilization in aerospace component manufacturing
- 2019
-
In: Proceedings of the 10th Aerospace Technology Congress. - : Linköping University Electronic Press. - 1650-3686 .- 1650-3740. - 9789175190068 ; , s. 183-188
-
Conference paper (peer-reviewed)abstract
- In the aerospace industry, with low volumes and many products, there is a critical need to efficiently use available manufacturing resources. Currently, at GKN Aerospace, resource allocation decisions that in many cases will last for several years are to some extent made with a short-term focus so as to minimize machining time, which results in a too high load on the most capable machines, and too low load on the less capable ones. This creates an imbalance in capacity utilization that leads to unnecessary queuing at some machines, resulting in long lead times and in an increase in tied-up capital. Tactical resource allocation on the medium to long-range planning horizon (six months to several years) aims to address this issue by allocating resources to meet the predicted future demand as effectively as possible, in order to ensure long range profitability. Our intent is to use mathematical optimization to find the best possible allocations.
|
|
| 31. |
- Fröidh, Oskar, et al.
(author)
-
Färdplan för ökad forskning och innovation inom underhåll av järnvägsfordon
- 2015
-
Reports (other academic/artistic)abstract
- KTH, Chalmers och Handelshögskolan vid Göteborgs universitet har av Trafikverket fått uppdraget att ta fram ett dokument om forskningen inom underhåll av järnvägsfordon. Det är föreliggande färdplan som ingår i Trafikverkets satsning Morgondagens depåer. Färdplanen ska ligga till grund för en strategi och förslag på utveckling för kostnadseffektivt fordonsunderhåll med de förutsättningar som råder i Sverige, med avreglering och många aktörer i branschen likväl som speciella klimatförutsättningar. Trafikverket har uppmärksammat att frågor om depåer och fordonsunderhåll inte alltid hanteras på ett bra sätt för att utveckla järnvägssystemet. Tidigare hade Banverket ett sektorsansvar men det avskaffades i och med att Trafikverket bildades. Det behövs dock ett övergripande systemansvar och incitament för att leda processen framåt mot en stabil utveckling genom forskning, utveckling och innovation i den fortsatta omreglering som sker av den svenska järnvägssektorn. Hur kan en effektiv samverkan mellan universitet, näringsliv och offentlig sektor utformas för att bidra till en säker och pålitlig tågtrafik i Sverige? En litteraturgenomgång har genomförts för att visa var den internationella forskningsfronten står. Det tycks dock som att det samlade greppet inom underhåll av järnvägsfordon inte är ett genomarbetat forskningsområde, utan det kan bli ett svenskt ”pionjärområde” där universitet, högskolor och institut i samarbete med branschen kan skapa forskningsresultat och kunskapsutveckling. Denna färdplan föreslår ett antal olika områden som skulle behöva ökad forskning för större kunskap och kompetens. Var ska depåer för person- respektive godsfordon mest effektivt lokaliseras, centralt eller perifert i jämförelse med trafiksystemet och respektive omlopp? Hur ska de utformas mest effektivt med tanke på fordonstyper, reservdelar och personalutnyttjande? Hur ska infrastrukturen till och internt i depåerna utformas för effektivt arbete? Detta ska ske i en avreglerad järnvägssektor med olika operatörer, vagnägare, depåägare samt underhållsleverantörer på olika långa kontrakt. Hur ska detta organiseras på ett stabilt sätt med långsiktig ekonomisk bärkraft för samtliga parter? Arbetet går att dela upp i avhjälpande och förebyggande underhåll; i depå eller mobilt, med säkerhets-, drifts- eller komfortrelaterat underhåll. På vilka olika sätt går det att utvärdera samt utveckla modeller för att prognostisera behovet av underhåll enligt ovan nämnda variabler? Målet är att ta fram vetenskapliga metoder för att effektivisera fordonsunderhåll för järnvägstrafiken på ett optimalt sätt. I färdplanen rekommenderas en strategi för fordonsunderhåll: Trafikverket ska verka för att efterfrågad funktion i det svenska järnvägssystemet uppnås, inkluderande kostnadseffektivt underhåll av både infrastruktur och fordon. Hög driftsäkerhet är attraktivt för resenärer och godskunder och har ett värde och motiverar ett samhällsekonomiskt synsätt på underhåll av järnvägsfordon. Tillståndsövervakning och relaterad prediktering ges en viktigare roll för förebyggande underhåll. Öka synergin mellan infrastruktur- och fordonsbaserad tillståndsövervakning, inte minst av den dynamiska samverkan mellan infrastruktur och fordon. Utred hur ”intelligensen” hos infrastruktur och fordon bäst fördelas och utvecklas för ett mera kostnadseffektivt underhåll av järnvägssystemet. Detta innefattar att man vet vad man skall mäta och att uppmätta storheter kan länkas till framtida nedbrytning av fordon och infrastruktur. Utred flödet och ”flaskhalsar” i dagens system av fordonsunderhåll (kritiska aspekter). Utveckla distinktionen av säkerhetsnödvändigt underhåll och komfortrelaterat underhåll. Verka för tydliga och rimliga ”spelregler” för aktörer inom fordonsunderhåll. Förbättra nätverket bland dessa aktörer, inte minst kring tekniska frågor. Skapa ytterligare incitament för effektivt fordonsunderhåll genom att se över kostnader och intäkter i intressentkedjan mellan de primära kunderna och de som kan åtgärda problemen. Lyft fram goda exempel (best practice) på väl fungerande fordonsunderhåll. Låt universitet och högskolor få en viktig och neutral roll i den kunskapsbaserade utvecklingen. Detta bör ske genom att skapa ett forsknings- utvecklings- och demonstrations (FUD)-program inom området underhåll för järnvägsfordon. I denna färdplan föreslås även ett antal olika forskningsprojekt och -områden som skulle kunna utvecklas i ett sammanhållet forskningsprogram.
|
|
| 32. |
- Fröidh, Oskar, et al.
(author)
-
Färdplan för ökad forskning och innovation inom underhåll av järnvägsfordon
- 2015
-
Reports (other academic/artistic)abstract
- KTH, Chalmers och Handelshögskolan vid Göteborgs universitet har av Trafikverket fått uppdraget att ta fram ett dokument om forskningen inom underhåll av järnvägsfordon. Det är föreliggande färdplan som ingår i Trafikverkets satsning Morgondagens depåer. Färdplanen ska ligga till grund för en strategi och förslag på utveckling för kostnadseffektivt fordonsunderhåll med de förutsättningar som råder i Sverige, med avreglering och många aktörer i branschen likväl som speciella klimatförutsättningar.Trafikverket har uppmärksammat att frågor om depåer och fordonsunderhåll inte alltid hanteras på ett bra sätt för att utveckla järnvägssystemet. Tidigare hade Banverket ett sektorsansvar men det avskaffades i och med att Trafikverket bildades. Det behövs dock ett övergripande systemansvar och incitament för att leda processen framåt mot en stabil utveckling genom forskning, utveckling och innovation i den fortsatta omreglering som sker av den svenska järnvägssektorn. Hur kan en effektiv samverkan mellan universitet, näringsliv och offentlig sektor utformas för att bidra till en säker och pålitlig tågtrafik i Sverige?En litteraturgenomgång har genomförts för att visa var den internationella forskningsfronten står. Det tycks dock som att det samlade greppet inom underhåll av järnvägsfordon inte är ett genomarbetat forskningsområde, utan det kan bli ett svenskt ”pionjärområde” där universitet, högskolor och institut i samarbete med branschen kan skapa forskningsresultat och kunskapsutveckling.Denna färdplan föreslår ett antal olika områden som skulle behöva ökad forskning för större kunskap och kompetens. Var ska depåer för person- respektive godsfordon mest effektivt lokaliseras, centralt eller perifert i jämförelse med trafiksystemet och respektive omlopp? Hur ska de utformas mest effektivt med tanke på fordonstyper, reservdelar och personalutnyttjande? Hur ska infrastrukturen till och internt i depåerna utformas för effektivt arbete? Detta ska ske i en avreglerad järnvägssektor med olika operatörer, vagnägare, depåägare samt underhållsleverantörer på olika långa kontrakt. Hur ska detta organiseras på ett stabilt sätt med långsiktig ekonomisk bärkraft för samtliga parter? Arbetet går att dela upp i avhjälpande och förebyggande underhåll; i depå eller mobilt, med säkerhets-, drifts- eller komfortrelaterat underhåll. På vilka olika sätt går det att utvärdera samt utveckla modeller för att prognostisera behovet av underhåll enligt ovan nämnda variabler? Målet är att ta fram vetenskapliga metoder för att effektivisera fordonsunderhåll för järnvägstrafiken på ett optimalt sätt.I färdplanen rekommenderas en strategi för fordonsunderhåll:Trafikverket ska verka för att efterfrågad funktion i det svenska järnvägssystemet uppnås, inkluderande kostnadseffektivt underhåll av både infrastruktur och fordon.Hög driftsäkerhet är attraktivt för resenärer och godskunder och har ett värde och motiverar ett samhällsekonomiskt synsätt på underhåll av järnvägsfordon.Tillståndsövervakning och relaterad prediktering ges en viktigare roll för förebyggande underhåll.Öka synergin mellan infrastruktur- och fordonsbaserad tillståndsövervakning, inte minst av den dynamiska samverkan mellan infrastruktur och fordon.Utred hur ”intelligensen” hos infrastruktur och fordon bäst fördelas och utvecklas för ett mera kostnadseffektivt underhåll av järnvägssystemet. Detta innefattar att man vet vad man skall mäta och att uppmätta storheter kan länkas till framtida nedbrytning av fordon och infrastruktur.Utred flödet och ”flaskhalsar” i dagens system av fordonsunderhåll (kritiska aspekter).Utveckla distinktionen av säkerhetsnödvändigt underhåll och komfortrelaterat underhåll.Verka för tydliga och rimliga ”spelregler” för aktörer inom fordonsunderhåll.Förbättra nätverket bland dessa aktörer, inte minst kring tekniska frågor.Skapa ytterligare incitament för effektivt fordonsunderhåll genom att se över kostnader och intäkter i intressentkedjan mellan de primära kunderna och de som kan åtgärda problemen.Lyft fram goda exempel (best practice) på väl fungerande fordonsunderhåll.Låt universitet och högskolor få en viktig och neutral roll i den kunskapsbaserade utvecklingen.Detta bör ske genom att skapa ett forsknings- utvecklings- och demonstrations (FUD)-program inom området underhåll för järnvägsfordon. I denna färdplan föreslås även ett antal olika forskningsprojekt och -områden som skulle kunna utvecklas i ett sammanhållet forskningsprogram.
|
|
| 33. |
- Garcia, Ricardo, et al.
(author)
-
Network design applications of the class of column generation/simplicial decomposition algorithms in convex differentiable optimization
- 2001
-
In: Investigacion Operacional. ; 22:2, s. 91-99
-
Journal article (peer-reviewed)abstract
- A new class of column generation/simplicial decomposition method for nonlinear convex and differentiable programming is presented. The new algorithm class builds on the intuitively appealing idea that nonlinear column generation problems may be advantageous computationally. Different applications of this methodology are presented, with special attention to the unicommodity and multicommodity network flow problems, which are obtained when some decomposition methods are applied to network design problems.
|
|
| 34. |
- Garcia-Rodenas, R., et al.
(author)
-
Column generation algorithms for nonlinear optimization, II: Numerical investigations
- 2011
-
In: Computers & Operations Research. - : Elsevier BV. - 0305-0548. ; 38:3, s. 591-604
-
Journal article (peer-reviewed)abstract
- Garcia et al. [1] present a class of column generation (CG) algorithms for nonlinear programs. Its main motivation from a theoretical viewpoint is that under some circumstances, finite convergence can be achieved, in much the same way as for the classic simplicial decomposition method; the main practical motivation is that within the class there are certain nonlinear column generation problems that can accelerate the convergence of a solution approach which generates a sequence of feasible points. This algorithm can, for example, accelerate simplicial decomposition schemes by making the subproblems nonlinear. This paper complements the theoretical study on the asymptotic and finite convergence of these methods given in [1] with an experimental study focused on their computational efficiency. Three types of numerical experiments are conducted. The first group of test problems has been designed to study the parameters involved in these methods. The second group has been designed to investigate the role and the computation of the prolongation of the generated columns to the relative boundary. The last one has been designed to carry out a more complete investigation of the difference in computational efficiency between linear and nonlinear column generation approaches. In order to carry out this investigation, we consider two types of test problems: the first one is the nonlinear, capacitated single-commodity network flow problem of which several large-scale instances with varied degrees of nonlinearity and total capacity are constructed and investigated, and the second one is a combined traffic assignment model.
|
|
| 35. |
- Gustavsson, Emil, 1987, et al.
(author)
-
Preventive maintenance scheduling of multi-component systems with deterioration costs
- 2012
-
Other publication (other academic/artistic)abstract
- We introduce the preventive maintenance scheduling problem with interval costs (PMSPIC), which is to schedule preventive maintenance of components of a system over a finite discretized time horizon, given a common set-up cost and component costs dependent on the lengths of the maintenance intervals. We present a 0-1 integer linear programming (0-1 ILP) model for the PMSPIC which was originally presented by Joneja (1990) to model the joint replenishment problem. We show that most of the integrality constraints can be relaxed and that the linear inequality constraints define facets of the convex hull of the feasible set. We present three applications demonstrating that the PMSPIC can be used to model several types of maintenance problems with deterioration costs. The first considers rail grinding. If the interval between the grinding occasions increases, then the sizes of the rail cracks increase, which implies that more grinding passes must be performed, generating a higher maintenance cost. We presume a deterministic model for crack growth and optimize the scheduling of the rail grinding on a set of track sections. Our second application concerns two approaches for the scheduling of component replacements in aircraft engines. In the first approach a bi-objective problem, simultaneously minimizing the cost for the scheduled preventive maintenance and the probability of unexpected stops, is formulated. The second approach considers the minimization of the sum of costs of preventive and expected corrective maintenance, without rescheduling. We also demonstrate that if rescheduling is allowed, then the 0-1 ILP model can be used as a policy by re-optimizing the schedule at a component failure, thus utilizing the opportunity for preventive maintenance. We evaluate the use of such a strategy in a simulation of the engine. The third approach considers components’ replacement in wind mills in a wind farm, extending the PMSPIC to consider several systems with a joint set-up cost. As for the aircraft engine application, we use the 0-1 ILP model as a policy for deciding upon replacement decisions allowing for rescheduling, and evaluate it by simulating the joint system. In each of the three applications, the use of the 0-1 ILP model is compared with age or constantinterval policies, resulting in a reduction of maintenance costs by up to 15% compared with the respective best simple policy.
|
|
| 36. |
- Gustavsson, Emil, 1987, et al.
(author)
-
Preventive maintenance scheduling of multi-component systems with interval costs
- 2014
-
In: Computers & industrial engineering. - : Elsevier BV. - 0360-8352. ; 76, s. 390-400
-
Journal article (peer-reviewed)abstract
- We introduce the preventive maintenance scheduling problem with interval costs (PMSPIC), which is to schedule preventive maintenance (PM) of the components of a system over a finite and discretized time horizon, given a common set-up cost and component costs dependent on the lengths of the maintenance intervals. We present a 0–1 integer linear programming (0–1 ILP) model for the PMSPIC; the model is identical to that presented by Joneja (1990) for the joint replenishment problem within inventory management. We study this model from a polyhedral and exact solutions’ point of view, as opposed to previously studied heuristics (e.g. Boctor, Laporte, & Renaud, 2004; Federgruen & Tzur, 1994; Levi, Roundy, & Shmoys, 2006; Joneja, 1990).We show that most of the integrality constraints can be relaxed and that the linear inequality constraints define facets of the convex hull of the feasible set. We further relate the PMSPIC to the opportunistic replacement problem, for which detailed polyhedral studies were performed by Almgren et al. (2012a). The PMSPIC can be used as a building block to model several types of maintenance planning problems possessing deterioration costs. By a careful modeling of these costs, a polyhedrally sound 0–1 ILP model is used to find optimal solutions to realistic-sized multi-component maintenance planning problems. The PMSPIC is thus easily extended by side constraints or to multiple tiers, which is demonstrated through three applications; these are chosen to span several levels of unmodeled randomness requiring fundamentally different maintenance policies, which are all handled by variations of our basic model. Our first application considers rail grinding. Rail cracks increase with increasing intervals between grinding occasions, implying that more grinding passes must be performed—thus generating higher costs. We optimize the grinding schedule for a set of track sections presuming a deterministic model for crack growth; hence, no corrective maintenance (CM) will occur between the grinding occasions scheduled. The second application concerns two approaches for scheduling component replacements in aircraft engines. The first approach is bi-objective, simultaneously minimizing the cost for the scheduled PM and the probability of unexpected stops. In the second approach the sum of costs for PM and expected CM—without rescheduling—is minimized. When rescheduling is allowed, the 0–1 ILP model is used as a policy by re-optimizing the schedule at a component failure, which then constitutes an opportunity for PM. The policy manages the trade-off between costs for PM and unplanned CM and is evaluated in a simulation of the engine. The third application considers components’ replacement in wind mills in a wind farm, extending the PMSPIC to comprise multiple tiers with joint set-up costs. Due to the large number of components unexpected stops occur frequently, thus calling for a dynamic rescheduling, which is evaluated through a simulation of the system. In each of the three applications, the use of the 0-1 ILP model is compared with age or constant-interval policies; the maintenance costs are reduced by up to 16% as compared with the respective best simple policy. The results are strongest for the first two applications, possessing low levels of unmodeled randomness.
|
|
| 37. |
- Gustavsson, Emil, 1987, et al.
(author)
-
Primal convergence from dual subgradient methods for convex optimization
- 2012
-
Other publication (other academic/artistic)abstract
- When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favourably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which is shown to converge to an optimal primal solution when the convexity weights are appropriately chosen. We generalize previous convergence results from linear to convex optimization and present a new set of rules for constructing the convexity weights that define the ergodic sequence of primal solutions. In contrast to previously proposed rules, they exploit more information from later subproblem solutions than from earlier ones. We evaluate the proposed rules on a set of nonlinear multicommodity flow problems and demonstrate that they clearly outperform the ones previously proposed.
|
|
| 38. |
- Gustavsson, Emil, 1987, et al.
(author)
-
Primal convergence from dual subgradient methods for convex optimization
- 2015
-
In: Mathematical Programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 150:2, s. 365-390
-
Journal article (peer-reviewed)abstract
- When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which is shown to converge to an optimal primal solution when the convexity weights are appropriately chosen. We generalize previous convergence results from linear to convex optimization and present a new set of rules for constructing the convexity weights that define the ergodic sequence of primal solutions. In contrast to previously proposed rules, they exploit more information from later subproblem solutions than from earlier ones. We evaluate the proposed rules on a set of nonlinear multicommodity flow problems and demonstrate that they clearly outperform the ones previously proposed.
|
|
| 39. |
|
|
| 40. |
- Jakobsson, Stefan, 1970, et al.
(author)
-
A method for simulation based optimization using radial basis functions
- 2010
-
In: Optimization & Engineering. - : Springer Science and Business Media LLC. - 1573-2924 .- 1389-4420. ; 11:4, s. 501-532
-
Journal article (peer-reviewed)abstract
- We propose an algorithm for the global optimization of expensive and noisy black box functions using a surrogate model based on radial basis functions (RBFs). A method for RBF-based approximation is introduced in order to handle noise. New points are selected to minimize the total model uncertainty weighted against the surrogate function value. The algorithm is extended to multiple objective functions by instead weighting against the distance to the surrogate Pareto front; it therefore constitutes the first algorithm for expensive, noisy and multiobjective problems in the literature. Numerical results on analytical test functions show promise in comparison to other (commercial) algorithms, as well as results from a simulation based optimization problem.
|
|
| 41. |
- Jakobsson, S, et al.
(author)
-
Combustion engine optimization: A multiobjective approach
- 2010
-
In: Optimization & Engineering. - : Springer Science and Business Media LLC. - 1389-4420 .- 1573-2924. ; 11:4, s. 533-554
-
Journal article (peer-reviewed)abstract
- To simulate the physical and chemical processes inside combustion engines is possible by appropriate software and high performance computers. For combustion engines a good design is such that it combines a low fuel consumption with low emissions of soot and nitrogen oxides. These are however partly conflicting requirements. In this paper we approach this problem in a multi-criteria setting which has the advantage that it is possible to estimate the trade off between the different objectives and the decision of the optimal solution is postponed until all possibilities and limitations are known. The optimization algorithm is based on surrogate models and is here applied to optimize the design of a diesel combustion engine.
|
|
| 42. |
|
|
| 43. |
- Kans, Mirka, 1971-, et al.
(author)
-
Data Driven Maintenance : A Promising Way of Action for Future Industrial Services Management
- 2022
-
In: International Congress and Workshop on Industrial AI 2021. IAI 2021. - Cham : Springer. - 9783030936389 - 9783030936396 ; , s. 212-223, s. 212-223
-
Conference paper (peer-reviewed)abstract
- Maintenance and services of products as well as processes are pivotal for achieving high availability and avoiding catastrophic and costly failures. At the same time, maintenance is routinely performed more frequently than necessary, replacing possibly functional components, which has negative economic impact on the maintenance. New processes and products need to fulfil increased environmental demands, while customers put increasing demands on customization and coordination. Hence, improved maintenance processes possess very high potentials, economically as well as environmentally. The shifting demands on product development and production processes have led to the emergency of new digital solutions as well as new business models, such as integrated product-service offerings. Still, the general maintenance problem of how to perform the right service at the right time, taking available information and given limitations is valid.The project Future Industrial Services Management (FUSE) project was a step in a long-term effort for catalysing the evolution of maintenance and production in the current digital era. In this paper, several aspects of the general maintenance problem are discussed from a data driven perspective, spanning from technology solutions and organizational requirements to new business opportunities and how to create optimal maintenance plans. One of the main results of the project, in the form of a simulation tool for strategy selection, is also described.
|
|
| 44. |
- Laksman, Efraim, 1983, et al.
(author)
-
The stochastic opportunistic replacement problem, part III: improved bounding procedures
- 2020
-
In: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 292:2, s. 711-733
-
Journal article (peer-reviewed)abstract
- We consider the problem to find a schedule for component replacement in a multi-component system, whose components possess stochastic lives and economic dependencies, such that the expected costs for maintenance during a pre-defined time period are minimized. The problem was considered in Patriksson et al. (Ann Oper Res 224:51–75, 2015), in which a two-stage approximation of the problem was optimized through decomposition (denoted the optimization policy). The current paper improves the effectiveness of the decomposition approach by establishing a tighter bound on the value of the recourse function (i.e., the second stage in the approximation). A general lower bound on the expected maintenance cost is also established. Numerical experiments with 100 simulation scenarios for each of four test instances show that the tighter bound yields a decomposition generating fewer optimality cuts. They also illustrate the quality of the lower bound. Contrary to results presented earlier, an age-based policy performs on par with the optimization policy, although most simple policies perform worse than the optimization policy.
|
|
| 45. |
- Larsson, Torbjörn, 1957-, et al.
(author)
-
A column generation procedure for the side constrained traffic equilibrium problem
- 2004
-
In: Transportation Research Part B. - : Elsevier. - 0191-2615 .- 1879-2367. ; 38:1, s. 17-38
-
Journal article (peer-reviewed)abstract
- We present a column generation procedure for the side constrained traffic equilibrium problem. A dual stabilization scheme is introduced to improve the computational performance. Computational experiments for the case of linear side constraints are presented. The test problems are well known traffic equilibrium instances where side constraints of link flow capacity type and general linear side constraints are added. The computational results are promising especially for instances with a relatively small number of side constraints.
|
|
| 46. |
- Larsson, Torbjörn, et al.
(author)
-
A generic column generation principle: derivation and convergence analysis
- 2015
-
In: Operational Research. - : Springer Science and Business Media LLC. - 1109-2858 .- 1866-1505. ; 15:2, s. 163-198
-
Journal article (peer-reviewed)abstract
- Given a non-empty, compact and convex set, and an a priori definedcondition which each element either satisfies or not, we want to find an elementbelonging to the former category. This is a fundamental problem of mathematicalprogramming which encompasses nonlinear programs, variational inequalities,saddle-point problems. We present a conceptual column generation scheme, whichalternates between solving a restriction of the original problem and a columngeneration phase which is used to augment the restricted problems. We establishgeneral applicability of the conceptual method, as well as to the three problemclasses mentioned. We also establish a version of the conceptual method in whichthe restricted and column generation problems are allowed to be solvedproximately, and of a version allowing for the dropping of columns. We showsome solution methods (e.g., Dantzig–Wolfe decomposition and simplicialcomposition) are special instances, and present new convergent column generationmethods in nonlinear programming, such as a sequential linear programming typemethod. Along the way, we also relate our quite general scheme in nonlinearprogramming presented in this paper with several other classic, and more recent,iterative methods in nonlinear optimization.
|
|
| 47. |
|
|
| 48. |
- Larsson, Torbjörn, et al.
(author)
-
A partial linearization method for the traffic assignment problem
- 1993
-
In: Optimization. - : Informa UK Limited. - 0233-1934 .- 1029-4945. ; 28:1, s. 47-61
-
Journal article (peer-reviewed)abstract
- This paper presents a new solution technique for the traffic assignment problem. The approach is based on an iteratively improved nonlinear and separable approximation of the originally nonseparable objective function, and resembles the Frank-Wolfe algorithm in the sense that the subproblem separates with respect to commodities. Since the single-commodity subproblems are strictly convex, the new algorithm will not suffer from the poor convergence behaviour of the Frank-Wolfe algorithm, which is a consequence of the extreme solutions of its linear subproblems. The solution method is outlined along with convergence results, and a dual approach to the solution of the strictly convex subproblems is described. The performance of the algorithm is illustrated with two numerical examples
|
|
| 49. |
- Larsson, Torbjörn, et al.
(author)
-
Convergent Lagrangian heuristics for nonlinear minimum cost network flows
- 2008
-
In: European Journal of Operational Research. - : Elsevier BV. - 0377-2217 .- 1872-6860. ; 189:2, s. 324-346
-
Journal article (peer-reviewed)abstract
- We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector, this is referred to as "early primal recovery". It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme, such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable, in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes. © 2007 Elsevier B.V. All rights reserved.
|
|
| 50. |
- Larsson, Torbjörn, et al.
(author)
-
Ergodic convergence in subgradient optimization - with application to simplicial decomposition of convex programs
- 2012
-
In: Contemporary Mathematics. - Providence, Rhode Island : American Mathematical Society. - 0271-4132 .- 1098-3627. ; 568, s. 159-186
-
Journal article (peer-reviewed)abstract
- When non-smooth, convex minimization problems are solved by subgradient optimization methods, the subgradients used will in general not accumulate to subgradients that verify the optimality of a solution obtained in the limit. It is therefore not a straightforward task to monitor the progress of subgradient methods in terms of the approximate fulfilment of optimality conditions. Further, certain supplementary information, such as convergent estimates of Lagrange multipliers and convergent lower bounds on the optimal objective value, is not directly available in subgradient schemes. As a means of overcoming these weaknesses in subgradient methods, we introduced in LPS96b, LPS96c, and LPS98 the computation of an ergodic (averaged) sequence of subgradients. Specifically, we considered a non-smooth, convex program solved by a conditional subgradient optimization scheme with divergent series step lengths, and showed that the elements of the ergodic sequence of subgradients in the limit fulfil the optimality conditions at the optimal solution, to which the sequence of iterates converges. This result has three important implications. The first is the finite identification of active constraints at the solution obtained in the limit. The second is the establishment of the convergence of ergodic sequences of Lagrange multipliers; this result enables sensitivity analyses for solutions obtained by subgradient methods. The third is the convergence of a lower bounding procedure based on an ergodic sequence of affine underestimates of the objective function; this procedure also provides a proper termination criterion for subgradient optimization methods. This article contributes first an overview of results and applications found in LPS96b, LPS96c, and LPS98 pertaining to the generation of ergodic sequences of subgradients generated within a subgradient scheme. It then presents an application of these results to that of the first instance of a simplicial decomposition algorithm for convex and non-smooth optimization problems.
|
|
