1,720,983 research outputs found
On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables
No full textWe define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it
Nonsingularity and Stationarity Results for Quasi-Variational Inequalities
No full textThe optimality system of a quasi-variational inequality can be reformulated as a non-smooth equation or a constrained equation with a smooth function. Both reformulations can be exploited by algorithms, and their convergence to solutions usually relies on the nonsingularity of the Jacobian, or the fact that the merit function has no nonoptimal stationary points. We prove new sufficient conditions for the absence of nonoptimal constrained or unconstrained stationary points that are weaker than some known ones. All these conditions exploit some properties of a certain matrix, but do not require the nonsingularity of the Jacobian. Further, we present new necessary and sufficient conditions for the nonsingularity of the Jacobian that are based on the signs of certain determinants. Additionally, we consider generalized Nash equilibrium problems that are a special class of quasi-variational inequalities. Exploiting their structure, we also prove some new sufficient conditions for stationarity and nonsingularity results
Numerically tractable optimistic bilevel problems
No full textWe consider a class of optimistic bilevel problems. Specifically, we address bilevel problems in which at the lower level the objective function is fully convex and the feasible set does not depend on the upper level variables.We show that this nontrivial class of mathematical programs is sufficiently broad to encompass significant real-world applications and proves to be numerically tractable. From this respect, we establish that the stationary points for a relaxation of the original problem can be obtained addressing a suitable generalized Nash equilibrium problem. The latter game is proven to be convex and with a nonempty solution set. Leveraging this correspondence, we provide a provably convergent, easily implementable scheme to calculate stationary points of the relaxed bilevel program. As witnessed by some numerical experiments on an application in economics, this algorithm turns out to be numerically viable also for big dimensional problems
Combining approximation and exact penalty in hierarchical programming
No full textWe address the minimization of an objective function over the solution set of a (non-parametric) lower-level variational inequality. This problem is a special instance of semi-infinite programs and encompasses, as particular cases, simple (smooth) bilevel and equilibrium selection problems. We resort to a suitable approximated version of the hierarchical problem. We show that this, on the one hand, does not perturb the original (exact) program ‘too much’, on the other hand, allows one to rely on some suitable exact penalty approaches whose convergence properties are established
Case article — Production and distribution optimization of beach equipment for the marinero company
No full textWe present a mixed integer nonlinear mathematical programming model, covering a broad range of operations research (OR)-related topics. The case is designed to allow students to use knowledge acquired from OR and management science classes to model, analyze, and provide concrete solutions for the considered problem. Because of its high practicality, this exercise is an ideal tool to make the OR domain more accessible and to learn how to balance a problem’s complexity with the availability of algorithms for its solution. The case has been proposed as a competitive challenge and has been assigned both to students pursuing a bachelor’s degree in management engineering and students pursuing a master’s degree in industrial engineering. Students were grouped into working teams, and all teams competed against each other to get the best solution to win the challenge. Both the work-in-team and the challenge settings have been enjoyed by the students. During three lectures of 90 minutes, a brief review of OR-related tools and a detailed description and analysis of the case study have been provided to the students. Successive periodic debriefing meeting sessions have been scheduled to engage and monitor students during project development
Effectively managing diagnostic tests to monitor the COVID-19 outbreak in Italy
No full textUrged by the outbreak of the COVID-19 in Italy, this study aims at helping to tackle the spread of the disease by resorting to operations research techniques. In particular, we propose a mathematical program to model the problem of establishing how many diagnostic tests the Italian regions must perform in order to maximize the overall disease detection capability. An important feature of our approach is its simplicity: data we resort to are easy to obtain and one can employ standard optimization tools to address the problem. The results we obtain when applying our method to the Italian case seem promising
On Nested Affine Variational Inequalities: The Case of Multi-Portfolio Selection
No full textWe deal with nested affine variational inequalities, i.e., hierarchical problems involving an affine (upper-level) variational inequality whose feasible set is the solution set of another affine (lower-level) variational inequality. We apply this modeling tool to the multi-portfolio selection problem, where the lower-level variational inequality models the Nash equilibrium problem made up by the different accounts, while the upper-level variational inequality is instrumental to perform a selection over this equilibrium set. We propose a projected averaging Tikhonov-like algorithm for the solution of this problem, which only requires the monotonicity of the variational inequalities for both the upper- and the lower-level in order to converge. Finally, we provide complexity properties
A convergent and fully distributable SVMs training algorithm
No full textThe Support Vector Machines (SVMs) dual formulation has a non-separable structure that makes the design of a convergent distributed algorithm a very difficult task. Recently some separable and distributable reformulations of the SVM training problem have been obtained by fixing one primal variable. While this strategy seems effective for some applications, in certain cases it could be weak since it drastically reduces the overall final performance. In this work we present the first fully distributable algorithm for SVMs training that globally converges to a solution of the original (non-separable) SVMs dual formulation. Besides a detailed convergence analysis, we provide a simple demonstrative example showing the advantages of the original SVMs dual formulation with respect to the weak separable one and highlights the practical effectiveness of our method. We report further tests to show practical convergence of the proposed method on real-world datasets
Recent Advances in Nonlinear Optimization and Equilibrium Problems: a Tribute to Marco D’Apuzzo
No full textOn Nested Affine Variational Inequalities: The Case of Multi-Portfolio Selection
Full text linkWe deal with nested affine variational inequalities, i.e., hierarchical problems involving an affine (upper-level) variational inequality whose feasible set is the solution set of another affine (lower-level) variational inequality. We apply this modeling tool to the multi-portfolio selection problem, where the lower-level variational inequality models the Nash equilibrium problem made up by the different accounts, while the upper-level variational inequality is instrumental to perform a selection over this equilibrium set. We propose a projected averaging Tikhonov-like algorithm for the solution of this problem, which only requires the monotonicity of the variational inequalities for both the upper- and the lower-level in order to converge. Finally, we provide complexity properties
- …
