共查询到20条相似文献,搜索用时 0 毫秒
1.
Herbert E. Scarf 《Mathematical Programming》1997,79(1-3):355-368
In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrixA. If the matrix satisfies some mild conditions, and isgeneric, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular
row ofA as the objective function, and using the remaining rows to impose constraints on the integer variables. 相似文献
2.
Robert Weismantel 《Mathematical Methods of Operations Research》1998,47(1):1-37
This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG). 相似文献
3.
Wiesława T. Obuchowska 《Journal of Global Optimization》2010,46(3):423-433
In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are
defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal
cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class
of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem
of cardinality not greater than 2
n
, this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate
that if the considered convex integer problem is bounded below, then there exists a subset of at most 2
n
−1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem,
equals to the minimum of the objective function over the entire system of constraints. 相似文献
4.
One of the most frequently occurring integer programming structures is the one which has special ordered sets of variables included in multiple choice constraints. For problems with this structure a set of ideal columns are defined from the linear programming relaxation of the integer program and a reduced integer program is formed by keeping only those columns within a specified distance from the ideal column. Conditions are established which guarantee when the optimal solution to the reduced problem is als optimal for the original problem. When these conditions are not satisfied, bounds on the optimal solution value are provided. Ideal columns are also used to establish weights for the special ordered set variables. This procedure has been implemented through a control program written by the authors for MPSX/370-MIP/370. Computational results are given. 相似文献
5.
6.
Sebastián Ceria Cécile Cordier Hugues Marchand Laurence A. Wolsey 《Mathematical Programming》1998,81(2):201-214
We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain. 相似文献
7.
8.
The set of all group relaxations of an integer program contains certain special members called Gomory relaxations. A family
of integer programs with a fixed coefficient matrix and cost vector but varying right hand sides is a Gomory family if every
program in the family can be solved by one of its Gomory relaxations. In this paper, we characterize Gomory families. Every
TDI system gives a Gomory family, and we construct Gomory families from matrices whose columns form a Hilbert basis for the
cone they generate. The existence of Gomory families is related to the Hilbert covering problems that arose from the conjectures
of Seb?. Connections to commutative algebra are outlined at the end.
Received: May 17, 2001 / Accepted: February 7, 2002
Published online: April 24, 2003
RID="⋆"
ID="⋆" Research partially supported by NSF grant DMS-0100141. 相似文献
9.
Jean B. Lasserre 《Discrete Optimization》2004,1(2):167-187
We consider the integer program P→max c′x|Ax=y;xNn . Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables λRm have discrete analogues zCm, related in a simple manner. Moreover, both optimal values of P and the LP obey the same formula, using z for P and |z| for the LP. One retrieves (and refines) the so-called group-relaxations of Gomory which, in this dual approach, arise naturally from a detailed analysis of a generalized residue formula of Brion and Vergne. Finally, we also provide an explicit formulation of a dual problem P*, the analogue of the dual LP in linear programming. 相似文献
10.
Robert F. Bailey José Cáceres Delia Garijo Antonio González Alberto Márquez Karen Meagher María Luz Puertas 《European Journal of Combinatorics》2013
A set of vertices S in a graph G is a resolving set for G if, for any two vertices u,v, there exists x∈S such that the distances d(u,x)≠d(v,x). In this paper, we consider the Johnson graphs J(n,k) and Kneser graphs K(n,k), and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids. 相似文献
11.
We give a method for strengthening cutting planes for pure and mixed integer programs. The method improves the coefficients of the integer-constrained variables, while leaving unchanged those of the continuous variables. We first state the general principle on which the method is based; then apply it to the class of cuts that can be obtained from disjunctive constraints. Finally, we give simple procedures for calculating the improved coefficients of cats in this class, and illustrate them on a numerical example. 相似文献
12.
David E. Bell 《Mathematical Programming》1979,17(1):176-183
Gomory's group relaxation for integer programs has been refined by column generation methods and dual ascent algorithms to identify a set of candidate solutions which are feasible in the relaxation but not necessarily so in the original integer program. Attempts at avoiding branch and bound procedures at this point have focussed on providing extra group constraints which eliminate all or most of the candidate solutions so that further ascent can take place. It will be shown that a single constraint usually of order 2 or 3, can eliminate all of the candidate solutions. 相似文献
13.
Binary clutter inequalities for integer programs 总被引:1,自引:0,他引:1
Adam N. Letchford 《Mathematical Programming》2003,98(1-3):201-221
We introduce a new class of valid inequalities for general integer linear programs, called binary clutter (BC) inequalities. They include the -cuts of Caprara and Fischetti as a special case and have some interesting connections to binary matroids, binary clutters and Gomory corner polyhedra.
We show that the separation problem for BC-cuts is strongly -hard in general, but polynomially solvable in certain special cases. As a by-product we also obtain new conditions under which -cuts can be separated in polynomial time.
These ideas are then illustrated using the Traveling Salesman Problem (TSP) as an example. This leads to an interesting link between the TSP and two apparently unrelated problems, the T-join and max-cut problems.Mathematics Subject Classification: 90C10 相似文献
14.
There exist general purpose algorithms to solve the integer linear programming problem but none of them are polynomial. Polynomially bounded rounding algorithms have been studied, but most of them are problem specific. In this paper we study a generalized rounding algorithm that is polynomial, characterize matrices that may be used in this scheme and identify a class of integer programs that it solves. 相似文献
15.
Bodur Merve Del Pia Alberto Dey Santanu S. Molinaro Marco Pokutta Sebastian 《Mathematical Programming》2018,171(1-2):331-359
Mathematical Programming - In this paper, we study the strength of Chvátal–Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs).... 相似文献
16.
This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension. 相似文献
17.
A finite test set for an integer optimization problem enables us to verify whether a feasible point attains the global optimum. In this paper, we establish several general results that apply to integer optimization problems with nonlinear objective functions. 相似文献
18.
In this paper, we describe the implementation of some heuristics for convex mixed integer nonlinear programs. The work focuses
on three families of heuristics that have been successfully used for mixed integer linear programs: diving heuristics, the
Feasibility Pump, and Relaxation Induced Neighborhood Search (RINS). We show how these heuristics can be adapted in the context
of mixed integer nonlinear programming. We present results from computational experiments on a set of instances that show
how the heuristics implemented help finding feasible solutions faster than the traditional branch-and-bound algorithm and
how they help in reducing the total solution time of the branch-and-bound algorithm. 相似文献
19.
20.
Stefano Gualandi 《4OR: A Quarterly Journal of Operations Research》2009,7(3):289-292
This is a summary of the author’s Ph.D. thesis supervised by Federico Malucelli and defended on 15 May 2008 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. This work presents new methods for enhancing
the Column Generation approach based on Constraint Programming when it is used for solving combinatorial optimization problems.
The methods proposed focus on the interactions between the linear programming solver and the constraint programming solver,
and on how they impact on both a single iteration and the overall execution of the Column Generation procedure. The result
of this work is the design and implementation of general-purpose optimization algorithms, whose efficiency is proven by solving
two very different problems: the Minimum Graph Coloring Problem and a resource allocation problem arising in Wireless Ad Hoc
Networks. 相似文献