ALBERT

Description: In this paper, we present global optimality conditions for cubic minimization involving cubic constraints and box or bivalent constraints, where the cubic objective function and cubic constraints contain no cross terms. By utilizing quadratic underestimators, we first derive sufficient global optimality conditions for a global minimizer of cubic minimization problems with cubic inequality and box constraints. Then we establish them for cubic minimization with cubic inequality and bivalent constraints. Finally, we establish sufficient and necessary global optimality condition for cubic minimization with cubic equality and binary constraints.

Description: In this paper, we study differential properties of Euclidean projection onto the high dimensional power cone $$\begin{aligned} K^{\alpha }_{m,n}=\left\{ (x,z)\in \mathbb {R}^m_+ \times \mathbb {R}^n, \left| \left| {z} \right| \right| \le \prod \nolimits _{i=1}^m x_i^{\alpha _i}\right\} , \end{aligned}$$ where \(0〈\alpha _i, \sum \nolimits _{i=1}^m \alpha _i=1\) . Projector’s formulas, its directional derivative formulas, its first order Fréchet derivative formulas are considered.

Description: We study the order of maximizers in linear conic programming (CP) as well as stability issues related to this. We do this by taking a semi-infinite view on conic programs: a linear conic problem can be formulated as a special instance of a linear semi-infinite program (SIP), for which characterizations of the stability of first order maximizers are well-known. However, conic problems are highly special SIPs, and therefore these general SIP-results are not valid for CP. We discuss the differences between CP and general SIP concerning the structure and results for stability of first order maximizers, and we present necessary and sufficient conditions for the stability of first order maximizers in CP.

Description: In this study, a new adaptive trust-region strategy is presented to solve nonlinear systems. More specifically, we propose a new method leading to produce a smaller trust-region radius close to the optimizer and a larger trust-region radius far away from the optimizer. Accordingly, it can lead to a smaller step-size close to the optimizer and a larger one far away from the optimizer. The new strategy includes a convex combination of the maximum norm of function value of some preceding successful iterates and the current norm of function value. The global convergence of the proposed approach is established while the local q-quadratic convergence rate is proved under local error bound condition, which is weaker than the nonsingularity. Numerical results of the proposed algorithm are also reported.

Description: We propose an exact algorithm to find the optimal solution to the grey pattern problem which is a special instance of the quadratic assignment problem. A very effective branch and bound algorithm is constructed. The special structure of the problem is exploited and optimal solutions for many problem instances established. One instance based on 64 facilities, organized in an 8 by 8 pattern, that was extensively researched in the literature was optimally solved in 15 s of computer time while existing papers report solution times of hours.

Description: In this article we consider combinatorial markets with valuations only for singletons and pairs of buy/sell-orders for swapping two items in equal quantity. We provide an algorithm that permits polynomial time market-clearing and -pricing. The results are presented in the context of our main application: the futures opening auction problem. Futures contracts are an important tool to mitigate market risk and counterparty credit risk. In futures markets these contracts can be traded with varying expiration dates and underlyings. A common hedging strategy is to roll positions forward into the next expiration date, however this strategy comes with significant operational risk. To address this risk, exchanges started to offer so-called futures contract combinations , which allow the traders for swapping two futures contracts with different expiration dates or for swapping two futures contracts with different underlyings. In theory, the price is in both cases the difference of the two involved futures contracts. However, in particular in the opening auctions price inefficiencies often occur due to suboptimal clearing, leading to potential arbitrage opportunities. We present a minimum cost flow formulation of the futures opening auction problem that guarantees consistent prices. The core ideas are to model orders as arcs in a network, to enforce the equilibrium conditions with the help of two hierarchical objectives, and to combine these objectives into a single weighted objective while preserving the price information of dual optimal solutions. The resulting optimization problem can be solved in polynomial time and computational tests establish an empirical performance suitable for production environments.

Description: Let a polyhedral convex set be given by a finite number of linear inequalities and consider the problem to project this set onto a subspace. This problem, called polyhedral projection problem, is shown to be equivalent to multiple objective linear programming. The number of objectives of the multiple objective linear program is by one higher than the dimension of the projected polyhedron. The result implies that an arbitrary vector linear program (with arbitrary polyhedral ordering cone) can be solved by solving a multiple objective linear program (i.e. a vector linear program with the standard ordering cone) with one additional objective space dimension.

Description: We propose a projection algorithm for solving split feasibility problems involving paramonotone equilibria and convex optimization. The proposed algorithm can be considered as a combination of the projection ones for equilibrium and convex optimization problems. We apply the algorithm for finding an equilibrium point with minimal environmental cost for a model in electricity production. Numerical results for the model are reported.

Description: In this paper we study discrete-time Markov decision processes in Borel spaces with a finite number of constraints and with unbounded rewards and costs. Our aim is to provide a simple method to compute constrained optimal control policies when the payoff functions and the constraints are of either: infinite-horizon discounted type and average (a.k.a. ergodic) type. To deduce optimality results for the discounted case, we use the Lagrange multipliers method that rewrites the original problem (with constraints) into a parametric family of discounted unconstrained problems. Based on the dynamic programming technique as long with a simple use of elementary differential calculus, we obtain both suitable Lagrange multipliers and a family of control policies associated to these multipliers, this last family becomes optimal for the original problem with constraints. We next apply the vanishing discount factor method in order to obtain, in a straightforward way, optimal control policies associated to the average problem with constraints. Finally, to illustrate our results, we provide a simple application to linear–quadratic systems (LQ-systems).

Description: We consider the 1D skiving stock problem (SSP) which is strongly related to the dual bin packing problem: find the maximum number of products with minimum length L that can be constructed by connecting a given supply of \( m \in {\mathbb {N}} \) smaller item lengths \( l_1,\ldots ,l_m \) with availabilities \( b_1,\ldots , b_m \) . For this NP-hard optimization problem, we focus on the proper relaxation and introduce a modeling approach based on graph theory. Additionally, we investigate the quality of the proper gap, i.e., the difference between the optimal objective values of the proper relaxation and the SSP itself. As an introductorily motivation, we prove that the SSP does not possess the integer round down property (IRDP) with respect to the proper relaxation. The main contribution of this paper is given by a construction principle for an infinite number of non-equivalent non-proper-IRDP instances and an enumerative approach that leads to the currently largest known (proper) gap.

Description: This paper discusses approximations of continuous and mixed-integer non-linear optimization problems via piecewise linear functions. Various variants of circle cutting problems are considered, where the non-overlap of circles impose a non-convex feasible region. While the paper is written in an “easy-to-understand” and “hands-on” style which should be accessible to graduate students, also new ideas are presented. Specifically, piecewise linear functions are employed to yield mixed-integer linear programming problems which provide lower and upper bounds on the original problem, the circle cutting problem. The piecewise linear functions are modeled by five different formulations, containing the incremental and logarithmic formulations. Another variant of the cutting problem involves the assignment of circles to pre-defined rectangles. We introduce a new global optimization algorithm, based on piecewise linear function approximations, which converges in finitely many iterations to a globally optimal solution. The discussed formulations are implemented in GAMS. All GAMS-files are available for download in the Electronic supplementary material. Extensive computational results are presented with various illustrations.

Description: A sequential method for a class of generalized fractional programming problems is proposed. The considered objective function is the ratio of powers of affine functions and the feasible region is a polyhedron, not necessarily bounded. Theoretical properties of the optimization problem are first established and the maximal domains of pseudoconcavity are characterized. When the objective function is pseudoconcave in the feasible region, the proposed algorithm takes advantage of the nice optimization properties of pseudoconcave functions; the particular structure of the objective function allows to provide a simplex-like algorithm even when the objective function is not pseudoconcave. Computational results validate the nice performance of the proposed algorithm.

