共查询到20条相似文献,搜索用时 31 毫秒
1.
《Operations Research Letters》2022,50(2):122-128
The max-cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results. 相似文献
2.
We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semi-assignment problem to hub location problems with some computational experiences. 相似文献
3.
We consider the vertex-weighted version of the undirected Steiner tree problem. In this problem, a cost is incurred both for the vertices and the edges present in the Steiner tree. We completely describe the associated polytope by linear inequalities when the underlying graph is series—parallel. For general graphs, this formulation can be interpreted as a (partial) extended formulation for the Steiner tree problem. By projecting this formulation, we obtain some very large classes of facet-defining valid inequalities for the Steiner tree polytope.Research supported by Air Force contract AFOSR-89-0271 and DARPA contract DARPA-89-5-1988. 相似文献
4.
In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm. 相似文献
5.
This note refers to the article by G. Ghiani and G. Laporte ``A branch-and-cut algorithm for the Undirected Rural Postman
Problem', Math. Program. 87 (2000). We show that some conditions for the facet-defining property of the basic non-trivial inequalities are not sufficient
and that the Rural Postman Problem polytope is more complex even when focusing on canonical inequalities only. 相似文献
6.
7.
We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (On the travelling salesman problem II: Lifting theorems and facets) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope. 相似文献
8.
Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment
problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the
polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic
assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these
polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining)
inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class
of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the
cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very
useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The
most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as
for the symmetric quadratic assignment polytope.
Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001 相似文献
9.
A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).Partially financed by P.R.C. Mathématique et Informatique. 相似文献
10.
11.
Rudolf Müller 《Mathematical Programming》1996,73(1):31-49
We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete. 相似文献
12.
The nth Birkhoff polytope is the set of all doubly stochastic n
× n matrices, that is, those matrices with nonnegative real coefficients
in which every row and column sums to one. A wide open problem concerns the
volumes of these polytopes, which have been known for n $\leq$ 8. We present a
new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff
polytope, that is, the function counting the integer points in the dilated
polytope. One reason to be interested in this counting function is that the
leading term of the Ehrhart polynomial is—up to a trivial factor—the volume
of the polytope. We implemented our methods in the form of a computer program,
which yielded the Ehrhart polynomial (and hence the volume) of the ninth
Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope. 相似文献
13.
Yongpei Guan Shabbir Ahmed George L. Nemhauser Andrew J. Miller 《Mathematical Programming》2006,105(1):55-84
This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under
uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend
the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness
of the inequalities as cuts.
This research has been supported in part by the National Science Foundation under Award number DMII-0121495. 相似文献
14.
The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral. 相似文献
15.
Gerhard Reinelt 《Discrete Applied Mathematics》2008,156(3):368-384
The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467-481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP. 相似文献
16.
17.
Hernán Abeledo Ricardo Fukasawa Artur Pessoa Eduardo Uchoa 《Mathematical Programming Computation》2013,5(1):27-55
The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices. 相似文献
18.
It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest. 相似文献
19.
R.L.M.J. van de Leensel C.P.M. van Hoesel J.J. van de Klundert 《Mathematical Programming》1999,86(1):161-185
This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid
inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining
these facets using the standard sequential lifting procedure. Applying this procedure requires solving a combinatorial problem.
For valid inequalities arising from minimal induced covers, we identify a class of lifting coefficients for which this problem
can be solved in polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have
a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly
NP-hard. The same lifting procedure can be applied to (1,k)-configurations, although in this case, the same combinatorial
interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show
that facets of the polytope can still be generated using a similar lifting technique. For tree knapsack problems, we observe
that all lifting coefficients can be obtained in polynomial time. Computational experiments indicate that these facets significantly
strengthen the LP-relaxation.
Received July 10, 1997 / Revised version received January 9, 1999? Published online May 12, 1999 相似文献
20.
《Optimization》2012,61(2):223-233
The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities. 相似文献