共查询到20条相似文献,搜索用时 46 毫秒
1.
Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer
programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given
a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities
for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset
of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities
are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base
inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various
mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location,
capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing
procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure.
Received: April 1998 / Accepted: January 2001?Published online April 12, 2001 相似文献
3.
The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities.
It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been
fruitful in the analysis of the stable marriage problem.
Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000 相似文献
4.
n such that x≥0, F(x,u)-v≥0 , and F(x,u)-v T·x=0 where these are vector inequalities. We characterize the local upper Lipschitz continuity of the (possibly set-valued)
solution mapping which assigns solutions x to each parameter pair (v,u). We also characterize when this solution mapping is
locally a single-valued Lipschitzian mapping (so solutions exist, are unique, and depend Lipschitz continuously on the parameters).
These characterizations are automatically sufficient conditions for the more general (and usual) case where v=0. Finally,
we study the differentiability properties of the solution mapping in both the single-valued and set-valued cases, in particular
obtaining a new characterization of B-differentiability in the single-valued case, along with a formula for the B-derivative.
Though these results cover a broad range of stability properties, they are all derived from similar fundamental principles
of variational analysis.
Received March 30, 1998 / Revised version received July 21, 1998
Published online January 20, 1999 相似文献
5.
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
6.
We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete
characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex
hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify
conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex
hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in
the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We
evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job
completion times subject to release dates.
Received March 24, 1994 / Revised version received February 13, 1997
Published online June 28, 1999 相似文献
7.
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem,
and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for
proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of
ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the
regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds
are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized
gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact
proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method,
while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance
rules is also discussed.
Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000 相似文献
8.
Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model
for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This
work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted
Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others
are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided.
Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance
of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals
in a few minutes.
Received: August 1999 / Accepted: January 2001?Published online April 12, 2001 相似文献
9.
The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many
closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization
(constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard
constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull
intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived
and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result
on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is
quantified by the angle between the subspaces.
Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999 相似文献
10.
We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the p-cycles. We describe a model for designing capacitated survivable networks based on directed p-cycles. We motivate this model by comparing it with other means of ensuring survivability, and present a mixed-integer programming formulation for it. We derive valid inequalities for the model based on the minimum capacity requirement between partitions of the nodes and give facet conditions for them. We discuss the separation for these inequalities and present results of computational experiments for testing their effectiveness as cutting planes when incorporated in a branch-and-cut algorithm. Our experiments show that the proposed inequalities reduce the computational effort significantly. 相似文献
11.
We deal with the problem of estimating some unknown regression function involved in a regression framework with deterministic
design points. For this end, we consider some collection of finite dimensional linear spaces (models) and the least-squares
estimator built on a data driven selected model among this collection. This data driven choice is performed via the minimization
of some penalized model selection criterion that generalizes on Mallows' C
p
. We provide non asymptotic risk bounds for the so-defined estimator from which we deduce adaptivity properties. Our results
hold under mild moment conditions on the errors. The statement and the use of a new moment inequality for empirical processes
is at the heart of the techniques involved in our approach.
Received: 2 July 1997 / Revised version: 20 September 1999 / Published online: 6 July 2000 相似文献
12.
Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated
or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral
structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided
solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the
undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of
network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations
of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of
the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities
for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes
the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem
itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially
reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem
for solving network loading problems.
Received: September 2000 / Accepted: October 2001?Published online March 27, 2002 相似文献
13.
The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints.
We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the
value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds
of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions
for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our
conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms
of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz
case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two
directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do
not assume that the Slater condition holds which has been required in almost all earlier papers.
Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000 相似文献
14.
1 ,E 2,..., such that ⋃ i≤τE i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge
sets can be divided into O(n) groups such that within one group, all E i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we
give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called
extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs
with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional
hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs.
Received November 1995 / Revised version received July 1998
Published online March 16, 1999 相似文献
15.
We give a new negative solution to Keisler's problem regarding Skolem functions and elementary extensions. In contrast to
existing ad hoc solutions due to Payne, Knight, and Lachlan, our solution uses well-known models.
Received: 20 September 1999 / Published online: 21 March 2001 相似文献
16.
Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs.
When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer
variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more
effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure
does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information
into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets
with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques
can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous
cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous
integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In
addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53,
2006) under some conditions. 相似文献
17.
Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is
most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes
is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point
of view. The real–world application we aim at is the control of a stacker crane in a warehouse.?We have implemented codes
based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results
for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms
the other two models we considered – at least for our special application – and that the heuristics provide acceptable solutions.
Received: August 1999 / Accepted: September 2000?Published online April 12, 2001 相似文献
18.
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the
box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions,
we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent
nonsmooth equation H(u,x)=0, where H:ℜ
2n
→ℜ
2n
, u∈ℜ
n
is a parameter variable and x∈ℜ
n
is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence { z
k
=( u
k
,x
k
)} such that the mapping H(·) is continuously differentiable at each z
k
and may be non-differentiable at the limiting point of { z
k
}. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which
play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not
require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if
we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the
proposed methods for particularly chosen smoothing functions are very promising.
Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999 相似文献
19.
We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances. 相似文献
20.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation
methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming)
Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems
have a linear objective function c
T
x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,”
into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number
of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of
standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?• Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method
which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for
a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?• Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method
which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000 相似文献
|