Description: In this paper, we consider a production, transportation and pricing problem for multi-product multi-market (PTPMM) as a system, and develop a PTPMM network equilibrium model. After allocating each product’s production cost and revenue to each path, we establish a profit network graph. An equilibrium PTPMM matrix and a \(\lambda \) -combination equilibrium are proposed based on a generalization of the well-known Wardrop’s equilibrium principle. The necessary and sufficient conditions for the \(\lambda \) -combination equilibrium are proposed using a linear scalarized profit function. We prove that solving the PTPMM network equilibrium problem can be reduced to the solving of the weak vector variational inequality problem, which proposes an algorithm for the PTPMM problem. Finally, an illustrative example is given to demonstrate an application of these theoretical results.

Description: In this paper we consider the impact of transaction costs on the periodic portfolio revision. We offer a statistical model for simulation of daily returns which can explain the empirical behavior of equity returns. The model is based on ARMA–GARCH processes, principal component analysis, classical tempered stable distribution, and skewed \(t\) copula. The main contribution of this paper is the application of a new approach for modelling transaction costs using daily returns by estimating an optimal portfolio with an arbitrary length for the holding period. Moreover, we compare the portfolio selection problem solved with and without transaction costs by applying different risk and performance measures on simulated returns, taking into account their Sharpe ratio and stable tail-adjusted return ratio. The experimental analysis suggests that the incorporation of transaction costs into an optimal portfolio framework leads to remarkable reduction of the transaction costs and stabilization of the optimal portfolio strategy. However, ignoring transaction costs does not always result in a less efficient portfolio.

Description: This paper considers a generalization of the inverse 1-median problem, the inverse \(k\) -centrum problem, on trees with variable vertex weights. In contrast to the linear time solvability of the inverse 1-median problem on trees, we prove that the inverse \(k\) -centrum problem on trees is \(\textit{NP}\) -hard. Particularly, the inverse 1-center problem, a special case of the mentioned problem with \(k=1\) , on a tree with \(n\) vertices can be solved in \(O(n^{2})\) time.

Description: We consider a discrete-time risk model with delayed claims and a dividend payment strategy. It is assumed that every main claim will induce a by-claim which may be delayed for one time period with a certain probability. In the evaluation of the expected present value of dividends, the interest rates are assumed to follow a Markov chain with finite state space. Dividends are paid to the shareholders according to an admissible strategy. The company controls the amount of dividends in order to maximize the cumulative expected discounted dividends prior to ruin minus the expected discounted penalty value at ruin. We obtain some properties of the optimal dividend-payment strategy, and offer high efficiency algorithms for obtaining the optimal strategy, the optimal value function and the expectation of time of ruin under the optimal strategy. Our method is mainly to transform the value function. Numerical examples are presented to illustrate the transformation method and the impact of the penalty for ruin on the optimal strategy, the corresponding expected present value of dividends and the expectation of time of ruin.

Description: Consider a search problem in which a stationary object is in one of \(L \epsilon \mathcal {N}\) locations. Each location can be searched using one of \(T \epsilon \mathcal {N}\) technologies, and each location-technology pair has a known associated cost and overlook probability. These quantities may depend on the number of times that the technology is applied to the location. This paper finds a search policy that maximizes the probability of finding the object given a constraint on the available budget. It also finds the policy that maximizes the probability of correctly stating at the end of a search where the object is. Additionally it exhibits another policy that minimizes the expected cost required to find the object and the optimal policy for stopping.

Description: In this paper we apply modified Newton method based on sample average approximation (SAA) to solve stochastic variational inequality with stochastic second-order cone constraints (SSOCCVI). Under some moderate conditions, the SAA solution converges to its true counterpart with probability approaching one at exponential rate as sample size increases. We apply the theoretical results for solving a class of stochastic second order cone complementarity problems and stochastic programming problems with stochastic second order cone constraints. Some illustrative examples are given to show how the globally convergent method works and the comparison results between our method and other methods. Furthermore, we apply this method to portfolio optimization with loss risk constraints problems.

Description: In this paper, we study the optimal reinsurance-investment problems in a financial market with jump-diffusion risky asset, where the insurance risk model is modulated by a compound Poisson process, and the two jump number processes are correlated by a common shock. Moreover, we remove the assumption of nonnegativity on the expected value of the jump size in the stock market, which is more economic reasonable since the jump sizes are always negative in the real financial market. Under the criterion of mean–variance, based on the stochastic linear–quadratic control theory, we derive the explicit expressions of the optimal strategies and value function which is a viscosity solution of the corresponding Hamilton–Jacobi–Bellman equation. Furthermore, we extend the results in the linear–quadratic setting to the original mean–variance problem, and obtain the solutions of efficient strategy and efficient frontier explicitly. Some numerical examples are given to show the impact of model parameters on the efficient frontier.

Description: The aim of this paper is to investigate the continuity of the solution set maps of set-valued vector optimization problems with set optimization criterion. First, we introduce a new concept, which is called a u -lower level map. Then, we give some sufficient conditions for the upper and lower semicontinuities of the generalized lower level map. Finally, by virtue of the semicontinuity of the u -lower level map, we obtain the continuity of the minimal solution set map to parametric set-valued vector optimization problems with set optimization criterion.

Description: We present a unified approach for partial information optimal investment and consumption problems in a non-Markovian Itô process market. The stochastic local mean rate of return and the Wiener process cannot be observed by the agent, whereas the path-dependent volatility, the path-dependent interest rate and the asset prices can be observed. The main assumption is that the asset price volatility is a nonanticipative functional of the asset price trajectory. The utility functions are general and satisfy standard conditions. First, we show that the corresponding full information market is complete and in this setting we solve the problem using standard methods. Second, we transform the original partial information problem into a corresponding full information problem using filtering theory, and show that it follows that the market is observationally complete in the sense that any contingent claim adapted to the observable filtration is replicable. Using the solutions of the full information problem we then easily derive solutions to the original partial information problem.

Description: In the paper we discuss three general properties of values of TU-games: \(\uplambda \) -standardness, general probabilistic consistency and some modifications of the null player property. Necessary and sufficient conditions for different families of efficient, linear and symmetric values are given in terms of these properties. It is shown that the results obtained can be used to get new axiomatizations of several classical values of TU-games.

Description: This study aims to present a limited memory BFGS algorithm to solve non-convex minimization problems, and then use it to find the largest eigenvalue of a real symmetric positive definite matrix. The proposed algorithm is based on the modified secant equation, which is used to the limited memory BFGS method without more storage or arithmetic operations. The proposed method uses an Armijo line search and converges to a critical point without convexity assumption on the objective function. More importantly, we do extensive experiments to compute the largest eigenvalue of the symmetric positive definite matrix of order up to 54,929 from the UF sparse matrix collection, and do performance comparisons with EIGS (a Matlab implementation for computing the first finite number of eigenvalues with largest magnitude). Although the proposed algorithm converges to a critical point, not a global minimum theoretically, the compared results demonstrate that it works well, and usually finds the largest eigenvalue of medium accuracy.

Description: In the paper portfolio optimization over long run risk sensitive criterion is considered. It is assumed that economic factors which stimulate asset prices are ergodic but non necessarily uniformly ergodic. Solution to suitable Bellman equation using local span contraction with weighted norms is shown. The form of optimal strategy is presented and examples of market models satisfying imposed assumptions are shown.

