Abstract: Abstract This paper presents three reformulations for the well-known maximum capture location problem under multinomial logit choice. The problem can be cast as an integer fractional program and it has been the subject of several linear reformulations in the past. Here we develop two linear and a conic reformulation based on alternative treatments of fractional programs. Numerical experiments conducted on established sets of instances have shown that conic reformulation has greatly improved the solution times as well as the size of the solvable problems as compared to the most successful reformulations to date. PubDate: 2021-01-20

Abstract: Abstract Given the costs and a feasible solution for a finite-dimensional linear program (LP), inverse optimization involves finding new costs that are close to the original and that also render the given solution optimal. Ahuja and Orlin employed the absolute sum norm and the maximum absolute norm to quantify distances between cost vectors, and applied duality to establish that the inverse LP problem can be formulated as another finite-dimensional LP. This was recently extended to semi-infinite LPs, countably infinite LPs, and finite-dimensional conic optimization problems. These works provide sufficient conditions so that the inverse problem also belongs to the same class as the forward problem. This paper extends this result to conic LPs in potentially infinite-dimensional Banach spaces. Moreover, the paper presents concrete derivations for continuous conic LPs, whose special cases include continuous linear programs and continuous conic programs; normed cone programs in Banach spaces, which include second-order cone programs as a special case; and semi-definite programs in Hilbert spaces. These derivations reveal the sharper result that, in each case, the inverse problem belongs to the same specific subclass as the forward problem. Instances where existing forward algorithms can then be adapted to solve the inverse problems are identified. Results in this paper may enable the application of inverse optimization to as yet unexplored areas such as continuous-time economic planning, continuous-time job-shop scheduling, continuous-time network flow, maximum flow with time-varying edge-capacities, and wireless optimization with time-varying coverage requirements. PubDate: 2021-01-19

Abstract: Abstract This paper studies an n-player non-cooperative game where each player has expected-value payoff function and chance-constrained strategy set. We consider the case where the row vectors defining the constraints are independent random vectors whose probability distributions are not completely known and belong to a certain distributional uncertainty set. The chance-constrained strategy sets are defined using a distributionally robust framework. We consider one density based uncertainty set and four two-moments based uncertainty sets. One of the considered uncertainty sets is based on a nonnegative support. Under the standard assumptions on the players’ payoff functions, we show that there exists a Nash equilibrium of a distributionally robust chance-constrained game for each uncertainty set. As an application, we study Cournot competition in electricity market and perform the numerical experiments for the case of two electricity firms. PubDate: 2021-01-19

Abstract: Abstract In this paper, we study the k-level facility location problem with outliers (k-LFLPWO), which is an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility location sets, a client location set of cardinality n and a non-negative integer \(q<n\) . Every facility location set has a different level which belongs to \(\{1, 2,\ldots , k\}\) . For any facility location, there is an opening cost. For any two locations, there is a connecting cost. We wish to connect at least \(n-q\) clients to opened facilities from level 1 to level k, such that the total cost including opening costs and connecting costs is minimized. Our main contribution is to present a 6-approximation algorithm, which is based on the technique of primal-dual, for the k-LFLPWO. PubDate: 2021-01-19

Abstract: Abstract In this paper, we develop optimality conditions and propose an algorithm for generalized fractional programming problems whose objective function is the maximum of finite ratios of difference of convex (dc) functions, with dc constraints, that we will call later, DC-GFP. Such problems are generally nonsmooth and nonconvex. We first give in this work, optimality conditions for such problems, by means of convex analysis tools. For solving DC-GFP, the use of Dinkelbach-type algorithms conducts to nonconvex subproblems, which causes the failure of the latter since it requires finding a global minimum for these subprograms. To overcome this difficulty, we propose a DC-Dinkelbach-type algorithm in which we overestimate the objective function in these subproblems by a convex function, and the constraints set by an inner convex subset of the latter, which leads to convex subproblems. We show that every cluster point of the sequence of optimal solutions of these subproblems satisfies necessary optimality conditions of KKT type. Finally we end with some numerical tests to illustrate the behavior of our algorithm. PubDate: 2021-01-18

Abstract: Abstract We introduce and study the notion of the \(\left( \sigma ,y\right) \) -conjugate of a proper \(\sigma \) -convex function. Some relations between the \(\sigma \) -subdifferentials and the Clarke–Rockafellar subdifferential are established. Also, we present some results regarding the \(\sigma \) -monotonicity of the \(\sigma \) -subdifferential of a function and its \(\sigma \) -convexity. Moreover, we obtain some particular relationships between the \(\sigma \) -subdifferential and the \(\left( \sigma ,y\right) \) -conjugate. PubDate: 2021-01-16

