-
作者：Tawarmalani, M; Sahinidis, NV
作者单位：Purdue University System; Purdue University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：This work addresses the development of an efficient solution strategy for obtaining global optima of continuous. integer. and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper. we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs an...
-
作者：Kolliopoulos, SG; Stein, C
作者单位：McMaster University; Columbia University; Dartmouth College
摘要：In a packing integer program, we are given a matrix A and column vectors b,c with nonnegative entries. We seek a vector x of nonnegative integers, which maximizes c(T)x, subject to Axless than or equal tob. The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connect...
-
作者：Magnanti, TL; Perakis, G
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We introduce a general adaptive line search framework for solving fixed point and variational inequality problems. Our goals are to develop iterative schemes that (i) compute solutions when the underlying map satisfies properties weaker than contractiveness, for example, weaker forms of nonexpansiveness, (ii) are more efficient than the classical methods even when the underlying map is contractive, and (iii) unify and extend several convergence results from the fixed point and variational ineq...
-
作者：Lawphongpanich, S; Hearn, DW
作者单位：State University System of Florida; University of Florida
摘要：This paper addresses two second-best toll pricing problems, one with fixed and the other with elastic travel demands, as mathematical programs with equilibrium constraints. Several equivalent nonlinear programming formulations for the two problems are discussed. One formulation leads to properties that are of interest to transportation economists. Another produces an algorithm that is capable of solving large problems and easy to implement with existing software for linear and nonlinear progra...
-
作者：Hamdouch, Y; Marcotte, P; Nguyen, S
作者单位：Universite de Montreal; Universite de Montreal
摘要：In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a user's position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution. users are assigned to strategies that minim...
-
作者：Hobbs, BF; Pang, JS
作者单位：Johns Hopkins University; Rensselaer Polytechnic Institute
摘要：This paper considers equilibria among multiple firms that are competing non-cooperatively against each other to sell electric power and buy resources needed to produce that power. Examples of such resources include fuels, power plant sites, and emissions allowances. The electric power market is a spatial market on a network in which flows are constrained by Kirchhoff's current and voltage laws. Arbitragers in the power market erase spatial price differences that are non-cost based. Power produ...
-
作者：Conde, E
作者单位：University of Sevilla
摘要：We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n-p}n) time. This improves the previously known complexity O(min{p,n-p}(2)n).
-
作者：Yamashita, N; Dan, H; Fukushima, M
作者单位：Kyoto University
摘要：In this paper we focus on the problem of identifying the index sets P(x) := {i \ x(i)>0}, N(x) := {i \ F-i(x)>0} and C(x) := {i \ x(i) = F-i(x)=0} for a solution x of the monotone nonlinear complementarity problem NCP(F). The correct identification of these sets is important from both theoretical and practical points of view. Such an identification enables us to remove complementarity conditions from the NCP and locally reduce the NCP to a system which can be dealt with more easily. We present...
-
作者：Cheung, D; Cucker, F
作者单位：City University of Hong Kong
摘要：We define a condition number K(A,b,c) for a linear program min c(T)x s.t. Ax=b,xgreater than or equal to0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log K(A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution.
-
作者：Ferris, MC; Voelker, MM
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：Radiotherapy treatment is often delivered in a fractionated manner over a period of time. Emerging delivery devices are able to determine the actual dose that has been delivered at each stage facilitating the use of adaptive treatment plans that compensate for errors in delivery. We formulate a model of the day-to-day planning problem as a stochastic program and exhibit the gains that can be achieved by incorporating uncertainty about errors during treatment into the planning process. Due to s...