Description: We consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.

Description: 〈h3〉Abstract〈/h3〉 〈p〉We introduce four accelerated (sub)gradient algorithms (ASGA) for solving several classes of convex optimization problems. More specifically, we propose two estimation sequences majorizing the objective function and develop two iterative schemes for each of them. In both cases, the first scheme requires the smoothness parameter and a Hölder constant, while the second scheme is parameter-free (except for the strong convexity parameter which we set zero if it is not available) at the price of applying a finitely terminated backtracking line search. The proposed algorithms attain the optimal complexity for smooth problems with Lipschitz continuous gradients, nonsmooth problems with bounded variation of subgradients, and weakly smooth problems with Hölder continuous gradients. Further, for strongly convex problems, they are optimal for smooth problems while nearly optimal for nonsmooth and weakly smooth problems. Finally, numerical results for some applications in sparse optimization and machine learning are reported, which confirm the theoretical foundations.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study a multiclass many-server queueing system with renewal arrivals and generally distributed service and patience times under a nonpreemptive allocation policy. The status of the system is described by a pair of measure-valued processes to track the residual service and patience times of customers in each class. We establish fluid approximations and study the long-term behavior of the fluid model. The equilibrium state of the fluid model leads to a nonlinear program, which enables us to identify a lower bound for the long-run expected total holding and abandonment costs and design an allocation policy to achieve this lower bound. The optimality of the proposed policy is also demonstrated via numerical experiments. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the problem of finding consistent upper price bounds and super replication strategies for exotic options, given the observation of call prices in the market. This field of research is called model-independent finance and has been introduced by Hobson (Finance Stoch 2(4):329–347, 1998). Here we use the link to mass transport problems. In contrast to existing literature we assume that the marginal distributions at the two time points we consider are discrete probability distributions. This has the advantage that the optimization problems reduce to linear programs and can be solved rather easily when assuming a general martingale Spence Mirrlees condition. We will prove the optimality of left-monotone transport plans under this assumption and provide an algorithm for its construction. Our proofs are simple and do not require much knowledge of probability theory. At the end we present an example to illustrate our approach.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the end-of-life inventory problem for the supplier of a product in its final phase of the service life cycle. This phase starts when the production of the items stops and continues until the warranty of the last sold item expires. At the beginning of this phase the supplier places a final order for spare parts to serve customers coming with defective items. At any time during the final phase the supplier may also decide to switch to an alternative and more cost effective service policy. This alternative policy may be in the form of replacing defective items with substitutable products or offering discounts/rebates on the new generation ones. In this setup, the objective is to find a final order quantity and a time to switch to an alternative policy which will minimize the total expected discounted costs of the supplier. The switching time is a stopping time and is based on the realization of the arrival process of defective items. In this paper, we study this problem under a general cost structure in a continuous-time framework where the arrival of customers is given by a non-homogeneous Poisson process. We show in detail how to compute the value function, and illustrate our approach on numerical examples.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The main results of the paper are a minimal element theorem and an Ekeland-type variational principle for set-valued maps whose values are compared by means of a weighted set order relation. This relation is a mixture of a lower and an upper set relation which form the building block for modern approaches to set-valued optimization. The proofs rely on nonlinear scalarization functions which admit to apply the extended Brézis–Browder theorem. Moreover, Caristi’s fixed point theorem and Takahashi’s minimization theorem for set-valued maps based on the weighted set order relation are obtained and the equivalences among all these results is verified. An application to generalized intervals is given which leads to a clear interpretation of the weighted set order relation and versions of Ekeland’s principle which might be useful in (computational) interval mathematics.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A novel approach for solving a multiple judge, multiple criteria decision making (MCDM) problem is proposed. The presence of multiple criteria leads to a non-total order relation. The ranking of the alternatives in such a framework is done by reinterpreting the MCDM problem as a multivariate statistics one and by applying the concepts in Hamel and Kostner (J Multivar Anal 167:97–113, 〈span〉2018〈/span〉). A function that ranks alternatives as well as additional functions that categorize alternatives into sets of “good” and “bad” choices are presented. The paper shows that the properties of these functions ensure a reasonable decision making process.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the problem of determining an optimal strategy for electricity injection that faces an uncertain power demand stream. This demand stream is modeled via an Ornstein–Uhlenbeck process with an additional jump component, whereas the power flow is represented by the linear transport equation. We analytically determine the optimal amount of power supply for different levels of available information and compare the results to each other. For numerical purposes, we reformulate the original problem in terms of the cost function such that classical optimization solvers can be directly applied. The computational results are illustrated for different scenarios. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we consider the problem of optimal investment-reinsurance with two dependent classes of insurance risks in a regime-switching financial market. In our model, the two claim-number processes are correlated through a common shock component, and the market mode is classified into a finite number of regimes. We also assume that the insurer can purchase proportional reinsurance and invest its surplus in a financial market, and that the values of the model parameters depend on the market mode. Using the techniques of stochastic linear-quadratic control, under the mean–variance criterion, we obtain analytic expressions for the optimal investment and reinsurance strategies, and derive closed-form expressions for the efficient strategies and the efficient frontiers which are based on the solutions to some systems of linear ordinary differential equations. Finally, we carry out a numerical study for illustration purpose.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A new solution concept for two-player zero-sum matrix games with multi-dimensional payoffs is introduced. It is based on extensions of the vector order in 〈span〉 〈span〉\(\mathbb {R}^d\)〈/span〉 〈/span〉 to order relations in the power set of 〈span〉 〈span〉\(\mathbb {R}^d\)〈/span〉 〈/span〉, so-called set relations, and strictly motivated by the interpretation of the payoff as multi-dimensional loss for one and gain for the other player. The new concept provides coherent worst case estimates for games with multi-dimensional payoffs. It is shown that–in contrast to games with one-dimensional payoffs–the corresponding strategies are different from equilibrium strategies for games with multi-dimensional payoffs. The two concepts are combined into new equilibrium notions for which existence theorems are given. Relationships of the new concepts to existing ones such as Shapley and vector equilibria, vector minimax and maximin solutions as well as Pareto optimal security strategies are clarified.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study a discrete time queueing system where deterministic arrivals have i.i.d. exponential delays 〈span〉 〈span〉\(\xi _{i}\)〈/span〉 〈/span〉. We describe the model as a bivariate Markov chain, prove its ergodicity and study the joint equilibrium distribution. We write a functional equation for the bivariate generating function, finding the solution on a subset of its domain. This solution allows us to prove that the equilibrium distribution of the chain decays super-exponentially fast in the quarter plane. We exploit the latter result and discuss the numerical computation of the solution through a simple yet effective approximation scheme in a wide region of the parameters. Finally, we compare the features of this queueing model with the standard 〈em〉M〈/em〉 / 〈em〉D〈/em〉 / 1 system, showing that the congestion turns out to be very different when the traffic intensity is close to 1.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Given an undirected simple graph 〈em〉G〈/em〉 with node set 〈em〉V〈/em〉 and edge set 〈em〉E〈/em〉, let 〈span〉 〈span〉\(f_v\)〈/span〉 〈/span〉, for each node 〈span〉 〈span〉\(v \in V\)〈/span〉 〈/span〉, denote a nonnegative integer value that is lower than or equal to the degree of 〈em〉v〈/em〉 in 〈em〉G〈/em〉. An 〈em〉f〈/em〉-dominating set in 〈em〉G〈/em〉 is a node subset 〈em〉D〈/em〉 such that for each node 〈span〉 〈span〉\(v\in V{{\setminus }}D\)〈/span〉 〈/span〉 at least 〈span〉 〈span〉\(f_v\)〈/span〉 〈/span〉 of its neighbors belong to 〈em〉D〈/em〉. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of 〈em〉f〈/em〉-dominating sets in 〈em〉G〈/em〉 and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost 〈span〉 〈span〉\(c_v\in {\mathbb {R}}\)〈/span〉 〈/span〉 for each node 〈span〉 〈span〉\(v\in V\)〈/span〉 〈/span〉, find an 〈em〉f〈/em〉-dominating set 〈em〉D〈/em〉 in 〈em〉G〈/em〉 whose cost, given by 〈span〉 〈span〉\(\sum _{v\in D}{c_v}\)〈/span〉 〈/span〉, is a minimum.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study a utility maximization problem under multiple Value-at-Risk (VaR)-type constraints. The optimization framework is particularly important for financial institutions which have to follow short-time VaR-type regulations under some realistic regulatory frameworks like Solvency II, but need to serve long-term liabilities. Deriving closed-form solutions, we show that risk management using multiple VaR constraints is more useful for loss prevention at 〈em〉intertemporal〈/em〉 time instances compared with the well-known result of the one-VaR problem in Basak and Shapiro (Rev Financ Stud 14:371–405, 〈span〉2001〈/span〉), confirming the numerical analysis of Shi and Werker (J Bank Finance 36(12):3227–3238, 〈span〉2012〈/span〉). In addition, the multiple-VaR solution at 〈em〉maturity〈/em〉 on average dominates the one-VaR solution in a wide range of intermediate market scenarios, but performs worse in good and very bad market scenarios. The range of these very bad market scenarios is however rather limited. Finally, we show that it is preferable to reach a fixed terminal state through insured intertemporal states rather than through extreme up and down movements, showing that a multiple-VaR framework induces a preference for less volatility.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉While there is vast literature on principal-agent service contracts in which a principal pools the service capacities of multiple agents for economy of scale, here we focus on the case that exists in practice of an agent pooling multiple principals. Since it is reasonable to presume that an agent of good standing attracts multiple contract offers, his main strategic decision is to select his principals. It is generally known that a principal can extract all economic surplus from a risk-neutral agent while the agent breaks even. However, this is not the case for an agent contracting multiple principals while accounting for their interdependent failure characteristics. In this paper we describe a methodology that enables an agent to calculate the value of each potential principal and therefore to contract a Pareto optimal subset of principals in a market where neither principals’ nor agents’ collusion is allowed. Unfortunately, computational intractability of first order analysis forces us to rely on a Monte Carlo simulation to understand the agent’s choice of the principals. The computation of each principal’s contribution to the agent’s welfare is enabled by a specific cooperative game of independent interest. We show that under certain conditions the agent can do better than break-even and can realize profits convexly increasing in the cardinality of the contracted principals. Our findings not only equip agents with a mathematical instrument for assessment of service contract’s financial viability but also offer agents a holistic perspective for screening principals before accepting contract offers.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The paper concerns with an inertial-like algorithm for approximating solutions of equilibrium problems in Hilbert spaces. The algorithm is a combination around the relaxed proximal point method, inertial effect and the Krasnoselski–Mann iteration. The using of the proximal point method with relaxations has allowed us a more flexibility in practical computations. The inertial extrapolation term incorporated in the resulting algorithm is intended to speed up convergence properties. The main convergence result is established under mild conditions imposed on bifunctions and control parameters. Several numerical examples are implemented to support the established convergence result and also to show the computational advantage of our proposed algorithm over other well known algorithms.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We analyze a Markovian smart polling model, which is a special case of the smart polling models studied in the work of Boon et al. (Queueing Syst 66:239–274, 〈span〉2010〈/span〉), as well as a generalization of the gated 〈em〉M〈/em〉 / 〈em〉M〈/em〉 / 1 queue considered in Resing and Rietman (Stat Neerlandica 58:97–110, 〈span〉2004〈/span〉). We first derive tractable expressions for the stationary distribution (when it exists) as well as the Laplace transforms of the transition functions of this polling model—while further assuming the system is empty at time zero—and we also present simple necessary and sufficient conditions for ergodicity of the smart polling model. Finally, we conclude the paper by briefly explaining how these techniques can be used to study other interesting variants of this smart polling model.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We develop a complete analysis of a general entry–exit–scrapping model. In particular, we consider an investment project that operates within a random environment and yields a payoff rate that is a function of a stochastic economic indicator such as the price of or the demand for the project’s output commodity. We assume that the investment project can operate in two modes, an “open” one and a “closed” one. The transitions from one operating mode to the other one are costly and immediate, and form a sequence of decisions made by the project’s management. We also assume that the project can be permanently abandoned at a discretionary time and at a constant sunk cost. The objective of the project’s management is to maximise the expected discounted payoff resulting from the project’s management over all switching and abandonment strategies. We derive the explicit solution to this stochastic control problem that involves impulse control as well as discretionary stopping. It turns out that this has a rather rich structure and the optimal strategy can take eight qualitatively different forms, depending on the problems data.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The question of measuring and managing systemic risk—especially in view of the recent financial crisis—became more and more important. We study systemic risk by taking the perspective of a financial regulator and considering the axiomatic approach originally introduced in Chen et al. (Manag Sci 59(6):1373–1388, 〈span〉2013〈/span〉) and extended in Kromer et al. (Math Methods Oper Res 84:323–357, 〈span〉2016〈/span〉). The aim of this paper is to generalize the static approach in Kromer et al. (〈span〉2016〈/span〉) and analyze systemic risk measures in a dynamic setting. We work in the framework of Cheridito et al. (Electron J Probab 11:57–106, 〈span〉2006〈/span〉) who consider risk measures for bounded discrete-time processes. Apart from the possibility to consider the “evolution of financial values”, another important advantage of the dynamic approach is the possibility to incorporate information in the risk measurement and management process. In context of this dynamic setting we also discuss the arising question of time-consistency for our dynamic systemic risk measures.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we consider 〈em〉k〈/em〉-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when 〈em〉k〈/em〉 is fixed. We focus first on the case without backorders and we give a 〈span〉 〈span〉\((2k-1)\)〈/span〉 〈/span〉-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a 〈em〉k〈/em〉-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a 〈em〉k〈/em〉-approximation algorithm for the 〈em〉k〈/em〉-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper new modeling techniques of 〈span〉 〈span〉\((S-1,S)\)〈/span〉 〈/span〉 inventory systems (continuous review base-stock inventory systems) with state dependent demand rates are proposed. Examples of single-location 〈span〉 〈span〉\((S-1,S)\)〈/span〉 〈/span〉 inventory systems where the demand, experienced by the system, varies due to the state of the system are, e.g., inventory models with partial backorders, inventory models with lost sales, inventory models with perishable items, inventory models with emergency replenishments etc. Models of such inventory systems are in general hard to solve due to the fact that the Markov property is often lost, and the prevalent tool used in the literature for providing exact solutions of such models is the theory of partial differential equations. Instead of using partial differential equations with rather complicated analysis of boundary conditions, we suggest considerably simpler techniques which are based on elementary theory of queueing and renewal processes. First, we show that it is possible to use Markov theory in order to prove certain statistical properties of the limiting distribution of the ages of the items in the system. Secondly, we develop a corresponding procedure based on renewal theory, which forms a basis for more complicated models assuming non-Poisson customer demand processes.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider relative or subjective optimization problems where the goal function and feasible set are dependent of the current state of the system under consideration. We propose equilibrium formulations of the corresponding problems that lead to general (quasi-)equilibrium problems. We propose to apply a regularized version of the penalty method for the general quasi-equilibrium problem, which enables us to establish existence results under weak coercivity conditions and replace the quasi-equilibrium problem with a sequence of the usual equilibrium problems. We describe several examples of applications and show that the subjective approach can be extended to non-cooperative game problems.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In the framework of normed spaces ordered by a convex cone not necessarily solid, we consider two set scalarization functions of type sup-inf, which are extensions of the oriented distance of Hiriart-Urruty. We investigate some of their properties and, moreover, we use these functions to characterize the lower and upper set less preorders of Kuroiwa and the strict lower and strict upper set relations. Finally, we apply the obtained results to characterize several concepts of minimal solution to a set optimization problem defined by a set-valued map. Minimal and weak minimal solutions with respect to the lower and upper set less relations are between the concepts considered. Illustrative examples are also given.〈/p〉

