-
作者：Çezik, MT; Iyengar, G
作者单位：Universite de Montreal; Universite de Montreal; Columbia University
摘要：In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomor...
-
作者：Danna, E; Rothberg, E; Le Pape, C
作者单位：Centre National de la Recherche Scientifique (CNRS); Avignon Universite
摘要：Given a feasible solution to a Mixed Integer Programming (MIP) model, a natural question is whether that solution can be improved using local search techniques. Local search has been applied very successfully in a variety of other combinatorial optimization domains. Unfortunately, local search relies extensively on the notion of a solution neighborhood, and this neighborhood is almost always tailored to the structure of the particular problem being solved. A MIP model typically conveys little ...
-
作者：Berkelaar, A; Gromicho, JAS; Kouwenberg, R; Zhang, SZ
作者单位：Vrije Universiteit Amsterdam; Chinese University of Hong Kong
摘要：This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their o...
-
作者：Cánovas, MJ; López, MA; Parra, J; Toledo, FJ
作者单位：Universidad Miguel Hernandez de Elche; Universitat d'Alacant
摘要：In this paper we consider the parameter space of all the linear inequality systems, in the n-dimensional Euclidean space, with a fixed and arbitrary (possibly infinite) index set. This parameter space is endowed with the topology of the uniform convergence of the coefficient vectors by means of an extended distance. Some authors, in a different context in which the index set is finite and, accordingly, the coefficients are bounded, consider the boundary of the set of consistent systems as the ...
-
作者：Filippi, C; Agnetis, A
作者单位：University of Padua; University of Siena
摘要：The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C-2 bins more than the optimal solution, i.e., an algorithm that is asymptoti...
-
作者：Fischetti, M; Glover, F; Lodi, A
作者单位：University of Padua; University of Colorado System; University of Colorado Boulder; University of Bologna
摘要：In this paper we consider the NP-hard problem of finding a feasible solution ( if any exists) for a generic MIP problem of the form min{c(T) x : Ax >= b, x(j) integer for all j is an element of I}. Trivially, a feasible solution can be defined as a point x*is an element of P := {x : Ax >= b} that is equal to its rounding (x) over tilde, where the rounded point (x) over tilde x is defined by (x) over tilde (j) := [ x*(j)] if j is an element of I and (x) over tilde (j)* := x(j)* otherwise, and [...
-
作者：Auslender, A; Teboulle, M
作者单位：Universite Claude Bernard Lyon 1; Tel Aviv University
摘要：We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior ...
-
作者：Iwata, S; Moriguchi, S; Murota, K
作者单位：University of Tokyo
摘要：This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum s...
