共查询到20条相似文献,搜索用时 0 毫秒
1.
We generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method. Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999 相似文献
2.
In this paper we show that the cut does not need to go through the query point: it can be deep or shallow. The primal framework
leads to a simple analysis of the potential variation, which shows that the inequality needed for convergence of the algorithm
is in fact attained at the first iterate of the feasibility step.
Received July 3, 1996 / Revised version received July 11, 1997 Published online August 18, 1998 相似文献
3.
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 相似文献
4.
Solving large quadratic assignment problems on computational grids 总被引:10,自引:0,他引:10
Kurt Anstreicher Nathan Brixius Jean-Pierre Goux Jeff Linderoth 《Mathematical Programming》2002,91(3):563-588
The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming
algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve
QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known
as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is
reported.
Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001 相似文献
5.
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 相似文献
6.
Infeasible-interior-point paths , a positive vector, for a horizontal linear complementarity problem are defined as the solution of () If the path converges for , then it converges to a solution of . This paper deals with the analyticity properties of and its derivatives with respect to r near r = 0 for solvable monotone complementarity problems . It is shown for with a strictly complementary solution that the path , , has an extension to which is analytic also at . If has no strictly complementary solution, then , , has an extension to that is analytic at .
Received May 24, 1996 / Revised version received February 25, 1998 相似文献
7.
We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on
the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only
as many linear programs as the problem has variables.
Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999 相似文献
8.
9.
The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K
n
, a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when
≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe
some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet
inducing.
Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999 相似文献
10.
Levent Tunçel 《Mathematical Programming》1999,86(1):219-223
Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B
-1
A∥2 where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number
was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that
the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1].
Received November 13, 1998 / Revised version received January 20, 1999? Published online May 12, 1999 相似文献
11.
We consider the TU version of Gale and Shapley's roommate game. We find several results that are analogous to known results
for the NTU game, such as a characterization of stable outcomes by forbidden minors, a characterization of the extreme points
of the core, and a median property of stable outcomes. The TU roommate game is a special case of the TU partitioning game
of Kaneko and Wooders. Bondareva and Shapley's balancedness condition for the core of such games is the starting point for
our forbidden minors approach.
Received: April 1999/Revised version: November 2000 相似文献
12.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
13.
theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for
block diagonal semidefinite programs, of which linear programming is a special case.
Received November 26, 1995 / Revised version received November 1, 1998
Published online February 25, 1999 相似文献
14.
András Frank 《Mathematical Programming》1999,84(3):565-576
In order to unify these approaches, here we describe a two-phase greedy algorithm working on a slight extension of lattice polyhedra. This framework includes the rooted node-connectivity augmentation problem, as well, and hence the resulting algorithm, when appropriately specialized, finds a minimum cost of new edges whose addition to a digraph increases its rooted connectivity by one. The only known algorithm for this problem used submodular flows. Actually, the specialized algorithm solves an extension of the rooted edge-connectivity and node-connectivity augmentation problem. Received December 1996 / Revised version received January 1998 Published online March 16, 1999 相似文献
15.
Martin Skutella 《Mathematical Programming》2002,91(3):493-514
In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex
to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed
along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed
a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various
areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing.
Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results
of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques
do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation
results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally,
we provide results on the hardness of approximation for several variants of the problem.
Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001 相似文献
16.
G. Still 《Mathematical Programming》2001,91(1):53-69
The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence
rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending
on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or
two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary
and for generalized semi-infinite problems.
Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001 相似文献
17.
Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove
that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation,
the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling
salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem.
Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999 相似文献
18.
Received June 13, 1995 / Revised version received February 6, 1998 Published online August 18, 1998 相似文献
19.
We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The
concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce
the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are
used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems
with discrete random variables. The results are illustrated with numerical examples.
Received: October 1998 / Accepted: June 2000?Published online October 18, 2000 相似文献
20.
Alexander V. Karzanov 《Combinatorica》1998,18(4):549-568
be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method.
We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer
multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise
open questions.
Received: June 11, 1998 相似文献