共查询到20条相似文献,搜索用时 31 毫秒
1.
We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases. 相似文献
2.
The best formulations for some combinatorial optimization problems are integer linear programming models with an exponential number of rows and/or columns, which are solved incrementally by generating missing rows and columns only when needed. As an alternative to row generation, some exponential formulations can be rewritten in a compact extended form, which have only a polynomial number of constraints and a polynomial, although larger, number of variables. As an alternative to column generation, there are compact extended formulations for the dual problems, which lead to compact equivalent primal formulations, again with only a polynomial number of constraints and variables. In this this paper we introduce a tool to derive compact extended formulations and survey many combinatorial optimization problems for which it can be applied. The tool is based on the possibility of formulating the separation procedure by an LP model. It can be seen as one further method to generate compact extended formulations besides other tools of geometric and combinatorial nature present in the literature. 相似文献
3.
LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been
considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations
are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added).
This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation
of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations.
Computational results using the extended formulations are performed. 相似文献
4.
Michele Conforti Gérard Cornuéjols Giacomo Zambelli 《Annals of Operations Research》2013,204(1):97-143
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski-Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set, and we present the proof of Fiorini, Massar, Pokutta, Tiwary and de Wolf of an exponential lower bound for the cut polytope. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. 相似文献
5.
《Operations Research Letters》2019,47(5):458-463
This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively. 相似文献
6.
Extended formulations in combinatorial optimization 总被引:1,自引:0,他引:1
Michele Conforti Gérard Cornuéjols Giacomo Zambelli 《4OR: A Quarterly Journal of Operations Research》2010,8(1):1-48
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”,
we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect
formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem.
Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation
with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various
tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem,
Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming,
and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied.
In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings,
and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’
result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. 相似文献
7.
8.
9.
Matthias Kppe Quentin Louveaux Robert Weismantel Laurence A. Wolsey 《Discrete Optimization》2004,1(2):141-165
We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory's group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation. 相似文献
10.
E.J.P. Miranda S.F. Rodrigues C. Aranas J.M.C. Dos Santos 《Journal of Mathematical Analysis and Applications》2022,505(2):125503
The plane wave expansion (PWE) and the extended plane wave expansion (EPWE) formulations are derived in order to obtain the complex dispersion relation of flexural waves in a metamaterial Mindlin-Reissner thick plate with multiple periodic resonators. These new formulations are useful to obtain more accurate results at higher frequencies than those based on Kirchhoff-Love thin plate theory. Multiple periodic resonators with multiple degrees of freedom (M-DOF) attached to metamaterial thick plates broaden the applications for wave attenuation in high frequencies. 相似文献
11.
Lot-sizing with production and delivery time windows 总被引:3,自引:0,他引:3
Laurence A. Wolsey 《Mathematical Programming》2006,107(3):471-489
We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production
time windows, in which each client specific order must be produced within a given time interval, we derive tight extended
formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the
variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we
also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic
programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs.
For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant
capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs.
We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI
takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438.
This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. 相似文献
12.
13.
El-Nabulsi Ahmad Rami 《Applied mathematics and computation》2011,217(22):9492-9496
In this letter, we study the fractional variational problems from extended exponentially fractional integral. Both the Lagrangian and Hamiltonian formulations are explored and discussed in some details. Some interesting consequences are revealed. 相似文献
14.
Ya. N. Shitov 《Doklady Mathematics》2015,92(3):707-708
Results related to extended formulations for convex polygons are discussed. In particular, it turns out that six linear inequalities are sufficient to describe a convex heptagon up to linear projection. 相似文献
15.
Due to its complexities in both mathematicM formulations and applications, universal co-kriging (UCK) has not been sufficiently discussed in literature. An extended and simpler matrix formulation UCK with incorporation of a polynomial variable trend is proposed in this paper. Estimators of the value and expectation of a regionMized vector taken in a point are obtained on the basis of cross-covaxiance and cross-vaxiogram, respectively. The complex expressions of co-kriging with trend are greatly simplified by introducing special matrix operations, such as Kronecker product, into the formulations. This simplification offers a feasible and easier approach for computer coding of the UCK, and helps the practitioners to use the UCK technique conveniently in real cases. 相似文献
16.
《Operations Research Letters》2022,50(1):1-7
Fisher linear discriminant analysis is a well-known technique for dimensionality reduction and classification. The method was first formulated in 1936 by Fisher. In this paper we concentrate on three different formulations of the multi-dimensional problem. We provide a mathematical explanation why two of the formulations are equivalent and prove that this equivalency can be extended to a broader class of objective functions. The second contribution is a rate of convergence of a fixed point method for solving the third model. 相似文献
17.
D. P. Babii S. K. Godunov V. T. Zhukov O. B. Feodoritova 《Computational Mathematics and Mathematical Physics》2007,47(3):427-441
Issues concerning difference approximations of overdetermined systems of hyperbolic equations are examined. The formulations of extended overdetermined systems are given for hydrodynamics equations, magnetohydrodynamics equations, Maxwell equations, and elasticity equations. Some approaches to the construction of difference schemes are discussed for these systems. 相似文献
18.
The many-to-many location-routing problem 总被引:1,自引:0,他引:1
In this paper the many to many location routing problem is introduced, and its relationship to various problems in distribution
management is emphasised. Useful mathematical formulations which can be easily extended to cater for other related problems
are produced. Techniques for tackling this complex distribution problem are also outlined. 相似文献
19.
Egon Balas 《Annals of Operations Research》2005,140(1):125-161
This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial
optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful
bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection
and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets
of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection
for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by
using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra,
whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation
of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter
and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed
0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut
generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently
discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it,
by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals
with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project
cuts.
This is an updated and extended version of the paper published in LNCS 2241, Springer, 2001 (as given in Balas, 2001).
Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through
contract N00014-97-1-0196. 相似文献
20.
In this contribution three mixed least-squares finite element methods (LSFEMs) for the incompressible Navier-Stokes equations are investigated with respect to accuracy and efficiency. The well-known stress-velocity-pressure formulation is the basis for two further div-grad least-squares formulations in terms of stresses and velocities (SV). Advantage of the SV formulations is a system with a smaller matrix size due to a reduction of the degrees of freedom. The least-squares finite element formulations, which are investigated in this contribution, base on the incompressible stationary Navier-Stokes equations. The first formulation under consideration is the stress-velocity-pressure formulation according to [1]. Secondly, an extended stress-velocity formulation with an additional residual is derived based on the findings in [1] and [5]. The third formulation is a pressure reduced stress-velocity formulation based on a condensation scheme. Therefore, the pressure is interpolated discontinuously, and eliminated on the discrete level without the need for any matrix inverting. The modified lid-driven cavity boundary value problem, is investigated for the Reynolds number Re = 1000 for all three formulations. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献