Description: Conventional data envelopment analysis evaluates the relative efficiency of a set of homogeneous decision making units (DMUs), where DMUs are evaluated in terms of a specified set of inputs and outputs. In some situations, however, a performance factor could serve as either an output or an input. These factors are referred to as dual-role factors. The presence of dual-role factor among performance factors gives rise to the issue of how to fairly designate the input/output status to such factor. Several studies have been conducted treating a dual-role factor in both methodological and applied nature. One approach taken to address this problem is to view the dual-role factor as being nondiscretionary and connect it to the returns to scale concepts. It is argued that the idea of classifying a factor as an input or an output within a single model cannot consider the causality relationships between inputs and outputs. In this paper we present a mixed integer linear programming approach with the aim at dealing with the dual-role factor. Model structure is developed for finding the status of a dual-role factor via solving a single model while considering the causality relationships between inputs and outputs. It is shown that the new model can designate the status of a dual-role factor with half calculations as the previous model. Both individual and aggregate points of view are suggested for deriving the most appropriate designation of the dual-role factor. A data set involving 18 supplier selections is adapted from literature review to illustrate the efficacy of the proposed models and compare the new approach with the previous ones.

Description: We consider a multi-person stopping game with players’ priorities and multiple stopping. Players observe sequential offers at random or fixed times. Each accepted offer results in a reward. Each player can obtain fixed number of rewards. If more than one player wants to accept an offer, then the player with the highest priority among them obtains it. The aim of each player is to maximize the expected total reward. For the game defined this way, we construct a Nash equilibrium. The construction is based on the solution of an optimal multiple stopping problem. We show the connections between expected rewards and stopping times of the players in Nash equilibrium in the game and the optimal expected rewards and optimal stopping times in the multiple stopping problem. A Pareto optimum of the game is given. It is also proved that the presented Nash equilibrium is a sub-game perfect Nash equilibrium. Moreover, the Nash equilibrium payoffs are unique. We also present new results related to multiple stopping problem.