Abstract: Abstract Recently, the estimation problem of upper and lower bounds of the solution set of the tensor complementarity problem has been studied when the tensor involved is a strictly semi-positive tensor or one of its subclasses. This paper aims to study such an estimation problem in a larger scope. First, we propose a lower bound formula under the condition that the tensor complementarity problem has a solution. When the problem under consideration falls back to several types of problems that have been studied, the achieved result improves the relevant known results. Second, by means of a newly introduced quantity, we give an upper bound formula of the solution set when the problem has a solution and the tensor involved is an \(R_0\) -tensor. This formula is new even when the concerned problem falls back to several problems that have already been discussed. Several examples are also given to confirm our theoretical findings. PubDate: 2021-01-12

Abstract: Abstract This work proposes a bi-objective mathematical optimization model and a two-stage heuristic for a real-world application of the heterogeneous Dynamic Dial-a-Ride Problem with no rejects, i.e., a patient transportation system. The problem consists of calculating route plans to meet a set of transportation requests by using a given heterogeneous vehicle fleet. These transportation requests can be either static or dynamic, and all of them must be attended to. In the first stage of the proposed heuristic, the problem’s static part is solved by applying a General Variable neighborhood Search based algorithm. In the second stage, the dynamic requests are dealt with by implementing a simple insertion heuristic. We create different instances based on the real data provided by a Brazilian city’s public health care system and test the proposed approach on them. The analysis of the results shows that the higher the level of dynamism, i.e., the number of urgent requests on each instance, the smaller the objective function value will be in the static part. The results also demonstrate that a higher level of dynamism increases the chance of a time window violation happening. Besides, we use the weighted sum method of the two conflicting objectives to analyze the trade-off between them and create an approximation for the Pareto frontier. PubDate: 2021-01-08

Abstract: Abstract Beside of cryptography-the primary traditional methods for ensuring information security and confidentiality, the appearance of the physical layer security approach plays an important role for not only enabling the data transmission confidentially without relying on higher-layer encryption, but also enhancing confidentiality of the secret key distribution in cryptography. Many techniques are employed in physical layers to improve secure transmission including cooperative relaying and beamforming technique. In this paper, we consider the secrecy rate maximization problems using two techniques mentioned above with two different relaying protocols: Amplify-and-Forward and Decode-and-Forward. The optimization problems with the aim of maximizing secrecy rate subject to total and individual relay power constraints are formulated as nonconvex problems, which can be reformulated as DC (difference of two convex functions) programs and thus can be solved by DC Algorithms (DCA). The special structure of feasible set is exploited which results to an efficient DC decomposition in the sense that it leads to convex subproblems that can be explicitly solved. The numerical results show that the proposed DCA schemes are better than the existing methods in terms of both runtime and secrecy rate. PubDate: 2021-01-08

Abstract: Abstract Sentence compression is an important problem in natural language processing with wide applications in text summarization, search engine and human–AI interaction system etc. In this paper, we design a hybrid extractive sentence compression model combining a probability language model and a parse tree language model for compressing sentences by guaranteeing the syntax correctness of the compression results. Our compression model is formulated as an integer linear programming problem, which can be rewritten as a difference-of-convex (DC) programming problem based on the exact penalty technique. We use a well-known efficient DC algorithm—DCA to handle the penalized problem for local optimal solutions. Then a hybrid global optimization algorithm combining DCA with a parallel branch-and-bound framework, namely PDCABB, is used for finding global optimal solutions. Numerical results demonstrate that our sentence compression model can provide excellent compression results evaluated by F-score, and indicate that PDCABB is a promising algorithm for solving our sentence compression model. PubDate: 2021-01-07

Abstract: Abstract In this paper, we study the extended trust-region subproblem in which the trust-region intersects the ball with m linear inequality constraints (m-eTRS). We assume that the linear constraints do not intersect inside the ball. We show that the optimal solution of m-eTRS can be found by solving one TRS, computing the local non-global minimizer of TRS if it exists and solving at most two TRSs with an additional linear equality constraint (1-eqTRS). Both TRS and (1-eqTRS) are polynomially and efficiently solvable, thus the new algorithm significantly improves over the SOCP/SDP relaxation of Burer and Yang [Math Program 149(1-2):253–264, 2015]. on two classes of test problems, the efficiency of the proposed approach is compared with the SOCP/SDP relaxation and branch and bound algorithm of Beck and Pan [J Global Optim 69(2):309–342, 2017]. PubDate: 2021-01-06

Abstract: Abstract In this paper, we examine the properly twice epi-differentiability and compute the second order epi-subderivative of the indicator function to a class of sets including the finite union of parabolically derivable and parabolically regular sets. In this way, we provide no-gap second order optimality conditions for a disjunctive constrained problem. Moreover, we derive applications of our results to some types of disjunctive programs. PubDate: 2021-01-06

