排序方式: 共有22条查询结果,搜索用时 15 毫秒
1.
2.
Safe bounds in linear and mixed-integer linear programming 总被引:1,自引:0,他引:1
Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.
Mathematics Subject Classification (2000):primary 90C11, secondary 65G20 相似文献
3.
Three formulations for the Minimum 2-Connected Dominating Set Problem, valid inequalities, a primal heuristic and Branch-and-Cut algorithms are introduced in this paper. As shown here, the preliminary computational results so far obtained indicate that these algorithms are quite promising. 相似文献
4.
In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement. 相似文献
5.
In radio communications, a set of links that can transmit in parallel with a tolerable interference is called a compatible set. Finding a compatible set with maximum weighted revenue of the parallel transmissions is an important subproblem in wireless network management. For the subproblem, there are two basic approaches to express the signal to interference plus noise ratio (SINR) within integer programming, differing in the number of variables and the quality of the upper bound given by linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of the two approaches. The contribution of the paper is two-fold. Firstly, we present such a comparison, and, secondly, we introduce matching inequalities improving the upper bounds as compared to the two basic approaches. The matching inequalities are generated within a branch-and-cut algorithm using a minimum odd-cut procedure based on the Gomory-Hu algorithm. The paper presents results of extensive numerical studies illustrating our statements and findings. 相似文献
6.
7.
The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce in an elegant way various problems of robust control into its form. However, in contrast to the Linear Matrix Inequality (LMI), which can be solved by interior-point-methods, the BMI is a computationally difficult object in theory and in practice. This article improves the branch-and-bound algorithm of Goh, Safonov and Papavassilopoulos (Journal of Global Optimization, vol. 7, pp. 365–380, 1995) by applying a better convex relaxation of the BMI Eigenvalue Problem (BMIEP), and proposes new Branch-and-Bound and Branch-and-Cut Algorithms. Numerical experiments were conducted in a systematic way over randomly generated problems, and they show the robustness and the efficiency of the proposed algorithms. 相似文献
8.
We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values. 相似文献
9.
We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000).In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem. 相似文献
10.
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 相似文献