| 1. |
- Strömberg, Ann-Brith, 1961, et al.
(författare)
-
Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods
- 2020
-
Ingår i: Numerical Nonsmooth Optimization: State of the Art Algorithms. - Cham : Springer International Publishing. ; , s. 499-547, s. 499-547
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- This chapter presents several solution methodologies for mixed-integer linear optimization, stated as mixed-binary optimization problems, by means of Lagrangian duals, subgradient optimization, cutting-planes, and recovery of primal solutions. It covers Lagrangian duality theory for mixed-binary linear optimization, a problem framework for which ultimate success—in most cases—is hard to accomplish, since strong duality cannot be inferred. First, a simple conditional subgradient optimization method for solving the dual problem is presented. Then, we show how ergodic sequences of Lagrangian subproblem solutions can be computed and used to recover mixed-binary primal solutions. We establish that the ergodic sequences accumulate at solutions to a convexified version of the original mixed-binary optimization problem. We also present a cutting-plane approach to the Lagrangian dual, which amounts to solving the convexified problem by Dantzig–Wolfe decomposition, as well as a two-phase method that benefits from the advantages of both subgradient optimization and Dantzig–Wolfe decomposition. Finally, we describe how the Lagrangian dual approach can be used to find near optimal solutions to mixed-binary optimization problems by utilizing the ergodic sequences in a Lagrangian heuristic, to construct a core problem, as well as to guide the branching in a branch-and-bound method. The chapter is concluded with a section comprising notes, references, historical downturns, and reading tips.
|
|
| 2. |
- Laksman, Efraim, 1983, et al.
(författare)
-
The stochastic opportunistic replacement problem, part III: improved bounding procedures
- 2020
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 292:2, s. 711-733
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 3. |
- Fotedar, Sunney, 1989, et al.
(författare)
-
Mathematical optimization of the tactical allocation of machining resources for an efficient capacity utilization in aerospace component manufacturing
- 2019
-
Ingår i: Proceedings of the 10th Aerospace Technology Congress. - : Linköping University Electronic Press. - 1650-3686 .- 1650-3740. - 9789175190068 ; , s. 183-188
-
Konferensbidrag (refereegranskat)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.
|
|
| 4. |
- Thörnblad, Karin, 1971, et al.
(författare)
-
Scheduling optimization of a real flexible job shop including fixture availability and preventive maintenance
- 2015
-
Ingår i: European Journal of Industrial Engineering. - 1751-5254 .- 1751-5262. ; 9:1, s. 126-145
-
Tidskriftsartikel (refereegranskat)abstract
- The multitask cell at GKN Aerospace Sweden is a flexible job shop containing ten resources aimed at being flexible with regard to product mix and processing types. We present a time-indexed formulation of the problem of optimally scheduling the planned jobs on the resources, also considering a limited availability of fixtures as well as required preventive maintenance activities. The objective is to minimize a weighted sum of the completion times and tardiness for the jobs, where the tardiness weight for a given job is a non-increasing function of its due date. We propose a fast iterative approach to finding a suitable value of the length of the time horizon that needs to be set for the time-indexed formulation and which considerably influences the computation time. Computational results show that the method developed is able to produce optimal, or near-optimal, schedules for real data instances within an acceptable practical time frame.
|
|
| 5. |
- Thörnblad, Karin, 1971, et al.
(författare)
-
Scheduling optimization of a real flexible job shop including side constraints regarding maintenance, fixtures, and night shifts
- 2013
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We present a generic iterative scheduling procedure for the scheduling of a real flexible job shop, the so-called multitask cell at GKN Aerospace Engine Systems in Sweden. A time-indexed formulation of the problem is presented including side constraints regarding preventive maintenance, fixture availability, and unmanned night shifts. This paper continues the work in [35], with an improvement of the iterative solution procedure and the inclusion of constraints regarding night shifts during which only unmanned processing is allowed. The resulting schedules are compared with schedules constructed using two priority dispatching rules. Computational results show that the gain of including the night shifts constraints is significant and that the methodology developed is able to produce near-optimal schedules for industrial data instances for the coming shift within an acceptable practical time frame.
|
|
| 6. |
- Bagloee, Saeed Asadi, et al.
(författare)
-
A hybrid machine-learning and optimization method to solve bi-level problems
- 2018
-
Ingår i: Expert Systems with Applications. - : Elsevier BV. - 0957-4174. ; 95, s. 142-152
-
Tidskriftsartikel (refereegranskat)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).
|
|
| 7. |
- Patriksson, Michael, 1964
(författare)
-
On the applicability and solution of bilevel optimization models in transportation science: A study on the existence, stability and computation of optimal solutions to stochastic mathematical programs with equilibrium constraints
- 2008
-
Ingår i: Transportation Research Part B. - : Elsevier BV. - 0191-2615. ; 42:10, s. 843-860
-
Tidskriftsartikel (refereegranskat)abstract
- Bilevel optimization models, and more generally MPEC (mathematical program with equilibrium constraints) models, constitute important modelling tools in transportation science and network games, as they place the classic ``what-if'' analysis in a proper mathematical framework. The MPEC model is also becoming a standard for the computation of optimal design solutions, where ``design'' may include either or both of network infrastructure investments and various types of tolls. At the same time, it does normally not sufficiently well take into account possible uncertainties and/or perturbations in problem data (travel costs and demands), and thus may not a priori guarantee robust designs under varying conditions. We consider natural stochastic extensions to a class of MPEC traffic models which explicitly incorporate data uncertainty. In stochastic programming terminology, we consider ``here-and-now'' models where decisions on the design must be made before observing the uncertain parameter values and the responses of the network users, and the design is chosen to minimize the expectation of the upper-level objective function. Such a model could, for example, be used to derive a fixed link pricing scheme that provides the best revenue for a given network over a given time period, where the varying traffic conditions are described by distributions of parameters in the link travel time and OD demand functions. For a general such SMPEC network model we establish not only the existence of optimal solutions, but in particular their stability to perturbations in the probability distribution. We also provide convergence results for general algorithmic schemes based on the penalization of the equilibrium conditions or possible joint upper-level constraints, as well as for algorithms based on the discretization of the probability distribution, the latter enabling the utilization of standard MPEC algorithms. Especially the latter part utilizes relations between the traffic application of SMPEC and stochastic structural topology optimization problems.
|
|
| 8. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The stochastic opportunistic replacement problem, part I: models incorporating individual component lives
- 2015
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 224:1, s. 25-50
-
Tidskriftsartikel (refereegranskat)abstract
- We consider an extension of the opportunistic replacement problem, which has been studied by Dickman et al. (The Journal of the Operational Research Society of India, 28:165–175, 1991), Andréasson (Optimization of opportunistic replacement activities in deterministic and stochastic multi-component systems, Licentiate thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2004), and Almgren et al. (The opportunistic replacement problem: analysis and case studies, Preprint, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2011), that allows the individuals of the same component to have non-identical lives. Formulating and solving this problem constitute a first step towards solving the opportunistic replacement problem with uncertain component lives. We show that the problem is NP-hard even with time independent costs, and present two 0–1 integer programming models for the problem. We show that in model I the integrality requirement on a majority of the variables can be relaxed; this is in contrast to model II and the model from Andréasson (Optimization of opportunistic replacement activities in deterministic and stochastic multi-component systems, Licentiate thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2004). We remove all superfluous variables and constraints in model I and show that the remaining constraints are facet inducing. We also utilize a linear transformation of model I to obtain a stronger version of model II, i.e., model II+, which inherits the polyhedral properties of model I. Numerical experiments show that the solution time of model I is significantly lower than those of both model II and Andréasson’s model. It is also slightly lower than the solution time of model II+.
|
|
| 9. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The stochastic opportunistic replacement problem, part II: a two-stage solution approach
- 2015
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 224:1, s. 51-75
-
Tidskriftsartikel (refereegranskat)abstract
- In Almgren et al. (The opportunistic replacement problem: analysis and case studies, preprint, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2011) we studied the opportunistic replacement problem, which is a multi-component maintenance scheduling problem with deterministic component lives. The assumption of deterministic lives is a substantial simplification, but valid in applications where critical components are assigned a technical life after which replacement is enforced. Here, we study the stochastic opportunistic replacement problem, which is a more general setting in which component lives are allowed to be stochastic. We consider a stochastic programming approach for the minimization of the expected cost over the remaining planning horizon. Further, we present a means to compute lower bounds on the recourse function. The lower bounds are used in the construction of a decomposition method which extends the integer L-shaped decomposition method to incorporate stronger optimality cuts. In order to obtain a computationally tractable model, a two-stage sample average approximation scheme is utilized. Numerical experiments on problem instances from the wind power and aviation industry as well as on two test instances are performed. The results show that the decomposition method is faster than solving the deterministic equivalent on all four instances considered. Furthermore, the numerical experiments show that decisions based on the stochastic programming approach compared with simpler maintenance policies yield maintenance decisions with a significantly lower expected total maintenance cost on two out of the four instances tested, and an equivalent maintenance cost compared to the best policy on the remaining two instances.
|
|
| 10. |
- Connors, R., et al.
(författare)
-
Sensitivity analysis of welfare, equity, and acceptability level of transport policies
- 2015
-
Ingår i: Springer Proceedings in Mathematics and Statistics. - Cham : Springer International Publishing. - 2194-1017 .- 2194-1009. - 9783319185668 - 9783319185675 ; 130, s. 39-65
-
Konferensbidrag (refereegranskat)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.
|
|
