检索结果-内蒙古大学图书馆

On polynomial kernels for sparse integer linear programs

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第5期82卷 758-766页

作者： Kratsch, Stefan Univ Bonn Dept Comp Sci Bonn Germany Univ Utrecht NL-3508 TC Utrecht Netherlands

Successful solvers for integer linear programs (ILPs) demonstrate that preprocessing can greatly speed up the computation. We study preprocessing for ILPs via the theoretical notion of kernelization from parameterized complexity. Prior to our work, there were only implied lower bounds from other problems that hold only for dense instances and do not take into account the domain size. We consider the feasibility problem for ILPs Ax <= where A is an r-row-sparse matrix parameterized by the number of variables, i.e., A has at most r nonzero entries per row, and show that its kernelizability depends strongly on the domain size. If the domain is unbounded then this problem does not admit a polynomial kernelization unless NP subset of coNP/poly. If, on the other hand, the domain size d of each variable is polynomially bounded in n, or if d is an additional parameter, then we do get a polynomial kernelization. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Parameterized complexity Kernelization integer linear programs

来源：评论

学校读者我要写书评

暂无评论

Generator Matrices by Solving integer linear programs 15th

Generator Matrices by Solving Integer Linear Programs

引用

15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC)

作者： Paulin, Lois Coeurjolly, David Bonneel, Nicolas Iehl, Jean-Claude Ostromoukhov, Victor Keller, Alexander Univ Lyon UCBL CNRS INSA LyonLIRIS Villeurbanne France NVIDIA Fasanenstr 81 D-10623 Berlin Germany

ISBN: (纸本)9783031597640;9783031597626;9783031597619

In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of dimensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solving the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.

关键词： Quasi-Monte Carlo methods Low discrepancy sequences Digital (t, m, s)-nets and (t, s)-sequences Generator matrices Optimization integer linear programs

来源：评论

学校读者我要写书评

暂无评论

On the knapsack closure of 0-1 integer linear programs

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 799-804页

作者： Fischetti, Matteo Lodi, Andrea Dipartimento di Ingegneria dell'Informazione University of Padova Padova Italy Dipartimento di Elettronica Informatica e Sistemistica University of Bologna Bologna Italy

Many inequalities for Mixed-integer linear programs (MILPs) or pure integer linear programs (ILPs) are derived from the Gomory corner relaxation, where all the nonbinding constraints at an optimal LP vertex are relaxed. Computational results show that the corner relaxation gives a good approximation of the integer hull for problems with general-integer variables, but the approximation is less satisfactory for problems with 0-1 variables only. A possible explanation is that, for 0-1 ILPs, even the non-binding variable bound constraints x_j≥0 or x_j≤1 play an important role, hence their relaxation produces weaker *** this note we address a relaxation for 0-1 ILPs that explicitly takes all variable bound constraints into account. More specifically, we introduce the concept of knapsack closure as a tightening of the classical Chvátal-Gomory (CG) closure. The knapsack closure is obtained as follows: for all inequalities w^Tx≥w0 valid for the LP relaxation, add to the original system all the valid inequalities for the knapsack polytope conv{xε{0,1}ⁿ:w^Tx≥w₀}. A MILP model for the corresponding separation problem is also introduced. © 2010 Elsevier B.V.

关键词： Cutting plane separation integer linear programs Knapsack Problem

来源：评论

学校读者我要写书评

暂无评论

Methods for closing surrogate dual GAP in integer linear programs

引用

Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice 2002年第9期22卷 70-73,83页

作者： Yang, Jie Chen, Jian-Wen Yin, Qun Ni, Ming-Fang Xi, Yiao-Xin General Staff Ministry of Commun. Beijing 100840 China Nanjing Inst. of Commun. Eng. Nanjing 210016 China

The valid inequalities is applied to surrogate duality in integer programs. The idea for closing surrogate dual gap is presented. Numerical example shows that the methods given in the paper is effective on stronger bo... 详细信息

关键词： Dual gap integer linear programs Surrogate duality

来源：评论

学校读者我要写书评

暂无评论

THE SUPPORT OF integer OPTIMAL SOLUTIONS

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第3期28卷 2152-2157页

