417 research outputs found
Merit Functions and Descent Algorithms for a Class of Variational Inequality Problems
No full text. We consider a variational inequality problem, where the cost mapping is the sum of a single-valued mapping and the subdifferential mapping of a convex function. For this problem we introduce a new class of equivalent optimization formulations; based on them, we also provide the first convergence analysis of descent algorithms for the problem. The optimization formulations constitute generalizations of those presented by Auchmuty [Auc89], and the descent algorithms are likewise generalizations of those of Fukushima [Fuk92], Larsson and Patriksson [LaP94] and several others, for variational inequality problems with single-valued cost mappings. Key Words. Variational Inequality Problems, Merit Functions, Fenchel's Inequality, Cost Approximation, Descent Algorithms Mathematics Subject Classification 1991. Primary: 49J40, 49M05; Secondary: 90C30, 90C33 1 Introduction Let X be a nonempty, closed and convex subset of ! n , F : X 7! ! n a continuous mapping on X , and u : ! n 7! ! ..
Algorithms for the continuous nonlinear resource allocation problem - New implementations and numerical studies
No full textPatriksson (2008) provided a then up-to-date survey on the continuous, separable, differentiable and convex resource allocation problem with a single resource constraint. Since the publication of that paper the interest in the problem has grown: several new applications have arisen where the problem at hand constitutes a subproblem, and several new algorithms have been developed for its efficient solution. This paper therefore serves three purposes. First, it provides an up-to-date extension of the survey of the literature of the field, complementing the survey in Patriksson (2008) with more then 20 books and articles. Second, it contributes improvements of some of these algorithms, in particular with an improvement of the pegging (that is, variable fixing) process in the relaxation algorithm, and an improved means to evaluate subsolutions. Third, it numerically evaluates several relaxation (primal) and breakpoint (dual) algorithms, incorporating a variety of pegging strategies, as well as a quasi-Newton method. Our conclusion is that our modification of the relaxation algorithm performs the best. At least for problem sizes up to 30 million variables the practical time complexity for the breakpoint and relaxation algorithms is linear
Cost Approximation Algorithms With Nonmonotone Line Searches for a General Class of Nonlinear Programs
No full text. When solving ill-conditioned nonlinear programs by descent algorithms, the descent requirement may induce the step lengths to become very small, thus resulting in very poor performances. Recently, suggestions have been made to circumvent this problem, among which is a class of approaches in which the objective value may be allowed to increase temporarily. Grippo et al. [GLL91] introduce nonmonotone line searches in the class of deflected gradient methods in unconstrained differentiable optimization; this technique allows for longer steps (typically of unit length) to be taken, and is successfully applied to some ill-conditioned problems. This paper extends their nonmonotone approach and convergence results to the large class of cost approximation algorithms of Patriksson [Pat93b], and to optimization problems with both convex constraints and nondifferentiable objective functions. Key Words. Nondifferentiable optimization, cost approximation, nonmonotone algorithms Abbreviated Title..
On the robustness of global optima and stationary solutions to stochastic mathematical programs with equilibrium constraints, Part II: Applications
No full textIn 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
Stochastic Assignment with Gammit Path Choice Models
No full textTraffic assignment models simulate transportation systems, where flows resulting from user choice behaviour are affected by transportation costs, and costs may be affected by flows due to congestion. Several path choice behaviour models can be specified through random utility theory. Probabilistic path choice models, where perceived path costs are modelled as random variables, lead to stochastic assignment. In this paper, reasonable modelling requirements are proposed to assure a realistic simulation of path choice behaviour through probabilistic choice models. Then, additive Gammit path choice models based on Gamma distribution are introduced and deeply analysed. These models satisfy all the proposed modelling requirements, and can be effectively embedded within existing models and algorithms for stochastic assignment
Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design
No full textWe provide a sensitivity analysis of separable traffic equilibrium models with travel cost and demand parameters. We establish that while equilibrium link flows may not always be directionally differentiable (even when the link travel costs are strictly increasing), travel demands and link costs are; this improves the general results of Patriksson [Patriksson, M., 2004. Sensitivity analysis of traffic equilibria. Transportation Science 37, 258-281]. The new results contradict common belief that equilibrium cost and demand sensitivities hinge on that of equilibrium flows. The paper by Tobin and Friesz [Tobin, R.L., Friesz, T.L., 1988. Sensitivity analysis for equilibrium network flow. Transportation Science 22, 242-250] brought the classic non-linear programming subject of sensitivity analysis to transportation science. Theirs is still the most widely used device by which "gradients" of traffic equilibrium solutions are calculated, for use in bilevel transportation planning applications such as network design, origin-destination (OD) matrix estimation and problems where link tolls are imposed on the users in order to reach a traffic management objective. However, it is not widely understood that the regularity conditions proposed by them are stronger than necessary. Also, users of their method sometimes misunderstand its limitations and are not aware of the computational advantages offered by more recent methods. In fact, a more often applicable formula was proposed already by Qiu and Magnanti [Qiu, Y., Magnanti, T.L., 1989. Sensitivity analysis for variational inequalities defined on polyhedral sets. Mathematics of Operations Research 14, 410-432], and Bell and Iida [Bell, M.G.H., Iida, Y., 1997. Transportation Network Analysis. John Wiley & Sons, Chichester, UK] describe one of the cases in practice in which the formula by Tobin and Friesz would not be able to generate sensitivity information, because one of their regularity conditions fails to hold. This paper provides an overview of this formula, and illustrates by means of examples that there are several cases where it is not applicable. Our findings are illustrated with small numerical examples, as are our own analysis. The findings of this paper are hoped to motivate replacing the previous approach with the more often applicable one, not only because of this fact but equally importantly because it is intuitive and also can be much more efficiently utilized: the sensitivity problem that provides the directional derivative is a linearized traffic equilibrium problem, and the sensitivity information can be generated efficiently by only slightly modifying a state-of-the-art traffic equilibrium solver. This is essential for bringing the use of sensitivity analysis in transportation planning beyond the solution of only toy problems. We finally utilize a new sensitivity solver in the preliminary testing of a simple heuristic for bilevel optimization in continuous traffic network design, and compare it favourably to previous heuristics on known small-scale problems.
The stochastic opportunistic replacement problem, part III: improved bounding procedures
No full textWe 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
Time out of mind: “Subben’s checklist” revisited – A partial description of the development of quantitative OR papers over a period of 25 years [Elektronisk resurs]
No full textThis short paper aims to investigate some of the historical developments of a classic, well-cited and highly esteemed scientific journal in the domain of quantitative operations research – namely the INFORMS journal Operations Research, over a period of 25 years. As such this paper, and the journal in question, represents an opportunity to analyze – also in more generality – how research production has evolved, and evolves, over time. Among the developments over time that we think we can trace are that (a) the historical overviews (or, literature surveys) in the articles, as well as the list of references, somewhat counter-intuitively shrink over time, while (b) the motivating and modelling parts grow. We have also analysed the articles’ utilization of “buzz words” representing the constitutive parts of a journal paper, based on “Subben’s checklist” (Larsson & Patriksson, 2014; 2016), and conclude through a citation study using a collection of either highly or little cited papers that there is a quite strong positive correlation between a journal paper being highly cited and it utilizing this checklist
Time out of mind: “Subben’s checklist” revisited – A partial description of the development of quantitative OR papers over a period of 25 years
No full textThis short paper aims to investigate some of the historical developments of a classic, well-cited and highly esteemed scientific journal in the domain of quantitative operations research – namely the INFORMS journal Operations Research, over a period of 25 years. As such this paper, and the journal in question, represents an opportunity to analyze – also in more generality – how research production has evolved, and evolves, over time. Among the developments over time that we think we can trace are that (a) the historical overviews (or, literature surveys) in the articles, as well as the list of references, somewhat counter-intuitively shrink over time, while (b) the motivating and modelling parts grow.
We have also analysed the articles’ utilization of “buzz words” representing the constitutive parts of a journal paper, based on “Subben’s checklist” (Larsson & Patriksson, 2014; 2016), and conclude through a citation study using a collection of either highly or little cited papers that there is a quite strong positive correlation between a journal paper being highly cited and it utilizing this checklist
- …
