-
作者：Wolsey, LA
作者单位：Universite Catholique Louvain
摘要：We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also sh...
-
作者：Markót, MC; Fernández, J; Casado, LG; Csendes, T
作者单位：Szeged University; Hungarian Academy of Sciences; European Space Agency; European Space Research & Technology Centre; University of Murcia; Universidad de Almeria; Szeged University
摘要：Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for ...
-
作者：Ye, YY
作者单位：Stanford University
摘要：We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vect...
-
作者：Cornuéjols, G; Lemaréchal, C
作者单位：Carnegie Mellon University; Aix-Marseille Universite; Inria
摘要：We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cut...
-
作者：Yin, HX; Ling, C; Qi, LQ
作者单位：Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Zhejiang University of Finance & Economics; Hong Kong Polytechnic University
摘要：In the paper, we prove the Holder continuous property of the Jacobian of the function generated from the dual of the power spectrum estimation problem. It follows that the convergence of the Newton method for the problem is at least of order 1 + 2/2m, where m is the order of the trigonometric bases. This result theoretically confirms the numerical observation by Potter (1990) and Cole and Goodrich (1993).
-
作者：Chou, MC; Queyranne, M; Simchi-Levi, D
作者单位：National University of Singapore; University of British Columbia; Massachusetts Institute of Technology (MIT)
摘要：Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to...
-
作者：Barahona, F
作者单位：International Business Machines (IBM); IBM USA
摘要：We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invu...
-
作者：Philpott, Andy; Schultz, Ruediger
作者单位：University of Auckland; University of Duisburg Essen
摘要：We consider an electricity generator making offers of energy into an electricity pool market over a horizon of several trading periods (typically a single trading day). The generator runs a set of generating units with given start-up costs, shut-down costs and operating ranges. At the start of each trading period the generator must submit to the pool system operator a new supply curve defining quantities of offered energy and the prices at which it wants these dispatched. The amount of dispatc...
-
作者：Guérin, J; Marcotte, P; Savard, G
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case.
-
作者：Lasserre, JB
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Omega can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max (z is an element of Omega) p(z), whereas the second problem is a robust analogue of the generic problem ...