Description: In this paper, some notions of pointwise well-posedness for set optimization problems are introduced. Some relationships among these notions are established. Using a new nonlinear scalarization function, pointwise well-posed set optimization problems are characterized by means of a family of Tykhonov well-posed scalar optimization problems. Also, three classes of well-posed set optimization problems are identified.

Description: In this paper, we present a proposal for a variation of the predictor–corrector interior point method with multiple centrality corrections. The new method uses the continued iteration to compute a new search direction for the predictor corrector method. The purpose of incorporating the continued iteration is to reduce the overall computational cost required to solve a linear programming problem. The computational results constitute evidence of the improvement obtained with the use of this technique combined with the interior point method.

Description: This paper analyzes a single-server discrete-time queueing model with general independent arrivals, where the service process of the server is characterized in two steps. Specifically, the model assumes that (1) each customer represents a random, arbitrarily distributed, amount of work for the server, the service demand , and (2) the server disposes of a fixed number of work units that can be executed per slot, the service capacity . For this non-classical queueing model, we obtain explicit closed-form results for the probability generating functions (pgf’s) of the unfinished work in the system (expressed in work units) and the queueing delay of an arbitrary customer (expressed in time slots). Deriving the pgf of the number of customers in the system turns out to be hard, in general. Nevertheless, we derive this pgf explicitly in a number of special cases, i.e., either for geometrically distributed service demands, and/or for Bernoulli arrivals or geometric arrivals. The obtained results show that the tail distributions of the unfinished work, the customer delay and the system content all exhibit a geometric decay, with semi-analytic formulas for the decay rates available. Another interesting conclusion is that, for a given system load, the mean customer delay converges to constant limiting values when the service capacity per slot goes to infinity, and either the mean arrival rate or the mean service demand increases proportionally. Accurate approximative analytical expressions are available for these limiting values.

Description: We study the performance of a reflected fluid production/inventory model operating in a stochastic environment that is modulated by a finite state continuous time Markov chain. The process alternates between ON and OFF periods. The ON period is switched to OFF when the content level reaches a predetermined level q and returns to ON when it drops to 0. The ON/OFF periods generate an alternative renewal process. Applying a matrix analytic approach, fluid flow techniques and martingales, we develop methods to obtain explicit formulas for the cost functionals (setup, holding, production and lost demand costs) in the discounted case and under the long-run average criterion. Numerical examples present the trade-off between the holding cost and the loss cost and show that the total cost appears to be a convex function of q .

Description: We study the combinatorial FIFO stack-up problem. In delivery industry, bins have to be stacked-up from conveyor belts onto pallets with respect to customer orders. Given k sequences \(q_1, \ldots , q_k\) of labeled bins and a positive integer p , the aim is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto an initially empty pallet of unbounded capacity located at one of p stack-up places. Bins with different pallet labels have to be placed on different pallets, bins with the same pallet label have to be placed on the same pallet. After all bins for a pallet have been removed from the given sequences, the corresponding stack-up place will be cleared and becomes available for a further pallet. The FIFO stack-up problem is to find a stack-up sequence such that all pallets can be build-up with the available p stack-up places. In this paper, we introduce two digraph models for the FIFO stack-up problem, namely the processing graph and the sequence graph. We show that there is a processing of some list of sequences with at most p stack-up places if and only if the sequence graph of this list has directed pathwidth at most \(p-1\) . This connection implies that the FIFO stack-up problem is NP-complete in general, even if there are at most 6 bins for every pallet and that the problem can be solved in polynomial time, if the number p of stack-up places is assumed to be fixed. Further the processing graph allows us to show that the problem can be solved in polynomial time, if the number k of sequences is assumed to be fixed.

Description: Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to statistics and computer science. When the marginal probability measures are absolutely continuous (or vanish on small sets) the theory of Wasserstein barycenters is well-developed [see the seminal paper (Agueh and Carlier in SIAM J Math Anal 43(2):904–924, 2011 )]. However, exact continuous computation of Wasserstein barycenters in this setting is tractable in only a small number of specialized cases. Moreover, in many applications data is given as a set of probability measures with finite support. In this paper, we develop theoretical results for Wasserstein barycenters in this discrete setting. Our results rely heavily on polyhedral theory which is possible due to the discrete structure of the marginals. The results closely mirror those in the continuous case with a few exceptions. In this discrete setting we establish that Wasserstein barycenters must also be discrete measures and there is always a barycenter which is provably sparse. Moreover, for each Wasserstein barycenter there exists a non-mass-splitting optimal transport to each of the discrete marginals. Such non-mass-splitting transports do not generally exist between two discrete measures unless special mass balance conditions hold. This makes Wasserstein barycenters in this discrete setting special in this regard. We illustrate the results of our discrete barycenter theory with a proof-of-concept computation for a hypothetical transportation problem with multiple marginals: distributing a fixed set of goods when the demand can take on different distributional shapes characterized by the discrete marginal distributions. A Wasserstein barycenter, in this case, represents an optimal distribution of inventory facilities which minimize the squared distance/transportation cost totaled over all demands.

