-
作者：Rubinov, A. M.; Wu, Z. Y.
作者单位：Federation University Australia
摘要：In this paper we derive necessary and sufficient conditions for some problems of global minimization. Our approach is based on methods of abstract convexity: we use a representation of an upper semicontinuous function as the lower envelope of a family of convex functions. We discuss applications of conditions obtained to the examination of some tractable sufficient conditions for the global minimum and to the theory of inequalities.
-
作者：Sager, Sebastian; Bock, Hans Georg; Reinelt, Gerhard
作者单位：Ruprecht Karls University Heidelberg
摘要：Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We cons...
-
作者：Ioslovich, Ilya; Borshchevsky, Michael; Gutman, Per-Olof
作者单位：Technion Israel Institute of Technology
摘要：The problem of fuel-optimal attitude maneuvering of a space vehicle (SV) with non-fixed time is considered. The state constraint related to the maintenance of artificial gravitation is imposed. This problem is especially important for long-time space missions. The attitude of the space vehicle is controlled by means of a pair of reactive engines which produce a single control torque with fixed direction in the body-fixed frame. An optimal solution is obtained in the class of trajectories belon...
-
作者：Louveaux, Francois; Salazar-Gonzalez, Juan-Jose
作者单位：Universidad de la Laguna; University of Namur; Universite Catholique Louvain
摘要：This paper studies how to set the vehicle capacity for traveling Salesman Problems where some of the customer demands are stochastic. The analyses are done for the one-commodity pickup-and-delivery TSP, as this problem also includes the setting of the initial load. The paper first considers feasibility issues. This includes finding the smallest vehicle capacity and some initial load such that a given tour is feasible for all scenarios. Different variants are considered as a function of the tim...
-
作者：Antipin, Anatoly
作者单位：Russian Academy of Sciences
摘要：We consider two-person nonzero-sum game, both in the classical form and in the form of a game with coupled variables. An extra-proximal approach for finding the game's solutions is suggested and justified. We provide our algorithm with an analysis of its convergence.
-
作者：Caprara, Alberto; Monaci, Michele
作者单位：University of Bologna; University of Padua
摘要：We consider geometric problems in which rectangles have to be packed into (identical) squares. These problems turn out to be very hard in practice, and ILP formulations in which variables specify the coordinates in the packing perform very poorly. While most methods developed so far are based on simple geometric considerations, a recent landmark result of Fekete and Schepers suggests to put these geometric aspects aside and use the most advanced tools for the one-dimensional case. In this pape...
-
作者：Iusem, Alfredo; Seeger, Alberto
作者单位：Avignon Universite
摘要：The concept of antipodality relative to a closed convex cone K subset of R-d has been explored in detail in a recent work of ours. The antipodality problem consists of finding a pair of unit vectors in K achieving the maximal angle of the cone. Our attention now is focused not just in the maximal angle, but in the angular spectrum of the cone. By definition, the angular spectrum of a cone is the set of angles satisfying the stationarity (or criticality) condition associated to the maximization...
-
作者：Correa, Jose R.; Wagner, Michael R.
作者单位：California State University System; California State University East Bay; Universidad Adolfo Ibanez
摘要：We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-pree...
-
作者：Nesterov, Yurii
作者单位：Universite Catholique Louvain
摘要：In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent m...
-
作者：Epstein, Leah; Levin, Asaf
作者单位：Hebrew University of Jerusalem; University of Haifa
摘要：Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property canno...
