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: In this paper, we introduce the selfish bin packing problem under a new version of cost sharing mechanism based on harmonic mean. The items (as agents) are selfish and intelligent to minimize the cost they have to pay, by selecting a proper bin to fit in. The tricky part is that the one with bigger size pays less and vice versa. We present the motivations and prove the existence of pure Nash Equilibrium under this new defined cost sharing mechanism. Then we study the Price of Anarchy, which is the ratio between the objective value of worst Nash Equilibrium and that of the optimum in the case with central decision maker. We prove the upper bound to be approximately 1.722 and show a 5/3 lower bound for this problem. We then include punishment into the model and prove that in this new model, the Price of Anarchy could be decreased to 3/2. PubDate: 2022-06-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: It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit constraint functions that cannot be solved for any parameter analytically. For this class of mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear function—in contrast to an approximation of the graph of the function considered in prior work. This method is shown to compute approximate global optimal solutions in finite time and we also provide a worst-case iteration bound. In some first numerical experiments we show that the “cost of not knowing enough” is rather high by comparing our approach with the open-source global solver SCIP. This reveals that a lot of work is still to be done for this highly challenging class of problems and we thus finally propose some possible directions of future research. PubDate: 2022-06-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: This paper is devoted to the investigation of a class of uncertain multiobjective fractional semi-infinite optimization problems ( \(UMFP \) , for brevity). We first obtain, by combining robust optimization and scalarization methodologies, necessary and sufficient optimality conditions for robust approximate weakly efficient solutions of ( \(UMFP \) ). Then, we introduce a Mixed type approximate dual problem for ( \(UMFP \) ) and investigate their robust approximate duality relationships. Moreover, we obtain some robust approximate weak saddle point theorems for an uncertain multiobjective Lagrangian function related to ( \(UMFP \) ). PubDate: 2022-06-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: A perfect matching in a hypergraph is a set of edges that partition the set of vertices. We study the complexity of deciding the existence of a perfect matching in orderable and separable hypergraphs. We show that the class of orderable hypergraphs is strictly contained in the class of separable hypergraphs. Accordingly, we show that for each fixed k, deciding perfect matching for orderable k-hypergraphs is polynomial time doable, but for each fixed \(k\ge 3\) , it is NP-complete for separable hypergraphs. PubDate: 2022-06-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: The vertex 3-colourability problem is to decide whether the vertex set of a given graph can be split into three subsets of pairwise non-adjacent vertices. This problem is known to be NP-complete in a certain class of graphs, defined by an explicit description of allowed 5-vertex induced subgraphs in them. In the present paper, we improve this result by showing that the vertex 3-colourability problem remains NP-complete for a reduced set of allowed 5-vertex induced structures. It gives a step towards obtaining a complete complexity dichotomy for the mentioned problem and all the classes, defined by 5-vertex forbidden induced prohibitions. PubDate: 2022-06-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: In this paper, we introduce and investigate a new regularity condition in the asymptotic sense for optimization problems whose objective functions are polynomial. The normalization argument in asymptotic analysis enables us to study the existence as well as the stability of solutions of these problems. We prove a Frank–Wolfe type theorem for regular optimization problems and an Eaves type theorem for non-regular pseudoconvex optimization problems. Moreover, under the regularity condition, we show results on the stability such as upper semicontinuity and local upper-Hölder stability of the solution map of polynomial optimization problems. At the end of the paper, we discuss the genericity of the regularity condition. PubDate: 2022-06-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: This paper analyzes a variant of Online Bipartite Matching in which incoming jobs must be matched to some worker, even if there are no available edges. A reward is only gained for matchings that are made across some edge. This paper gives matching upper and lower bounds for the most general version of this variation. It then provides an optimal policy for this problem when the underlying bipartite graph meets certain conditions and then identifies the most general conditions under which this policy is guaranteed to be optimal. PubDate: 2022-06-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: Several applications in medical imaging and non-destructive material testing lead to inverse elliptic coefficient problems, where an unknown coefficient function in an elliptic PDE is to be determined from partial knowledge of its solutions. This is usually a highly non-linear ill-posed inverse problem, for which unique reconstructability results, stability estimates and global convergence of numerical methods are very hard to achieve. The aim of this note is to point out a new connection between inverse coefficient problems and semidefinite programming that may help addressing these challenges. We show that an inverse elliptic Robin transmission problem with finitely many measurements can be equivalently rewritten as a uniquely solvable convex non-linear semidefinite optimization problem. This allows to explicitly estimate the number of measurements that is required to achieve a desired resolution, to derive an error estimate for noisy data, and to overcome the problem of local minima that usually appears in optimization-based approaches for inverse coefficient problems. PubDate: 2022-06-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: The purpose of this article is to establish some results on the existence and generic stability of solution sets of the controlled system for multiobjective generalized games in infinite-dimensional spaces. First, we introduce a class of the controlled system for multiobjective generalized games. Afterward, we establish some conditions for existence of the solution set to this problem using the Kakutani–Fan–Glicksberg fixed-point theorem. Finally, we study the generic stability of set-valued mappings where the set of essential points of a map is a dense residual subset of a (Hausdorff) metric space of the set-valued maps. The results presented in the paper are new and completely different from the main results given by some authors in the literature. PubDate: 2022-06-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: We present an algorithm to solve capacity extension problems that frequently occur in energy system optimization models. Such models describe a system where certain components can be installed to reduce future costs and achieve carbon reduction goals; however, the choice of these components requires the solution of a computationally expensive combinatorial problem. In our proposed algorithm, we solve a sequence of linear programs that serve to tighten a budget—the maximum amount we are willing to spend towards reducing overall costs. Our proposal finds application in the general setting where optional investment decisions provide an enhanced portfolio over the original setting that maintains feasibility. We present computational results on two model classes, and demonstrate computational savings up to 96% on certain instances. PubDate: 2022-06-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: In this paper, to economically and fast solve the linear complementarity problem, based on a new equivalent fixed-point form of the linear complementarity problem, we establish a class of new modulus-based matrix splitting methods, which is different from the previously published works. Some sufficient conditions to guarantee the convergence of this new iteration method are presented. Numerical examples are offered to show the efficacy of this new iteration method. Moreover, the comparisons on numerical results show the computational efficiency of this new iteration method advantages over the corresponding modulus method, the modified modulus method and the modulus-based Gauss–Seidel method. PubDate: 2022-06-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: Mathematical approaches, such as compartmental models and agent-based models, have been utilized for modeling the spread of the infectious diseases in the computational epidemiology. However, the role of social network structure for transmission of diseases is not explicitly considered in these models. In this paper, the influence maximization problem, considering the diseases starting at some initial nodes with the potential to maximize the spreading in a social network, is adapted to model the spreading process. This approach includes the analysis of network structure and the modeling of connections among individuals with probabilities to be infected. Additionally, individual behaviors that change along the time and eventually influence the spreading process are also included. These considerations are formulated by integer optimization models. Simulation results, based on the randomly generated networks and a local community network under the COVID-19, are performed to validate the effectiveness of the proposed models, and their relationships to the classic compartmental models. PubDate: 2022-06-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: First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the \(\epsilon \) -scaling auction algorithm, the Hungarian algorithm and the FlowAssign algorithm. The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity. PubDate: 2022-06-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: Owing to treatment complexity in chemotherapy administration, nurses are usually required at the beginning, end, and at certain times during the treatment period to ensure high-quality infusion. It is, thus, critical for an outpatient chemotherapy unit to design a scheduling template that can effectively match nursing resources with treatment requirements. The template contains appointment slots of different lengths and thus allows schedulers to place patients into these slots according to the provider’s order. As the template is often used over a period of several months, there usually exists a mismatch between the daily patient mix and the fixed structure of the given template. Hence, override policies must be employed to adjust to demand. However, these policies are often manually performed by schedulers. We propose a mixed-integer linear programming model to systematically develop optimal override policies in place of the manual process to improve template utilization while maintaining template stability. Numerical experiments based on real-life data from a chemotherapy unit are conducted to demonstrate the effectiveness of the proposed approach. PubDate: 2022-06-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: The bin packing problem with divisible item sizes and rejection penalties (the BP–DR problem, for short) is defined as follows. Given a lot of bins with same capacity limitation L and a set \(X=\{x_{1},\ldots ,x_{n}\}\) of items with a size function \(s: X\rightarrow Z^{+}\) and a penalty function \(p:X\rightarrow R^{+}\) , where the item sizes are divisible, i.e., either \(s(x_{i}) s(x_{j})\) or \(s(x_{j}) s(x_{i})\) for any two items \(x_{i}\) and \(x_{j}\) with \(1\le i < j\le n\) , each of these n items must be either put into a bin under the constraint that the summation of sizes of items in that bin does not exceed L, or rejected with its penalty that we must pay for. No item can be spread into more than one bin. We consider the BP–DR problem and its important variant. (1) The BP–DR problem is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above, the objective is to minimize the number of bins used plus the summation of penalties paid for the rejected items, and (2) Given a penalty budget \(B\in R^{+}\) , the bin packing problem with divisible item sizes and bounded rejection penalties (the BP–DBR problem, for short) is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above and that the summation of penalties paid for the rejected items does not exceed B, the objective is to minimize the number of bins used. In this paper, we design two exact combinatorial algorithms to solve the BP–DR problem and the BP–DBR problem, respectively. PubDate: 2022-06-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: A proximal bundle algorithm is proposed for solving unconstrained nonsmooth nonconvex optimization problems. At each iteration, using already generated information, the algorithm defines a convex model of the augmented objective function. Then by solving a quadratic subproblem a new candidate iterate is obtained and the algorithm is repeated. The novelty in our approach is that the objective function can be any arbitrary locally Lipschitz function without any additional assumptions. The global convergence, starting from any point, is also studied. At the end, some encouraging numerical results with a MATLAB implementation are reported. PubDate: 2022-06-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: This paper investigates the collaborative scheduling problem of research and development (R&D) and manufacturing processes in the context of high-end equipment, and the objective is to minimize the makespan. A unique feature is the dual usage of a limited resource budget, which can increase the quantity of both researchers and assembly lines. This brings new challenges to resource allocation and related collaborative scheduling. A mixed-integer programming model is formulated and further simplified based on the network structure, and the CPLEX solver is used to obtain the optimal solutions for the simplified model with the small-scale cases. Furthermore, an improved Variable Neighborhood Search (IVNS) algorithm is developed to obtain the near-optimal solutions for small-scale and large-scale cases. The neighborhood structure operates the R&D and manufacturing parts of solution. Variable neighborhood descent with different amount and sequence of neighborhood structures is designed to enhance the effectiveness and efficiency of the proposed algorithm. Computational experiments are conducted to evaluate the performance of the proposed algorithm. The experimental results show that the proposed algorithm performs well in terms of the solution quality and running time. PubDate: 2022-05-09
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: We analyze the stochastic proximal subgradient descent in the case where the objective functions are path differentiable and verify a Sard-type condition. While the accumulation set may not be reduced to unique point, we show that the time spent by the iterates to move from one accumulation point to another goes to infinity. An oscillation-type behavior of the drift is established. These results show a strong stability property of the proximal subgradient descent. Using the theory of closed measures, Bolte et al. (2020) established this type of behavior for the deterministic subgradient descent. Our technique of proof relies on the classical works on stochastic approximation of differential inclusions, which allows us to extend results in the deterministic case to a stochastic and proximal setting, as well as to treat these different cases in a unified manner. PubDate: 2022-05-06
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 concerns with the problem of estimating the transition matrix of a low-rank discrete-state Markov model from its state-transition trajectories. We propose a low-rank spectral method via the best rank-r approximation of the spectral estimator based on the matrix elementwise \(l_q (q\ge 1)\) norm distance. Specifically, we establishing the Lipschitzian type error bound for the rank-constrained transition matrix set. Then, we prove a statistical upper bound for the estimation error of the proposed estimator. Numerical comparisons with the rank-constrained maximum likelihood estimator which computed by DC (difference of convex function) programming algorithm (Zhu et al. in Oper Res, 2021. https://doi.org/10.1287/opre.2021.2115) illustrate the merits of the proposed estimator in terms of the recoverability and the required computing time. PubDate: 2022-05-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 consider a class of bilevel programming problems (BPPs) where the leader’s decision variables are all binary, the follower’s decision variables are all continuous, and a fractional objective function appears in the follower’s problem. This class of problems generalizes standard bilevel linear mixed-integer programs with a linear program (LP) in the lower level. One motivating application example for this generalization arises in a network interdiction context, where the follower (i.e., the evader) instead of minimizing his/her shortest path, optimizes some fractional objective function, e.g., a cost-to-time ratio. By applying Charnes-Cooper transformation, we first reformulate the original BPP as an equivalent BPP with a fractional objective in the upper level, but an LP in the lower level. Using a combination of the LP strong-duality property and linearization techniques, we show how to address the resulting reformulation via a parametric approach that solves a sequence of linear mixed-integer programs. The latter can be handled by off-the-shelf solvers, which implies that our overall solution scheme is easy to implement. Finally, we perform a brief computational study to illustrate the performance of the proposed approaches. PubDate: 2022-05-04
Hybrid journal (It can contain Open Access articles)