Description: In view of the recent financial crisis systemic risk has become a very important research object. It is of significant importance to understand what can be done from a regulatory point of view to make the financial system more resilient to global crises. Systemic risk measures can provide more insight on this aspect. The study of systemic risk measures should support central banks and financial regulators with information that allows for better decision making and better risk management. For this reason this paper studies systemic risk measures on locally convex-solid Riesz spaces. In our work we extend the axiomatic approach to systemic risk, as introduced in Chen et al. (Manag Sci 59(6):1373–1388, 2013 ), in different directions. One direction is the introduction of systemic risk measures that do not have to be positively homogeneous. The other direction is that we allow for a general measurable space whereas in Chen et al. ( 2013 ) only a finite probability space is considered. This extends the scope of possible loss distributions of the components of a financial system to a great extent and introduces more flexibility for the choice of suitable systemic risk measures.

Description: This article deals with constrained multi-objective optimization problems. The main purpose of the article is to investigate relationships between constrained and unconstrained multi-objective optimization problems. Under suitable assumptions (e.g., generalized convexity assumptions) we derive a characterization of the set of (strictly, weakly) efficient solutions of a constrained multi-objective optimization problem using characterizations of the sets of (strictly, weakly) efficient solutions of unconstrained multi-objective optimization problems. We demonstrate the usefulness of the results by applying it on constrained multi-objective location problems. Using our new results we show that special classes of constrained multi-objective location problems (e.g., point-objective location problems, Weber location problems, center location problems) can be completely solved with the help of algorithms for the unconstrained case.

Description: This paper studies continuous-time Markov decision processes with a denumerable state space, a Borel action space, bounded cost rates and possibly unbounded transition rates under the risk-sensitive finite-horizon cost criterion. We give the suitable optimality conditions and establish the Feynman–Kac formula, via which the existence and uniqueness of the solution to the optimality equation and the existence of an optimal deterministic Markov policy are obtained. Moreover, employing a technique of the finite approximation and the optimality equation, we present an iteration method to compute approximately the optimal value and an optimal policy, and also give the corresponding error estimations. Finally, a controlled birth and death system is used to illustrate the main results.

Description: Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization–idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives.

Description: In multi-objective optimization, one considers optimization problems with more than one objective function, and in general these objectives conflict each other. As the solution set of a multi-objective problem is often rather large and contains points of no interest to the decision-maker, strategies are sought that reduce the size of the solution set. One such strategy is to combine several objectives with each other, i.e. by summing them up, before employing tools to solve the resulting multi-objective optimization problem. This approach can be used to reduce the dimensionality of the objective space as well as to discard certain unwanted solutions, especially the ‘extreme’ ones found by minimizing just one of the objectives given in the classical sense while disregarding all others. In this paper, we discuss in detail how the strategy of combining objectives linearly influences the set of optimal, i.e. efficient solutions.

Description: Numerical dynamic programming algorithms typically use Lagrange data to approximate value functions over continuous states. Hermite data can be easily obtained from solving the Bellman equation and used to approximate the value functions. We illustrate the use of Hermite data with one-, three-, and six-dimensional examples. We find that Hermite approximation improves the accuracy in value function iteration (VFI) by one to three digits using little extra computing time. Moreover, VFI with Hermite approximation is significantly faster than VFI with Lagrange approximation for the same accuracy, and this advantage increases with the dimension of the continuous states.

Description: In this note, we give a geometrical decomposition of the equity core as a finite union of polyhedrons. As a consequence, we characterize the non-emptiness of the equity core (Selten in Decision theory and social ethics: issues in social choice, Reidel, Dordrecht, 289–301,   1978 ) and provide a method, easy to implement, for computing the Lorenz-maximal allocations in the equal division core (Dutta and Ray in Games Econ Behav 3:403–422, 1991 ).

Description: We study the asset allocation of a quadratic loss-averse (QLA) investor. First, we derive conditions under which the QLA problem is equivalent to the mean-variance (MV) and conditional value-at-risk (CVaR) problems. Then we solve analytically the two-asset problem of the QLA investor for one risk-free and one risky asset. We find that the optimal QLA investment in the risky asset is finite, strictly positive, and minimal with respect to the reference point for a value strictly larger than the risk-free rate. Finally, we implement the trading strategy of a QLA investor who reallocates her portfolio on a monthly basis using 13 EU and 13 US assets. Using risk-adjusted performance measures that do not target specific types of utility we find that QLA portfolios mostly outperform MV and CVaR portfolios; and that incorporating a conservative dynamic update of the QLA parameters, which is based on the historical patterns of bull and bear markets, improves the performance of QLA portfolios. Compared with linear loss-averse portfolios, QLA portfolios display significantly less risk but they also yield lower returns.

Description: The aim of this paper is to study the concept of properly efficient equilibrium for a multicriteria noncooperative strategic game. Using results of multicriteria optimization programming, we give some characterizations and existence results of this concept in the considered game.

Description: The sequential stochastic assignment problem (SSAP) allocates N workers to N IID sequentially arriving tasks so as to maximize the expected total reward. This paper studies two extensions of the SSAP. The first one assumes that the values of any two consecutive tasks are dependent on each other while the exact number of tasks to arrive is unknown until after the final arrival. The second extension generalizes the first one by assuming that the number of workers is also random. Optimal assignment policies for both problems are derived and proven to have the same threshold structure as the optimal policy of the SSAP.

Description: Limiting ratio average (undiscounted) reward finite (state and action spaces) semi-Markov decision processes (SMDPs) with absorbing states are considered where all but one states are absorbing. We propose a realistic inspection model that suitably fits into the class of undiscounted SMDPs with absorbing states. Existence of an optimal semi-stationary policy (i.e., a semi-Markov policy independent of decision epoch counts) is proved. A linear programming algorithm is provided to compute such an optimal policy.

Description: We consider a continuous time stochastic fluid model with alternating on- and off-periods. During on-periods the process increases linearly, during off periods there is an additional negative decrease rate, proportional to the content level. While the durations of the on-periods have an exponential distribution we allow for general distributions for the durations of the off-periods. We study the overflow time of the system and its behavior as the overflow level tends to infinity. Such systems can be related to queuing systems which switch between a one-server mode and phases with infinitely many available servers.

Description: We apply the well-known Condorcet criterion from voting theory outside of its classical framework and link it with spanning trees of an undirected graph. In situations in which a network, represented by a spanning tree of an undirected graph, needs to be installed, decision-makers typically do not agree on the network to be implemented. Instead, each of these decision-makers has her own ideal conception of the network. In order to derive a group decision, i.e., a single spanning tree for the entire group of decision-makers, the goal would be a spanning tree that beats each other spanning tree in a simple majority comparison. When comparing two dedicated spanning trees, a decision-maker will be considered to be more satisfied with the one that is “closer” to her proposal. In this context, the most basic and natural measure of distance is the usual set difference: we simply count the number of edges the spanning tree has in common with the proposal of the decision-maker. In this work, we show that it is computationally intractable to decide (1) if such a spanning tree exists, and (2) if a given spanning tree satisfies the Condorcet criterion.

Description: When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to nonconvex mixed-integer nonlinear optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several continuous reformulations of the problem. The applicability and relevance of different model formulations, especially of those without discrete variables, is demonstrated by a computational study on both academic examples and real-world instances. In addition, we provide preliminary computational results for an entire network.