Abstract: Abstract The vertex colourability problem is to determine, for a given graph and a given natural k, whether it is possible to split the graph’s vertex set into at most k subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for \(\{claw,butterfly\}\) -free graphs. A claw is the star graph with three leaves, a butterfly is obtained by coinciding a vertex in a triangle with a vertex in another triangle. PubDate: 2021-01-06

Abstract: Abstract We consider the maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance (denoted by (MSPITH)), which has wide applications in transportation network, network war and terrorist network. The problem (MSPITH) aims to maximize the length of the shortest path from the root of a tree to all its leaves by upgrading edge weights such that the upgrade cost under sum-Hamming distance is upper-bounded by a given value. We show that the problem (MSPITH) under weighted sum-Hamming distance is NP-hard. We consider two cases of the problem (MSPITH) under unit sum-Hamming distance based on the number K of critical edges. We propose a greedy algorithm within \(O(n+l\log l)\) time when \(K=1\) and a dynamic programming algorithm within \(O(n(\log n+K^3))\) time when \(K>1\) , where n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we consider a minimum cost shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary search algorithm within \(O(n^4\log n)\) time, where a dynamic programming algorithm is executed in each iteration to solve its corresponding problem (MSPITH). Finally, we design numerical experiments to show the effectiveness of the algorithms. PubDate: 2021-01-06

Abstract: Abstract In this paper, we study the absolute value equation (AVE) \(Ax-b= x \) . One effective approach to handle AVE is by using concave minimization methods. We propose a new method based on concave minimization methods. We establish its finite convergence under mild conditions. We also study some classes of AVEs which are polynomial time solvable. PubDate: 2021-01-05

Abstract: Abstract The paper deals with a Berge equilibrium (Théorie générale des jeux à-personnes, Gauthier Villars, Paris, 1957; Some problems of non-antagonistic differential games, 1985) in the bimatrix game for mixed strategies. Motivated by Nash equilibrium (Ann Math 54(2):286, 1951; Econometrica 21(1):128–140, 1953), we prove an existence of Berge equilibrium in the bimatrix game. Based on Mills theorem (J Soc Ind Appl Math 8(2):397–402, 1960), we reduce the bimatrix game to a nonconvex optimization problem. We illustrate the proposed approach on an example. PubDate: 2021-01-04

Abstract: Abstract During major infectious disease outbreak, such as COVID-19, the goods and parcels supply and distribution for the isolated personnel has become a key issue worthy of attention. In this study, we propose a delivery problem that arises in the last-mile delivery during major infectious disease outbreak. The problem is to construct a Hamiltonian tour over a subset of candidate parking nodes, and each customer is assigned to the nearest parking node on the tour to pick up goods or parcels. The aim is to minimize the total cost, including the routing, allocation, and parking costs. We propose three models to formulate the problem, which are node-based, flow-based and bilevel programing formulations. Moreover, we develop a variable neighborhood search algorithm based on the ideas from the bilevel programing formulations to solve the problem. Finally, the proposed algorithm is tested on a set of randomly generated instances, and the results indicate the effectiveness of the proposed approach. PubDate: 2021-01-04

Abstract: Abstract In the sequel, we outline necessary and sufficient condition to the existence of extremas of a function on a self-similar set, and we describe discrete gradient algorithm to find the extrema. PubDate: 2021-01-04

Abstract: Abstract In this paper, we present the problem in which a municipal company operating in the waste management sector willing to encourage users to use differentiated waste collection facilities, designs a utility user function to attain such a goal. The problem is modeled in terms of bilevel optimization where the leader is the municipal firm which aims at maximizing the concurrent fraction of user waste demand thrown in recycling facilities, and the follower are users aiming at maximizing the utility function proposed by the leader. The resulting bilevel model is analysed in terms of stability showing that its optimistic solution value equals the pessimistic solution value. A solution approach is presented. Finally, a computational study shows the effectiveness of our proposal. PubDate: 2021-01-02

Abstract: Abstract Researchers and practitioners have addressed many variants of facility locations problems. Each location problem can be substantially different from each other depending on the objectives and/or constraints considered. In this paper, the bi-objective obnoxious p-median problem (Bi-OpM) is addressed given the huge interest to locate facilities such as waste or hazardous disposal facilities, nuclear power or chemical plants and noisy or polluting services, among others. The Bi-OpM aims to locate p facilities maximizing two different objectives: the distance between each customer and their nearest facility center and the dispersion among facilities. To address the Bi-OpM problem a Multi-objective Parallel Variable Neighborhood Search approach (Mo-PVNS) is implemented. Computational results indicate the superiority of the Mo-PVNS compared to the state-of-art algorithms. PubDate: 2021-01-02