During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integerprogramming polyhedrons. However, no such class has had as much practical success as the MI...
详细信息
ISBN:
(纸本)9783540727910
During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integerprogramming polyhedrons. However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integerprogramming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed integer polyhedron, and either proves the point is in the convex hull of said polyhedron, or finds a separating hyperplane. the main feature of this algorithm is a specialized subroutine for solving the Mixed integer Knapsack Problem which exploits cost and lexicographic dominance. Separating over the entire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.
this paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined...
详细信息
ISBN:
(纸本)9783540727910
this paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. this characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. the algorithm runs in O(gamma) time, where gamma is the number of the nonzero coefficients.
We describe new algorithms for solving linear programming relaxations of very large precedence constrained production scheduling problems. We present theory that motivates a new set of algorithmic ideas that;can be em...
详细信息
ISBN:
(纸本)9783642130359
We describe new algorithms for solving linear programming relaxations of very large precedence constrained production scheduling problems. We present theory that motivates a new set of algorithmic ideas that;can be employed on a wide range of problems;on data sets arising in the mining industry our algorithms prove effective on problems with many millions of variables and constraints, obtaining provably optimal solutions in a few minutes of computation(1).
For a graph G and a collection of vertex pairs {(s(1), t(1)),..., (s(k), t(k))}, the disjoint paths problem is to find k vertex-disjoint paths P-1,..., P-k, where P-i is a path from s(i) to t(i) for each i = 1,..., k....
详细信息
ISBN:
(纸本)9783540688860
For a graph G and a collection of vertex pairs {(s(1), t(1)),..., (s(k), t(k))}, the disjoint paths problem is to find k vertex-disjoint paths P-1,..., P-k, where P-i is a path from s(i) to t(i) for each i = 1,..., k. this problem is one of the classic problems in combinatorialoptimization and algorithmic graph theory, and has many applications, for example in transportation networks, VLSI layout, and recently, virtual circuits routing in high-speed networks. As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s(1,) t(1)),..., (s(k), t(k))}. the objective is to find k paths P-i,..., P-k such that Pi is a path from si to ti and P-i and P-j have neither common vertices nor adjacent vertices for any distinct i,j. this problem setting is a generalization of the disjoint paths problem, since if we subdivide each edge, then desired disjoint paths would be induced disjoint paths. the problem is motivated by not only the disjoint paths problem but also the recognition of an induced subgraph. the latter has been developed in the recent years, and this is actually connected to the Strong Perfect Graph theorem [4], and the recognition of the perfect graphs [2]. In this paper, we shall investigate the complexity issues of this problem. the induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed planar graph, (ii) solvable in linear time when k is fixed and G is an undirected planar graph, (iii) NP-hard when k = 2 and G is an acyclic directed graph, (iv) NP-hard when k = 2 and G is an undirected general graph. (i) generalizes the result by Schrijver [22], while (ii) genera
We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the nontrivial facet-defining inequalit...
详细信息
ISBN:
(纸本)9783540727910
We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the nontrivial facet-defining inequalities for MEP. this result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory [9] and for the Master Knapsack Polyhedron by Araoz [1]. Furthermore, this characterization also gives a polynomial time algorithm for separating an arbitrary point from the MEP. We describe how facet defining inequalities for the Master Cyclic Group Polyhedron can be lifted to obtain facet defining inequalities for the MEP, and also present facet defining inequalities for the MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of the MEP and present an interpolation theorem that produces valid inequalities for general Mixed integerprogramming Problems using facets of the MEP.
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results....
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. the robustness considered is w.r.t. adversarial removal of a given number of elements from the chosen set. In particular, for the fundamental case of single element removal, we show that one can approximate the problem up to a factor (1 - 1/e) - epsilon by making O(n(1/epsilon)) queries, for arbitrary epsilon > 0. the ideas are also extended to more general settings.
In this study, the performance of the modified subgradient algorithm (MSG) to solve the 0-1 quadratic knapsack problem (QKP) is examined. the MSG is proposed by Gasimov for solving dual problems constructed with respe...
详细信息
ISBN:
(纸本)9789955282839
In this study, the performance of the modified subgradient algorithm (MSG) to solve the 0-1 quadratic knapsack problem (QKP) is examined. the MSG is proposed by Gasimov for solving dual problems constructed with respect to sharp Augmented Lagrangian function. the MSG has some important proven properties. For example, it is convergent, and it guarantees the zero duality gap for the problems such that its objective and constraint functions are all Lipschtz. Besides it doesn't need to be convexity or differentiability conditions on the primal problem. the MSG has successfully used for solving nonconvex continuous and some combinatorial problems with equality constraints since it was suggested. In this study, the MSG is used to solve the QKP which is one of the well known combinatorialoptimization problems with inequality constraint. Firstly, zero-one nonlinear problem is converted into continuous nonlinear problem by adding only one constraint and not adding new variables, then to solve the continuous QKP, dual problem with "zero duality gap" is constructed by using the sharp Augmented Lagrangian function. Finally, to solve the dual problem, the MSG is used by considering the equality constraint in the computation of the norm. the proposed approach is applied for some test problems. the results are also presented and discussed.
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Pr...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
 \subseteq$
 \subseteq ? n , the fractional packing problem is to find an x ∈ P such t...
ISBN:
(纸本)3540660194
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
\subseteq$
\subseteq ? n , the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists.
We show how to efficiently model binary constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear prog...
详细信息
ISBN:
(纸本)9783540723967
We show how to efficiently model binary constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear programming description of the convex hull of all integer feasible solutions when the BCP that is given has bounded tree-width.
暂无评论