作者： Aliev, I. De Loera, J. A. Eisenbrand, F. Oertel, T. Weismantel, R. Cardiff Univ Sch Math Cardiff CF24 4AG S Glam Wales Univ Calif Davis Dept Math Davis CA 95616 USA Ecole Polytech Fed Lausanne Inst Math CH-7015 Lausanne Switzerland Swiss Fed Inst Technol Inst Operat Res CH-8092 Zurich Switzerland

The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m log(2 root m parallel to Lambda parallel to(infinity)), where parallel to Lambda parallel to(infinity) is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.

关键词： support function sparse solutions integer linear programs

来源：评论

学校读者我要写书评

暂无评论

MIXED-integer QUADRATIC-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1982年第3期22卷 332-349页

作者： LAZIMY, R The Hebrew University Jerusalem Israel

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.

关键词： Generalized Benders Decomposition Generalized Inverses integer linear programs Mixed-integer Quadratic Programming Quadratic Duality Theory Quadratic Programming

来源：评论

学校读者我要写书评

暂无评论

Models for the single-vehicle preemptive pickup and delivery problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第2期23卷 196-223页

作者： Kerivin, H. L. M. Lacroix, M. Mahjoub, A. R. Univ Clermont Ferrand CNRS LIMOS UMR 6158 F-63173 Aubiere France

In this paper, we study a variant of the well-known single-vehicle pickup and delivery problem where the demands can be unloaded/reloaded at any node. By proving new complexity results, we give the minimum information which is necessary to represent feasible solutions. Using this, we present integer linear programs for both the unitary and the general versions. We then show that the associated linear relaxations are polynomial-time solvable and present some computational results.

关键词： Pickup and delivery Reloads Minimal representations Complexity integer linear programs Separation problems Preemptive stacker crane problem

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithm for the multicovering problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第2期41卷 433-450页

作者： Gorgi, Abbass El Ouali, Mourad Srivastav, Anand Hachimi, Mohamed Univ Ibn Zohr Agadir Morocco Univ Kiel Kiel Germany

Let H = (V, epsilon) be a hypergraph with maximum edge size l and maximum degree Delta. For a given positive integers b(v), v is an element of V, a set multicover in H is a set of edges C subset of epsilon such that every vertex v in V belongs to at least b(v) edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed Delta and b := min(v is an element of V) b(v), the problem of set multicover is not approximablewithin a ratio less than delta :=Delta-b+1, unlessP = NP. Hence it's a challenge to explore for which classes of hypergraph the conjecture doesn't hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of max {148/149 delta, (1 - (b-1)e(delta/4)/94l)delta} for b >= 2 and delta >= 3. Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it's more general since we set no restriction on the parameter l. Moreover we present a further polynomial time algorithm with an approximation ratio of 5/6 delta for hypergraphs with l <= (1 + epsilon)(l) over bar for any fixed epsilon is an element of [0, 1/2], where (l) over bar is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs.

关键词： integer linear programs Hypergraphs Approximation algorithm Randomized rounding Set cover and set multicover k-matching

来源：评论

学校读者我要写书评

暂无评论

integer linear programming models for a cement delivery problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第3期222卷 623-631页

作者： Hertz, Alain Uldry, Marc Widmer, Marino Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Univ Fribourg Dept Informat Decis Support & Operat Res CH-1700 Fribourg Switzerland

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Vehicle routing Split deliveries integer linear programs

来源：评论

学校读者我要写书评

暂无评论

Exploiting symmetry in integer convex optimization using core points

引用

OPERATIONS RESEARCH LETTERS 2013年第3期41卷 298-304页

作者： Herr, Katrin Rehn, Thomas Schuermann, Achill Tech Univ Darmstadt Fachbereich Math D-64293 Darmstadt Germany Univ Rostock Inst Math D-18051 Rostock Germany

We consider convex programming problems with integrality constraints that are invariant under a linear symmetry group. To decompose such problems, we introduce the new concept of core points, i.e., integral points whose orbit polytopes are lattice-free. For symmetric integer linear programs, we describe two algorithms based on this decomposition. Using a characterization of core points for direct products of symmetric groups, we show that prototype implementations can compete with state-of-the-art commercial solvers, and solve an open MIPLIB problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Symmetry integer linear programs integer convex optimization Core point Core set

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：