Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In a recent paper (Lv and Wang, Study on proportionate flowshop scheduling with due-date assignment and position-dependent weights. Optim. Lett., 2021. https://doi.org/10.1007/s11590-020-01670-4), Lv and Wang studied due date proportionate flowshop scheduling problems with position-dependent weights. For common due date and slack due date assignments, they proved that these two problems can be solved in \(O(n\log n)\) time respectively, where n is the number of jobs. For slack due date assignment, there is an error. We will show the error by a counter example and explain why it is incorrect. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract More than three decades ago, Boyd and Balakrishnan established a regularity result for the two-norm of a transfer function at maximizers. Their result extends easily to the statement that the maximum eigenvalue of a univariate real analytic Hermitian matrix family is twice continuously differentiable, with Lipschitz second derivative, at all local maximizers, a property that is useful in several applications that we describe. We also investigate whether this smoothness property extends to max functions more generally. We show that the pointwise maximum of a finite set of q-times continuously differentiable univariate functions must have zero derivative at a maximizer for \(q=1\) , but arbitrarily close to the maximizer, the derivative may not be defined, even when \(q=3\) and the maximizer is isolated. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Two-stage stochastic programming is a mathematical framework widely used in real-life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision makers make use of numerical methods to obtain a near-optimal solution. Some applications rely on the implementation of non-converged and therefore sub-optimal solutions because of computational time or power limitations. In this context, the existing partition-refinement methods provide an optimistic solution whenever convergence is not attained. Optimistic solutions often generate high disappointment levels because they consistently underestimate the actual costs in the approximate objective function. To address this issue, we developed a conservative convergent partition-refinement method for two-stage stochastic linear programming problems with a convex recourse function of the uncertainty. Given a partition of the uncertainty support, a conservative decision can be obtained by means of a distributionally robust problem whose complexity grows exponentially with the uncertainty dimensionality. We prove the convergence of the method given a refining partition sequence and propose algorithmic schemes to address the problem of dimensionality. For problems with low-dimensional uncertainty, we developed a deterministic equivalent linear programming model; whereas, for medium-sized uncertainty dimensionality, we propose a column and constraint generation algorithm. To handle high dimensional uncertainty, we propose a simplex-based heuristic method whose complexity grows linearly with the uncertainty dimension—size of the random vector. In the presence of monotone recourse functions with regard to an uncertain parameter, we prove convergence of the proposed simplex-based heuristic method. Computational experiments are presented for a farmer’s problem, an aircraft allocation problem, and a Unit Commitment problem. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, a robust inventory problem with uncertain cumulative demands is considered. Interval-budgeted uncertainty sets are used to model possible cumulative demand scenarios. It is shown that under discrete budgeted uncertainty the robust min–max problem can be solved in polynomial time. On the other hand, for continuous budgeted uncertainty, the problem is weakly NP-hard. It can be solved in pseudopolynomial time and admits an FPTAS for nonoverlapping cumulative demand intervals. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We derive a linear program for minimization, subject to a linear constraint, of an arbitrary positively homogeneous convex functional, whose dual set is given by linear inequalities, possibly involving auxiliary variables. This allows to reduce to linear programming individual and cooperative portfolio optimization problems with arbitrary deviation measures whose risk envelopes are given by a finite number of linear constraints. Earlier, such linear programs were known only for individual porfolio optimization problems with special examples of deviation measures, such as mean absolute deviation or CVaR deviation. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We propose and analyze the convergence of a novel stochastic algorithm for solving monotone inclusions that are the sum of a maximal monotone operator and a monotone, Lipschitzian operator. The propose algorithm requires only unbiased estimations of the Lipschitzian operator. We obtain the rate \({\mathcal {O}}(log(n)/n)\) in expectation for the strongly monotone case, as well as almost sure convergence for the general case. Furthermore, in the context of application to convex–concave saddle point problems, we derive the rate of the primal–dual gap. In particular, we also obtain \({\mathcal {O}}(1/n)\) rate convergence of the primal–dual gap in the deterministic setting. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we consider a single machine parallel batch scheduling problem subject to chains of jobs. We present polynomial lower and upper bounds as well as their experimental comparison and relative errors. According to the results of the numerical experiment, the relative difference between upper and lower bounds does not exceed 1.5. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper studies a model for cooperative congestion games. There is an array of cooperative games V and a player’s strategy is to choose a subset of the set V. The player gets a certain payoff from each chosen game. The paper demonstrates that if a payoff is the Shapley or the Banzhaf value, then the corresponding cooperative congestion game has a Nash equilibrium in pure strategies. The case is examined where each game in V has a coalition partition. The stability of the vector of coalition structures is determined, taking into account the transitions of players within a game and their migrations to other games. The potential function is defined for coalition partitions, and is used as a means of proving the existence of a stable vector of coalition structures for a certain class of cooperative game values. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The two-stage stochastic variational inequality (TSVI) is a popular modeling paradigm recently with a wide range of applications in stochastic programming, game problems, equilibrium, etc. To numerically solve a TSVI, samples drawn from the true probability distribution are employed to discretely approximate the original problem with continuous probability distribution. However, this key assumption can hardly be fulfilled in practice because the perceived data may usually contain noise. This leads to the so-called statistically robust analysis. This paper considers the statistical robustness of TSVIs. We first give some preliminaries on both TSVIs and statistical robustness, which lay the foundation for the subsequent discussion. Then both qualitative and quantitative statistical robustness of TSVIs are studied. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we introduce three classes of structured tensor: QN-tensor, S-QN tensor and generalized S-QN tensor, which are proved to be nonsingular \({\mathcal {H}}\) -tensors. Moreover, we present the upper bound for the norm of the solution of TCP \(({{\mathcal {A}}},q)\) defined by a nonsingular \({\mathcal {H}}\) -tensor with positive diagonal entries. The estimation of upper bound requires a diagonal scaling matrix D such that \({{\mathcal {A}}}\cdot D\) is strictly diagonally dominant. When \({{\mathcal {A}}}\) belongs to the set of QN-tensor or S-QN tensor, a choice for the diagonal scaling matrix is given. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this article, we investigate the convergence rate of the following dynamic system in \({\mathbb {R}}^{n}\) $$\begin{aligned} \ddot{x}(t)+\frac{A}{t^\theta }{\dot{x}}(t)+\nabla F(x(t))=0,\quad t>0, \end{aligned}$$ where A denotes the constant positive definite matrix and the potential function \(F:{\mathbb {R}}^n\rightarrow {\mathbb {R}}\) is continuous differentiable. This system is of vital importance, especially in optimization and engineering. This article presents new convergence rates of the above dynamics when F(x) satisfies some local geometrical properties by constructing a proper Lyapunov function. Finally, some numerical experiments were performed to explain the convergence results. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we study the multi-depot k-traveling repairman problem. This problem extends the traditional traveling repairman problem to the multi-depot case. Its objective, similar to the single depot variant, is the minimization of the sum of the arrival times to customers. We propose two distinct formulations to model the problem, obtained on layered graphs. In order to find feasible solutions for the largest instances, we propose a hybrid genetic algorithm where initial solutions are built using a splitting heuristic and a local search is embedded into the genetic algorithm. The efficiency of the mathematical formulations and of the solution approach are investigated through computational experiments. The proposed models are scalable enough to solve instances up to 240 customers. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract More than half a century ago Martin Gardner popularized a question leading to the benchmark problem of determining the minimum side length of a square into which the squares of sizes \(1,2,\dots ,n\) can be packed without overlap. Constructions are known for a certain range of n, and summing up the areas yields that a packing in a square of size smaller than \(N:= \!\sqrt{n(n+1)(2n+1)/6)} \) is not possible. Here we prove that an asymptotically minimal packing exists in a square of size \(N+cn+O(\!\sqrt{n})\) with \(c<1\) , and such a packing is achievable with guillotine-cuts. An improved construction is also given for the case where the constraint of guillotine cutting is dropped. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We investigate the properties of robust solutions of the Capacitated Facility Location Problem with uncertain demand. We show that the monotonic behavior of the price of robustness is not guaranteed, and therefore that one cannot discriminate among alternative robust solutions by simply relying on the trade-off price-vs-robustness. Furthermore, we report a computational study on benchmark instances from the literature and on instances derived from a real-world application, which demonstrates the validity in practice of our findings. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We develop a Nash equilibrium problem representing a perfectly competitive market wherein all players are subject to the same source of uncertainty with an unknown probability distribution. Each player—depending on her individual access to and confidence over empirical data—builds an ambiguity set containing a family of potential probability distributions describing the uncertain event. The ambiguity set of different players is not necessarily identical, yielding a market with potentially heterogeneous ambiguity aversion. Built upon recent developments in the field of Wasserstein distributionally robust chance-constrained optimization, each ambiguity-averse player maximizes her own expected payoff under the worst-case probability distribution within her ambiguity set. Using an affine policy and a conditional value-at-risk approximation of chance constraints, we define a tractable Nash game. We prove that under certain conditions a unique Nash equilibrium point exists, which coincides with the solution of a single optimization problem. Numerical results indicate that players with comparatively lower consumption utility are highly exposed to rival ambiguity aversion. PubDate: 2022-11-19
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We explore novel approaches for solving nonlinear optimization problems with unrelaxable bound constraints, which must be satisfied before the objective function can be evaluated. Our method reformulates the unrelaxable bound-constrained problem as an unconstrained optimization problem that is amenable to existing unconstrained optimization methods. The reformulation relies on a domain warping to form a merit function; the choice of the warping determines the level of exactness with which the unconstrained problem can be used to find solutions to the bound-constrained problem, as well as key properties of the unconstrained formulation such as smoothness. We develop theory when the domain warping is a multioutput sigmoidal warping, and we explore the practical elements of applying unconstrained optimization methods to the formulation. We develop an algorithm that exploits the structure of the sigmoidal warping to guarantee that unconstrained optimization algorithms applied to the merit function will find a stationary point to the desired tolerance. PubDate: 2022-11-13
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a graph \(G=(V,E)\) and a set C of unordered pairs of edges regarded as being in conflict, a stable spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each \(\left\{ e_i, e_j \right\} \in C\) , at most one of the edges \(e_i\) and \(e_j\) is in T. The existing work on Lagrangean algorithms to the NP-hard problem of finding minimum weight stable spanning trees is limited to relaxations with the integrality property. We exploit a new relaxation of this problem: fixed cardinality stable sets in the underlying conflict graph \(H =(E,C)\) . We find interesting properties of the corresponding polytope, and determine stronger dual bounds in a Lagrangean decomposition framework, optimizing over the spanning tree polytope of G and the fixed cardinality stable set polytope of H in the subproblems. This is equivalent to dualizing exponentially many subtour elimination constraints, while limiting the number of multipliers in the dual problem to E . It is also a proof of concept for combining Lagrangean relaxation with the power of integer programming solvers over strongly NP-hard subproblems. We present encouraging computational results using a dual method that comprises the Volume Algorithm, initialized with multipliers determined by Lagrangean dual-ascent. In particular, the bound is within 5.5% of the optimum in 146 out of 200 benchmark instances; it actually matches the optimum in 75 cases. All of the implementation is made available in a free, open-source repository. PubDate: 2022-11-11
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We propose a simple variant of the generalized Frank–Wolfe method for solving strongly convex composite optimization problems, by introducing an additional averaging step on the dual variables. We show that in this variant, one can choose a simple constant step-size and obtain a linear convergence rate on the duality gaps. By leveraging the convergence analysis of this variant, we then analyze the local convergence rate of the logistic fictitious play algorithm, which is well-established in game theory but lacks any form of convergence rate guarantees. We show that, with high probability, this algorithm converges locally at rate O(1/t), in terms of certain expected duality gap. PubDate: 2022-11-07
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper introduces the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem, a new variant of the well-known Vehicle Routing Problem. It is a real-world problem originating from the policies of a Nordic distribution company. The problem includes a single depot, a non-predetermined hierarchy of intermediate facilities, and two different fleets, consisting of homogeneous original and homogeneous local vehicles, which are pulling swap-bodies. Original vehicles with attached swap-bodies depart from the central depot. They can either visit customers directly if only one swap-body is attached or visit one or two consecutive switch points in order to transfer one or two loaded swap-bodies to a corresponding number of local vehicles, which are subsequently routed to customers while the original vehicle itself proceeds to serve customers with the remaining loaded swap-body. A mixed-integer formulation of the problem is proposed. A short bibliographic review, relations, shared characteristics, and differences of the proposed variant and several known VRP variants are analyzed and discussed. The solution of an illustrative instance is presented in order to demonstrate the solution concept for the problem as well as to compare with solution concepts for previously stated VRP variants. Computational experiments on small instances that could be solved within one hour are also presented. The problem is computationally hard to solve. Thus, the development of heuristics and metaheuristics is an important future task in order to enable solution of real case instances or instances of realistic sizes. PubDate: 2022-11-05
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We present a computational study of SDP-based bounds for Max-Cut that use a subset of hypermetric inequalities as cutting planes to strengthen the basic relaxation. Solving these relaxations is computationally challenging due to the potentially large number of violated constraints. To overcome these difficulties, we describe a heuristic separation algorithm for hypermetric inequalities and propose to use the augmented Lagrangian method as a bounding routine. Computational experiments show that the resulting relaxations provide very tight bounds for the Max-Cut. PubDate: 2022-11-04
Hybrid journal (It can contain Open Access articles)