Description: We study \(G/GI/N(+GI)\) queues with alternating renewal service interruptions in the Halfin–Whitt regime. The systems experience up and down alternating periods. In the up periods, the systems operate normally as the usual \(G/GI/N(+GI)\) queues with non-idling first-come–first-served service discipline. In the down periods, arrivals continue entering the systems, but all servers stop functioning while the amount of service that each customer has received will be conserved and services will resume when the next up period starts. For models with abandonment, interruptions do not affect customers’ patience times. We assume that the up periods are of the same order as the service times but the down periods are asymptotically negligible compared with the service times. We establish the functional central limit theorems for the queue-length processes and the virtual-waiting time processes in these models, where the limit processes are represented as stochastic integral convolution equations driven by jump processes. The convergence in these limit theorems is proved in the space \({\mathbb D}\) endowed with the Skorohod \(M_1\) topology.

Description: 〈h3〉Abstract〈/h3〉 〈p〉Blockwise coordinate descent methods have a long tradition in continuous optimization and are also frequently used in discrete optimization under various names. New interest in blockwise coordinate descent methods arises for improving sequential solutions for problems which consist of several planning stages. In this paper we systematically formulate and analyze the blockwise coordinate descent method for integer programming problems. We discuss convergence of the method and properties of the resulting solutions. We extend the notion of Pareto optimality for blockwise coordinate descent to the case that the blocks do not form a partition and compare Pareto optimal solutions to blockwise optimal and to global optimal solutions. Among others we derive a condition which ensures that the solution obtained by blockwise coordinate descent is weakly Pareto optimal and we confirm convergence of the blockwise coordinate descent to a global optimum in matroid polytopes. The results are interpreted in the context of multi-stage linear integer programming problems and illustrated for integrated planning in public transportation.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉This paper deals with decentralized decision-making situations in which firms outsource production orders to multiple identical suppliers. Each firm aims to minimize the sum of its completion times. We study whether a central authority can install a mechanism such that strategic interaction leads to a socially optimal schedule. For the case of single demand the shortest-first mechanism implements optimal schedules in Nash equilibrium. We show that for the general case there exists no anonymous mechanism that implements optimal schedules in correlated equilibrium.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In entry-exit gas markets as they are currently implemented in Europe, network constraints do not affect market interaction beyond the technical capacities determined by the TSO that restrict the quantities individual firms can trade at the market. It is an up to now unanswered question to what extent existing network capacity remains unused in an entry-exit design and to what extent feasible adjustments of the market design could alleviate inefficiencies. In this paper, we offer a four-level modeling framework that is capable of analyzing these issues and provide some first results on the model structure. In order to decouple gas trading from network congestion management, the TSO is required to determine technical capacities and corresponding booking fees at every entry and exit node up front. Firms book those capacities, which gives them the right to charge or discharge an amount of gas at a certain node up to this capacity in every scenario. Beyond these technical capacities and the resulting bookings, gas trade is unaffected by network constraints. The technical capacities have to ensure that transportation of traded quantities is always feasible. We assume that the TSO is regulated and determines technical capacities, fees, and transportation costs under a welfare objective. As a first step we moreover assume perfect competition among gas traders and show that the booking and nomination decisions can be analyzed in a single level. We prove that this aggregated model has a unique solution. We also show that the TSO’s decisions can be subsumed in one level as well. If so, the model boils down to a mixed-integer nonlinear bilevel problem with robust aspects. In addition, we provide a first-best benchmark that allows to assess welfare losses that occur in an entry-exit system. Our approach provides a generic framework to analyze various aspects in the context of semi-liberalized gas markets. Therefore, we finally discuss and provide guidance on how to include several important aspects into the approach, such as network and production capacity investment, uncertain data, market power, and intra-day trading.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉This paper studies optimal booking policies for capacity control models in revenue management with two substitutable resources. Our model covers a broader class of problems than previous works including (i) flexible demand and opaque selling for (ii) both dynamic and static demand settings. We provide a unifying characterization of the structure of optimal booking control by exploiting concavity, submodularity, and subconcavity of the value function. Our characterization is based on the notion of optimal “booking paths” formalizing the idea that an optimal allocation of a demand batch decomposes into a sequence of optimal single-request allocations. In addition, we examine the relationship between our booking path-based and a switching curve-based policy, which has been known previously for the case with dynamic demand. We show that both these characterizations describe an optimal policy. Computationally, there is no advantage of implementing either switching curves or booking paths in the dynamic setting. In the static setting, however, one can resort to the simple criteria which we propose in order to construct the optimal booking paths, thereby accelerating the evaluation of the value function.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We address the problem of finding conditions which guarantee the existence of open-loop Nash equilibria in discrete time dynamic games (DTDGs). A classical approach to DTDGs involves analyzing the problem using optimal control theory. Sufficient conditions for the existence of open-loop Nash equilibria obtained from this approach are mainly limited to linear-quadratic games (Başar and Olsder in Dynamic noncooperative game theory, 2nd edn, SIAM, Philadelphia, 〈span〉1999〈/span〉). Another approach of analysis is to substitute the dynamics and transform the game into a static game. But the substitution of state dynamics makes the objective functions of the resulting static problems extremely hard to analyze. We introduce a third approach in which the dynamics are not substituted, but retained as constraints in the optimization problem of each player, resulting thereby in a 〈em〉generalized Nash game〈/em〉. Using this, we give sufficient conditions for the existence of open-loop Nash equilibria for a class of DTDGs where the cost functions of players admit a 〈em〉quasi-potential〈/em〉 function. Our results apply with nonlinear dynamics and without stage additive cost functions, and allow constraints on state and actions spaces, and in some cases, yield a generalization of similar results from linear-quadratic games.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Single-peakedness was introduced by Black (J Political Econ 56:23–34, 1948) as a sufficient condition to overcome Condorcet paradox. Since then it has been attracting interest from researchers in various fields. In this paper, we propose a simple recursive procedure of constructing complete single-peaked domains of tiling type explicitly for any finite alternative sets, by combining two results published in recent years, and some observations of known results and examples by the author. The underlying basic structure of tiling type and properties of single-peaked domains provided here give a good visualization and make further developments on single-peakedness more easy.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider a supplier selling a product with a relatively short life cycle and following a non-increasing price curve. Because of the short cycle, there is a single procurement opportunity at the beginning of the cycle. The objective of the supplier is to determine the initial order quantity and the time to remove the product from the market in order to maximize her profits. We study this problem in a continuous-time framework where the demand is modeled with a non-homogeneous Poisson process having a general intensity function and the pricing strategy is given by an arbitrary non-increasing function. We give a rigorous mathematical analysis for the problem and show how it can be solved in two stages. We also consider the special case with piecewise constant intensity and price functions. For this case, we show that the optimal exit time is included in the set of break points of these functions. This brings a fast method to obtain the optimal solution for this special case.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Risk control is one of the crucial problems in finance. One of the most common ways to mitigate risk of an investor’s financial position is to set up a portfolio of hedging securities whose aim is to absorb unexpected losses and thus provide the investor with an acceptable level of security. In this respect, it is clear that investors will try to reach acceptability at the lowest possible cost. Mathematically, this problem leads naturally to considering set-valued maps that associate to each financial position the corresponding set of optimal hedging portfolios, i.e., of portfolios that ensure acceptability at the cheapest cost. Among other properties of such maps, the ability to ensure lower semicontinuity and continuous selections is key from an operational perspective. It is known that lower semicontinuity generally fails in an infinite-dimensional setting. In this note, we show that neither lower semicontinuity nor, more surprisingly, the existence of continuous selections can be a priori guaranteed even in a finite-dimensional setting. In particular, this failure is possible under arbitrage-free markets and convex risk measures.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We revisit the polyhedral projection problem. This problem has many applications, among them certain problems in global optimisation, polyhedral calculus, problems encountered in information theory and financial mathematics. In particular, it has been shown recently that polyhedral projection problems are equivalent to vector linear programmes (which contain multiple objective linear programmes as a sub-class). In this article, we develop a novel solution concept which provides more detailed insights into the structure of the projected polyhedron by taking its lineality space into account. We explore the relationship of our new solution concept to a previous one. We extend the problem class of vector linear programmes by using pre-orders instead of partial orders. We then show that solutions (according to the lattice approach) to such vector linear programmes can be derived by solving a related polyhedral projection problem.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we introduce a new concept of slope for a set-valued map using a scalarizing function defined with the help of the Hiriart-Urruty signed distance function. It turns out that this slope possesses most properties of the strong slope of a scalar-valued function. We present some applications in set optimization studied with Kuroiwa’s set approach. Namely, we obtain criteria for error bounds of a lower level set and the existence of weak optimal solutions under a Palais–Smale type condition.〈/p〉

