共查询到20条相似文献,搜索用时 15 毫秒
1.
Nimrod Megiddo 《Mathematical Programming》1986,35(3):365-367
We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best vertex (which is highly degenerate) is already given. So, to solve the latter, it is sufficient to exit that vertex in a direction that improves the objective function value. 相似文献
2.
A technique for the resolution of degeneracy in an Active Set Method for Quadratic Programming is described. The approach generalises Fletcher's method [2] which applies to the LP case. The method is described in terms of an LCP tableau, which is seen to provide useful insights. It is shown that the degeneracy procedure only needs to operate when the degenerate constraints are linearly dependent on those in the active set. No significant overheads are incurred by the degeneracy procedure. It is readily implemented in a null space format, and no complications in the matrix algebra are introduced.The guarantees of termination provided by [2], extending in particular to the case where round-off error is present, are preserved in the QP case. It is argued that the technique gives stronger guarantees than are available with other popular methods such as Wolfe's method [11] or the method of Goldfarb and Idnani [7].Presented at the 14th International Symposium on Mathematical Programming, Amsterdam, August 5–9, 1991. 相似文献
3.
4.
《Discrete Applied Mathematics》1988,21(2):169-172
The system of two equations in nonnegative integer unknowns xj and expressed in the form ∑nj=1 a1jxj=b1, ∑nj=1 a2jxj=b2 has equivalent solutions to the single equation ∑nj=1 (t1aij+t2a2j)aj= t1b1+t2b2, provided t1 and t2 are suitably chosen. Glover [2] has n inequalities for determining t1 and t2. Elimam and Elmaghraby [1] try to achieve a single inequality for t1 and t2. We show, however, that the inequality of [1] may give t1 and t2 values that do not produce equivalence. We present a new theorem which leads to a single inequality constraint giving t1 and t2 values that consistently produce equivalence. 相似文献
5.
In the b-coloring problem, we aim to assign colors from a set to the vertices of a graph in such a way that adjacent vertices do not receive the same color, and for every we have a -colored vertex in such that every color in is assigned to at least one of ’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. 相似文献
6.
A hybrid algorithm to solve large scale zero–one integer programming problems has been developed. The algorithm combines branch-and-bound, enumeration and cutting plane techniques. Mixed-integer cuts are generated in the initial phase of the algorithm and added to the L.P. Benders cuts are derived and used implicitly but, except for the cut from the initial LP, are not stored. The algorithm has been implemented on an experimental basis in MPSX/370 using its Extended Control Language and Algorithmic Tools. A computational study based on five well-known difficult test problems and on three practical problems with up to 2000 zer–one variables shows that the hybrid code compares favorably with MIP/370 and with results published for other algorithms. 相似文献
7.
《European Journal of Operational Research》1988,34(3):393-398
The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model. 相似文献
8.
Laurence A. Wolsey 《Mathematical Programming》1973,4(1):222-232
When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek
th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk
th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed. 相似文献
9.
Gwo Dong Lin 《Mathematical Methods of Operations Research》1986,30(1):A79-A82
To aggregate constraints is a technique for solving the integer programming problem. In this note we modify a result of Zionts (1974); without this modification, there is a counterexample for Zionts' result. Further, we give an elegant theorem which considers the aggregation of nonlinear constraints.This work was partially supported by the Chinese National Science Council. 相似文献
10.
The separable integer programming problem with so called nested constraints is shown to be equivalent to its continual version obtained by piecewise linear continuation of the cost functions. A new approach to solution of the latter based on its successive reduction in size is suggested. When applied to the problem with piecewise linear convex functions it leads to two algorithms for its solution applicable also to the similar integer problem. These algorithms turn out more efficient than those obtained by dynamic programming approach. 相似文献
11.
Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough. 相似文献
12.
Claude-Alain Burdet 《Mathematical Programming》1972,2(1):32-64
For a linear integer programming problem, thelocal information contained at an optimal solution
of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use ofenvironmental information (of a global nature but pertaining to the discrete vicinity of
), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept ofenumerative inequalities is introduced and it is shown how it can be obtained in the context of the convex outer-domain theory of Balas, Young, et al.Generally speaking, enumerative inequalities can be made arbitrarily strong (deep), but at the cost of an increasing amount of work (i.e. enumeration) for their construction. In particular cases, however, very little global information can produce enumerative inequalities stronger than anyvalid cut.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands. 相似文献
13.
14.
Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable. 相似文献
15.
H.P Williams 《Journal of Combinatorial Theory, Series A》1976,21(1):118-123
This paper describes how the Fourier-Motzkin Elimination Method, which can be used for solving Linear Programming Problems, can be extended to deal with Integer Programming Problems. The extension derives from a known decision procedure for the formal theory of a fragment of arithmetic which excludes multiplication. 相似文献
16.
In this study, we combine least-index pivot selection rules with Keller's algorithm for quadratic programming to obtain a finite method for processing degenerate problems.Research and reproduction of this report were partially supported by National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267. 相似文献
17.
We show that a 2-variable integer program, defined by m constraints involving coefficients with at most bits, can be solved with O(m+) arithmetic operations on rational numbers of size O(). 相似文献
18.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
19.
In this review we describe recent developments in linear and integer (linear) programming. For over 50 years Operational Research practitioners have made use of linear optimisation models to aid decision making and over this period the size of problems that can be solved has increased dramatically, the time required to solve problems has decreased substantially and the flexibility of modelling and solving systems has increased steadily. Large models are no longer confined to large computers, and the flexibility of optimisation systems embedded in other decision support tools has made on-line decision making using linear programming a reality (and using integer programming a possibility). The review focuses on recent developments in algorithms, software and applications and investigates some connections between linear optimisation and other technologies. 相似文献
20.
D.R. Woodall 《Discrete Mathematics》1977,17(2):215-218
An attempt is made, with only partial success, to obtain integer analogues of some linear-programming results that are useful in combinatorics. 相似文献