Authors:M. A. Goberna; M. A. López Pages: 221 - 264 Abstract: Abstract This paper reviews the state-of-the-art in the theory of deterministic and uncertain linear semi-infinite optimization, presents some numerical approaches to this type of problems, and describes a selection of recent applications in a variety of fields. Extensions to related optimization areas, as convex semi-infinite optimization, linear infinite optimization, and multi-objective linear semi-infinite optimization, are also commented. PubDate: 2017-09-01 DOI: 10.1007/s10288-017-0350-6 Issue No:Vol. 15, No. 3 (2017)
Authors:Xianglai Qi; Jinjiang Yuan Pages: 265 - 276 Abstract: Abstract In this paper, we consider the semi-online hierarchical scheduling for load balancing on two identical machines. In the problem, the jobs are available online over list and the objective is to minimize the \(l_p\) -norm of the two machines’ loads. Two semi-online versions are investigated: the buffer version and the rearrangement version. We design a unified optimal semi-online algorithm for both models. PubDate: 2017-09-01 DOI: 10.1007/s10288-016-0334-y Issue No:Vol. 15, No. 3 (2017)
Authors:Benoîte de Saporta; François Dufour; Christophe Nivot Pages: 277 - 302 Abstract: Abstract This paper is dedicated to the investigation of a new numerical method to approximate the optimal stopping problem for a discrete-time continuous state space Markov chain under partial observations. It is based on a two-step discretization procedure based on optimal quantization. First, we discretize the state space of the unobserved variable by quantizing an underlying reference measure. Then we jointly discretize the resulting approximate filter and the observation process. We obtain a fully computable approximation of the value function with explicit error bounds for its convergence towards the true value function. PubDate: 2017-09-01 DOI: 10.1007/s10288-016-0337-8 Issue No:Vol. 15, No. 3 (2017)
Authors:N. Mahdavi-Amiri; F. Salehi Sadaghiani Pages: 303 - 326 Abstract: Abstract Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification. PubDate: 2017-09-01 DOI: 10.1007/s10288-016-0338-7 Issue No:Vol. 15, No. 3 (2017)
Authors:Xavier Fernandes; Joana Rebelo; João Gouveia; Rodrigo Maia; Nuno Bustorff Silva Pages: 163 - 181 Abstract: Abstract In this paper, we study the problem of establishing a dynamic charging schedule of electric vehicles (EVs) at a charging station, assuming that limited power implies that only a limited number of EVs can charge simultaneously. The only control we assume to be available to the charging station is the ability to (at any given time) turn on or off the power supply to any EV, with this tool we want to develop a charging schedule that will satisfy the energy demands of the EVs in their intended deadlines. We propose two distinct approaches to this problem: a discretized time version, based on a greedy-like algorithm, and a continuous time version, based on linear programming. We compare these two approaches and numerically study the improvement they yield in the efficiency of the charging procedure, when applied to simulated data based on real parking data. Finally, we illustrate the flexibility of the models by sketching several possible extensions. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0328-9 Issue No:Vol. 15, No. 2 (2017)
Authors:Michaël Gabay; Nadia Brauner; Vladimir Kotov Pages: 183 - 199 Abstract: Abstract We use game theory techniques to automatically compute improved lower bounds on the competitive ratio for the bin stretching problem. Using these techniques, we improve the best lower bound for this problem to 19/14. We explain the technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0330-2 Issue No:Vol. 15, No. 2 (2017)
Authors:Ching-Hui Tang Abstract: Abstract In this study, we deal with the problem of short-term transportation outsourcing for transshipment centers. The carrier needs to determine the numbers of outsourced and self-run trips for the different types of transportation tasks. Stochastic demands which are likely to occur in actual operation are considered. Different trip numbers need to be determined in sequence, so a two-stage stochastic programming technique is applied to formulate the problem. Two models are developed based upon practical considerations to help determine the optimal transportation outsourcing plan. A case study regarding the operations of a logistics carrier in Taiwan is performed. Several tests are also performed considering the number of demand scenarios, optimality gaps, variations in demands, outsourcing cost variations, and problem dimensions in order to better understand the performance of the two models. PubDate: 2017-10-17 DOI: 10.1007/s10288-017-0355-1
Authors:Weidong Li; Qianna Cui Abstract: Abstract In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme. PubDate: 2017-10-16 DOI: 10.1007/s10288-017-0356-0
Authors:Hadi Charkhgard; Martin Savelsbergh; Masoud Talebian Abstract: Abstract We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem. PubDate: 2017-09-18 DOI: 10.1007/s10288-017-0354-2
Authors:Anton Bondarev; Alfred Greiner Abstract: Abstract In this paper we analyze an inter-temporal optimization problem of a representative firm that invests in horizontal and vertical innovations and that faces a constraint with respect to total R&D spending. We find that there can exist two different steady-states of the economy when the amount of research spending falls short of an endogenously determined threshold: one with higher productivities and less new technologies being developed, and the other with more technologies being created and lower productivities. But, for a higher amount of R&D spending the steady-state becomes unique and the firm produces the whole spectrum of available technologies. Thus, a lock-in effect may arise that, however, can be overcome by raising R&D spending sufficiently. PubDate: 2017-07-29 DOI: 10.1007/s10288-017-0348-0
Hybrid journal (It can contain Open Access articles)
[2352 journals]