Description: Consider the single-server queue in which customers are rejected if their total sojourn time would exceed a certain level \(K\) . A basic performance measure of this system is the probability \(P_K\) that a customer gets rejected in steady state. This paper presents asymptotic expansions for \(P_K\) as \(K\rightarrow \infty \) . If the service time \(B\) is light-tailed and inter-arrival times are exponential, it is shown that the loss probability has an exponential tail. The proof of this result heavily relies on results on the two-sided exit problem for Lévy processes with no positive jumps. For heavy-tailed (subexponential) service times and generally distributed inter-arrival times, the loss probability is shown to be asymptotically equivalent to the trivial lower bound \(P(B〉K)\) .

Description: This note concerns discrete-time controlled Markov chains driven by a decision maker with constant risk-sensitivity \(\lambda \) . Assuming that the system evolves on a denumerable state space and is endowed with a bounded cost function, the paper analyzes the continuity of the optimal average cost with respect to the risk-sensitivity parameter, a property that is promptly seen to be valid at each no-null value of \(\lambda \) . Under standard continuity-compactness conditions, it is shown that a general form of the simultaneous Doeblin condition allows to establish the continuity of the optimal average cost at \(\lambda = 0\) , and explicit examples are given to show that, even if every state is positive recurrent under the action of any stationary policy, the above continuity conclusion can not be ensured under weaker recurrence requirements, as the Lyapunov function condition.

Description: This paper extends the notion of individual minimal rights for a transferable utility game (TU-game) to coalitional minimal rights using minimal balanced families of a specific type, thus defining a corresponding minimal rights game. It is shown that the core of a TU-game coincides with the core of the corresponding minimal rights game. Moreover, the paper introduces the notion of the \(k\) -core cover as an extension of the core cover. The \(k\) -core cover of a TU-game consists of all efficient payoff vectors for which the total joint payoff for any coalition of size at most \(k\) is bounded from above by the value of this coalition in the corresponding dual game, and from below by the value of this coalition in the corresponding minimal rights game. It is shown that the core of a TU-game with player set \(N\) coincides with the largest integer below or equal to \(\frac{|N|}{2}\) -core cover. Furthermore, full characterizations of games for which a \(k\) -core cover is nonempty and for which a \(k\) -core cover coincides with the core are provided.

Description: We deal with discounted ARAT stochastic games on a Borel state space with finite action spaces and nonatomic transition probabilities. We prove the existence of pure Nash equilibria in stationary almost Markov strategies that depend only on the current and previous state of the game. Our proof is based on an existence theorem for correlated equilibria in stochastic games and some results on the integrals of set-valued mappings with respect to a probability measure depending on a parameter.

Description: We consider the single-leg airline revenue management problem in continuous time with Poisson arrivals. Earlier work on this problem generally uses the Hamilton–Jacobi–Bellman equation to find an optimal policy whenever the value function is differentiable and is a solution to this equation. In this paper, we employ a different probabilistic approach, which does not rely on the smoothness of the value function. Instead, we use a continuous-time discrete-event dynamic programming operator to construct the value function and study its properties. A by-product of this approach is the analysis of the differentiability of the value function. We show that differentiability may break down for example with discontinuous arrival intensities. Therefore, one should exercise caution in using arguments based on the differentiability of the value function and the Hamilton–Jacobi–Bellman equation in general.

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the stochastic queue core problem on a tree network. Our aim is to find an optimal path on a tree network subject to the average travel time of particles moving along the tree for service given by a server traversing along the optimal path. We assume that particles originating at a node on a tree network request their demands for service randomly and the server is modeled first by an M/M/1 and then by an M/G/1 queue using the FIFO discipline. We consider that all paths along which the particles travel are modeled with an M/G/c/c state-dependent queue with the particles being independent of each other having demands according to the Poisson distribution. Two algorithms are developed for computing the optimal path on a tree network along with the M/M/1 and the M/G/1 queues. The computational complexity of the algorithms and illustrative numerical results obtained by implementations of the algorithms in MATLAB software environment are given.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Sparse optimization problems have gained much attention since 2004. Many approaches have been developed, where nonconvex relaxation methods have been a hot topic in recent years. In this paper, we study a partially sparse optimization problem, which finds a partially sparsest solution of a union of finite polytopes. We discuss the relationship between its solution set and the solution set of its nonconvex relaxation. In details, by using geometrical properties of polytopes and properties of a family of well-defined nonconvex functions, we show that there exists a positive constant 〈span〉 〈span〉\(p^*\in (0,1]\)〈/span〉 〈/span〉 such that for every 〈span〉 〈span〉\(p\in [0,p^*)\)〈/span〉 〈/span〉, all optimal solutions to the nonconvex relaxation with the parameter 〈em〉p〈/em〉 are also optimal solutions to the original sparse optimization problem. This provides a theoretical basis for solving the underlying problem via its nonconvex relaxation. Moreover, we show that the problem we concerned covers a wide range of problems so that several important sparse optimization problems are its subclasses. Finally, by an example we illustrate our theoretical findings.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Consider 〈em〉n〈/em〉 firms (agents) located at a river, indexed by 〈span〉 〈span〉\(1, \dots , n\)〈/span〉 〈/span〉 from upstream to downstream. The pollution generated by these firms induce cleaning costs 〈span〉 〈span〉\(c_1, \dots , c_n\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(c_i\)〈/span〉 〈/span〉 is the cost for cleaning the water in region 〈em〉i〈/em〉 (according to the local environmental standards). The corresponding cost allocation problem is highly interesting both in theory and practice. Among the most prominent allocation schemes are the so-called Local Responsibility and Upstream Equal Sharing. The first one allocates simply each local cost 〈span〉 〈span〉\(c_i\)〈/span〉 〈/span〉 to the corresponding firm 〈em〉i〈/em〉. The second distributes each 〈span〉 〈span〉\(c_i\)〈/span〉 〈/span〉 equally among firms 〈span〉 〈span〉\(1, \dots , i\)〈/span〉 〈/span〉. We propose and characterize a dynamic scheme which, given a particular order of arrival, allocates the current total cost among the firms that have arrived so far. The corresponding expected allocation (〈em〉w.r.t.〈/em〉 a random arrival order) turns out to be a convex combination of the two schemes above. 〈/p〉