Abstract: We apply the t-linearization technique to the maximum diversity problem (MDP) and compare its performance with other well-known linearizations. We lift the t-constraints based on the cardinality restriction, derive valid inequalities for MDP, and show their usefulness to solve the problem within the t-linearization framework. We propose and computationally evaluate a branch-and-bound algorithm on benchmark instances. The algorithm is compared with other exact approaches from the literature. PubDate: 2021-03-09
Abstract: In a recent paper, Jiang et al. (Eng Optim 52(1):37–52, 2020) considered proportionate flowshop scheduling with position-dependent weights. For common and slack due-date assignment problems, they proved that both of these two problems can be solved in \(O(n^{2} \log n)\) time, where \(n\) is the number of jobs. The contribution of this paper is that we show that these two problems can be optimally solved by a lower-order algorithm, i.e., in \(O(n\log n)\) time. PubDate: 2021-03-08
Abstract: While measuring forecasting accuracy has been intensively studied by researchers, the consideration of sets of non-dominated solutions has not yet been explored in the literature. Even when considering measures that are in harmony, small changes in model parameters can result in a trained system capable of forecasting different time series characteristics. In this regard, this study shows how a set of non-dominated forecasting models can assist decision makers to pick the most suitable model for operations on dynamic environments. In particular, the system presents an interesting trade-off provided with assistance of a new strategic measure, which forces the forecasting model to learn the highest values of the time series. An automatic self-adaptive forecasting framework, calibrated with Multi-Objective VND inspired techniques, and able to perform k-steps-ahead forecasting, is considered. There is a growing demand for learning big-data time series, such as those derived from sensors in energy mini/microgrid systems, in which real-time decisions should be made quickly and can vary according to the available energy resources. Thus, a case of study is considered using data from disaggregated power readings of a typical microgrid due to the fact that load demand forecasting, with different components of a house, is of crucial importance for management and operation of new emerging decentralized systems. PubDate: 2021-03-08
Abstract: This paper conducts a comparative study of proximal gradient methods (PGMs) and proximal DC algorithms (PDCAs) for sparse regression problems which can be cast as Difference-of-two-Convex-functions (DC) optimization problems. It has been shown that for DC optimization problems, both General Iterative Shrinkage and Thresholding algorithm (GIST), a modified version of PGM, and PDCA converge to critical points. Recently some enhanced versions of PDCAs are shown to converge to d-stationary points, which are stronger necessary condition for local optimality than critical points. In this paper we claim that without any modification, PGMs converge to a d-stationary point not only to DC problems but also to more general nonsmooth nonconvex problems under some technical assumptions. While the convergence to d-stationary points is known for the case where the step size is small enough, the finding of this paper is valid also for extended versions such as GIST and its alternating optimization version, which is to be developed in this paper. Numerical results show that among several algorithms in the two categories, modified versions of PGM perform best among those not only in solution quality but also in computation time. PubDate: 2021-03-03
Abstract: The Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations assumes that, at each station, the number of vehicles simultaneously refueling cannot exceed the number of available pumps. The state-of-the-art solution method, based on the generation of all feasible non-dominated paths, performs well only with up to 2 pumps. In fact, it needs cloning the paths between every pair of pumps. To overcome this issue, in this paper, we propose new path-based MILP models without cloning paths, for both the scenario with private stations (i.e., owned by the fleet manager) and that with public stations. Then, a more efficient cutting plane approach is designed for addressing both the scenarios. Numerical results, obtained considering a set of benchmark instances ad hoc generated for this work, show both the efficiency and the effectiveness of this new cutting plane approach proposed. Finally, a sensitivity analysis, carried out by varying the number of customers to be served and their distribution, shows very good performances of the proposed approach. PubDate: 2021-03-01
Abstract: We present a short-step interior-point algorithm (IPA) for sufficient linear complementarity problems (LCPs) based on a new search direction. An algebraic equivalent transformation (AET) is used on the centrality equation of the central path system and Newton’s method is applied on this modified system. This technique was offered by Zsolt Darvay for linear optimization in 2002. Darvay first used the square root function as AET and in 2012 Darvay et al. applied this technique with an other transformation formed by the difference of the identity map and the square root function. We apply the AET technique with the new function to transform the central path equation of the sufficient LCPs. This technique leads to new search directions for the problem. We introduce an IPA with full Newton steps and prove that the iteration bound of the algorithm coincides with the best known one for sufficient LCPs. We present some numerical results to illustrate performance of the proposed IPA on two significantly different sets of test problems and compare it, with related, quite similar variants of IPAs. PubDate: 2021-03-01
Abstract: We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items’ combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop exact solution algorithms for the robust problem, based on cut generation and mixed-integer programming, and present the results of computational experiments. PubDate: 2021-03-01
Abstract: We consider the learning effects in the coordination of production and outbound distribution for manufacturers. The objective is to minimize service span, which lasts from the beginning of production to the completion of delivery of products. In production, a batch-processing facility is used to process jobs which have different sizes. Batch-position-based learning effects are considered since workers become skillful gradually after processing batches one by one. In distribution, a vehicle with a fixed capacity is used to deliver products the customer and the transportation time from the manufacturer to the customer is a constant. We show the coordinated scheduling problem is NP-hard in the strong sense. We propose properties of optimal solutions and we provide an approximation algorithm for the problem. The absolute performance guarantee of the algorithm is 1.667 and the asymptotic performance guarantee is 1.223. Then we consider the problem where there are infinite vehicles and the performance guarantees are respectively 1.5 and 1.223. Finally we analyze the performance of the algorithm by the change of the problem scale, the learning index and operational factors. We propose managerial suggestions for decision makers of manufacturers according to our results. PubDate: 2021-03-01
Abstract: Remanufacturing has been widely recognized in practice. However, the low acceptance of remanufactured products deeply hinders the performance of remanufacturing. Recently, trade-in programs are growing in popularity for selling remanufactured products to promote consumptions. In this paper, under the constraint of consumer participation, we investigate the conditions under which a trade-in program for remanufactured products should be adopted and how to optimize the pricing and production decisions. Cannibalization between new and remanufactured products has been analyzed for both primary and replacement markets. PubDate: 2021-03-01
Abstract: We study a variant of the competitive facility location problem, in which a company is to locate new facilities in a market where competitor’s facilities already exist. We consider the scenario where only a limited number of possible attractiveness levels is available, and the company has to select exactly one level for each open facility. The goal is to decide the facilities’ locations and attractiveness levels that maximize the profit. We apply the gravity-based rule to model the behavior of the customers and formulate a multi-ratio linear fractional 0–1 program. Our main contributions are the exact solution approaches for the problem. These approaches allow for easy implementations without the need for designing complicated algorithms and are “friendly” to the users without a solid mathematical background. We conduct computational experiments on the randomly generated datasets to assess their computational performance. The results suggest that the mixed-integer quadratic conic approach outperforms the others in terms of computational time. Besides that, it is also the most straightforward one that only requires the users to be familiar with the general form of a conic quadratic inequality. Therefore, we recommend it as the primary choice for such a problem. PubDate: 2021-03-01
Abstract: In this work, we give a tight estimate of the rate of convergence for the Halpern-iteration for approximating a fixed point of a nonexpansive mapping in a Hilbert space. Specifically, using semidefinite programming and duality we prove that the norm of the residuals is upper bounded by the distance of the initial iterate to the closest fixed point divided by the number of iterations plus one. PubDate: 2021-03-01
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-03-01
Abstract: Transportation auctions are increasingly made online and the bidding time intervals are becoming much shorter. From the carriers’ perspective, bid determination problems need to be solved more quickly due to the increasing number of auctions in the online transportation marketplace for their survivability. In this research, we study the bid price determination problem of truckload (TL) carriers participating in multiple independent first-price sealed-bid single-request TL transportation auctions simultaneously. The carriers must win the right combination of auctions to ensure profitability. The high level of competition, the uncertainty of the outcomes of the auctions, and the independence of the auctions from each other constitute the main challenge in this setting. In order to solve this problem, we develop an efficient heuristic which identifies the auctions to participate and determines the carriers’ bids in the selected auctions. We demonstrate the efficiency and the effectiveness of our proposed heuristic by simulating a competitive auction-based transportation procurement marketplace under various parameter settings. The simulations show that our proposed heuristic performs close to an existing approach found in the literature with much less computational effort. PubDate: 2021-03-01
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-03-01
Abstract: Production and inventory planning have become crucial and challenging in nowadays competitive industrial and commercial sectors, especially when multiple plants or warehouses are involved. In this context, this paper addresses the complexity of uncapacitated multi-plant lot-sizing problems. We consider a multi-item uncapacitated multi-plant lot-sizing problem with fixed transfer costs and show that two of its very restricted special cases are already NP-hard. Namely, we show that the single-item uncapacitated multi-plant lot-sizing problem with a single period and the multi-item uncapacitated two-plant lot-sizing problem with fixed transfer costs are NP-hard. Furthermore, as a direct implication of the proven results, we also show that a two-echelon multi-item lot-sizing with joint setup costs on transportation is NP-hard. PubDate: 2021-03-01
Abstract: In this paper, we present necessary/sufficient conditions for the convex polynomial programming (CPP) problems. Some new stability results for parametric CPP problems are characterized under a regular condition. We give a positive answer for the open question in Kim et al. (Optim Lett 6:363–373, 2012) for the solution existence of convex quadratic programming problems. PubDate: 2021-03-01
Abstract: In this paper, we address the problem of minimum number of Steiner points of constrained 1-line-fixed Steiner tree (abbreviated to the MNSP-C1LF-ST problem), which is defined as follows. Given n terminals located at the same side of a fixed line l in the Euclidean plane \({\mathbb {R}}^2\) and a constant L, we are asked to find a Steiner tree T to interconnect these n terminals in \({\mathbb {R}}^2\) such that the Steiner points of the tree T, which has at least one Steiner point, are all located on the fixed line l and that the weight \(w(T)=\sum _{e\in T}w(e) \le L\) , the objective is to minimize the number s(T) of Steiner points of the tree T, where the weight \(w(e)=0\) if the two endpoints of that edge \(e\in T\) are located on the line l and otherwise the weight w(e) is the Euclidean distance between the two endpoints of that edge \(e\in T\) . In addition, when L is the minimum weight of all possible constrained 1-line-fixed Steiner trees as mentioned above, we refer to this version as the problem of minimum number of Steiner points of constrained 1-line-fixed minimum Steiner tree (abbreviated to the MNSP-C1LF-MST problem). We obtain two main results. (1) Using strategies of finding a minimum spanning tree with a degree constraint, we can design a 3-approximation algorithm in time \(O(n^2\log n)\) to solve the MNSP-C1LF-ST problem. (2) Combining Delaunay triangulation properties and strategies of finding a minimum spanning tree with a degree constraint, we can provide a simple exact algorithm in time \(O(n\log n \log \beta (n))\) to solve the MNSP-C1LF-MST problem, where \(\beta (n)=\min \{i~ ~\log ^{(i)} n \le 4-6/n\}\) . PubDate: 2021-03-01
Abstract: In many practical control systems or management systems, the manager of systems may allow that the statistic probability of system error or parameter deviation occurs within a certain range. The problem of decision optimization under probabilistic constraint is thus an issue needs to be addressed urgently. In this paper, we consider to develop an event-based approach which can solve the probabilistic constrained decision problems in discrete events dynamic systems. The framework of the event-based optimization is first introduced, and then with the methodology of the performance sensitivity analysis, we present an online event-based policy iteration algorithm based on the derived performance gradient formula. We apply the event-based idea and propose the concept of “risk state”, “risk event” and “risk index” which can be used to better describe the nature of the probabilistic constrained problem. Furthermore, by taking the Lagrangian approach, the constrained decision problem can be solved with two steps. Finally, numerical experiments are designed to verify the efficiency of the proposed method. PubDate: 2021-03-01
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-03-01
Abstract: In this paper, we study optimal control problems containing ordinary control systems, linear with respect to a control variable, described by fractional Dirichlet and Dirichlet–Neumann Laplace operators and a nonlinear integral performance index. The main result is a theorem on the existence of optimal solutions for such problems. In our approach we use a characterization of a weak lower semicontinuity of integral functionals. PubDate: 2021-03-01
Hybrid journal (It can contain Open Access articles)
