-
作者：Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamas
作者单位：McMaster University
摘要：By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2(n) n(5/2)), we prove that solving this n-dimensional linear optimization problem requires at least 2(n)-1 iterations.
-
作者：Glover, Fred; Sherali, Hanif D.
作者单位：University of Colorado System; University of Colorado Boulder; Virginia Polytechnic Institute & State University
摘要：We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0-1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and -1. We pr...
-
作者：Anstreicher, Kurt M.; Iusem, Alfredo
作者单位：University of Iowa
-
作者：Yamashita, Nobuo
作者单位：Kyoto University
摘要：Quasi-Newton methods are powerful techniques for solving unconstrained minimization problems. Variable metric methods, which include the BFGS and DFP methods, generate dense positive definite approximations and, therefore, are not applicable to large-scale problems. To overcome this difficulty, a sparse quasi-Newton update with positive definite matrix completion that exploits the sparsity pattern E := {( i, j) vertical bar (del(2) f (x))(i j) not equal 0 for some x is an element of R-n} of th...
-
作者：Bonami, Pierre; Cornuejols, Gerard; Dash, Sanjeeb; Fischetti, Matteo; Lodi, Andrea
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA; Aix-Marseille Universite; University of Padua; University of Bologna
摘要：Recent experiments by Fischetti and Lodi show that the first Chvatal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvatal closure by modeling the Chvatal-Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since ...
-
作者：Baillon, J. -B.; Cominetti, R.
作者单位：Universidad de Chile; heSam Universite; Universite Pantheon-Sorbonne
摘要：We analyze an equilibrium model for traffic networks based on stochastic dynamic programming. In this model passengers move towards their destinations by a sequential process of arc selection based on a discrete choice model at every intermediate node in their trip. Route selection is the outcome of this sequential process while network flows correspond to the invariant measures of the underlying Markov chains. The approach may handle different discrete choice models at every node, including t...
-
作者：Ye, Yinyu
作者单位：Stanford University
摘要：We present polynomial-time interior-point algorithms for solving the Fisher and Arrow - Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic operation complexity bound of O(n(4) log(1/epsilon)) for computing an epsilon-equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O(n(4)L) which is in line with the best complexity bound for linear programmi...
-
作者：Briant, O.; Lemarechal, C.; Meurdesoif, Ph.; Michel, S.; Perrot, N.; Vanderbeck, F.
作者单位：Inria; Universite de Bordeaux
摘要：When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle m...
-
作者：Kiwiel, Krzysztof C.
作者单位：Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences
摘要：We give several linear time algorithms for the continuous quadratic knapsack problem. In addition, we report cycling and wrong-convergence examples in a number of existing algorithms, and give encouraging computational results for large-scale problems.
-
作者：Iwata, Satoru
作者单位：Kyoto University
摘要：Submodular functions often arise in various fields of operations research including discrete optimization, game theory, queueing theory and information theory. In this survey paper, we give overview on the fundamental properties of submodular functions and recent algorithmic devolopments of their minimization.
