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

The complexity of generic primal algorithms for solving general integer programs

MATHEMATICS OF OPERATIONS RESEARCH 2002年第4期27卷 681-692页

作者： Schulz, AS Weismantel, R MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA Univ Magdeburg Fak Math D-39106 Magdeburg Germany

primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with increasingly better objective function value until an optimal solution is reached. From an abstract point of view, an augmentation problem is solved in each iteration. That is, given a feasible point, these methods find an augmenting vector, if one exists. Usually, augmenting vectors with certain properties are sought to guarantee the polynomial running time of the overall algorithm. In this paper, we show that one can solve every integer programming problem in polynomial time provided one can efficiently solve the directed augmentation problem. The directed augmentation problem arises from the ordinary augmentation problem by splitting each direction into its positive and its negative part and by considering linear objectives on these parts. Our main result states that in order to get a polynomial-time algorithm for optimization it is sufficient to efficiently find, for any linear objective function in the positive and negative part, an arbitrary augmenting vector. This result also provides a general framework for the design of polynomial-time algorithms for specific combinatorial optimization problems. We demonstrate its applicability by considering the min-cost flow problem, by giving a novel algorithm for linear programming over unimodular spaces, and by providing a different proof that for 0/1-integer programming an efficient algorithm solving the ordinary augmentation problem suffices for efficient optimization. Our main result also implies that directed augmentation is at least as hard as optimization. In other words, for an NP-hard problem already the task of finding a directed augmenting vector in polynomial time is hopeless, unless P = NP. We illustrate this kind of consequence with the help of the knapsack problem.

关键词： integer programming combinatorial optimization computational complexity primal algorithms augmentation problem

来源：评论

学校读者我要写书评

暂无评论

primal separation algorithms

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2003年第3期1卷 209-224页

作者： Letchford, Adam N. Lodi, Andrea Univ Lancaster Dept Management Sci Lancaster LA1 4YW England Univ Bologna DEIS I-40136 Bologna Italy

Given an integer polyhedron P-I subset of R-n, an integer point (x) over bar is an element of P-I, and a point x* is an element of R-n \ P-I, the primal separation problem is the problem of finding a linear inequality which is valid for P-I, violated by x*, and satisfied at equality by (x) over bar. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.

关键词： Integer programming separation primal algorithms knapsack problem stable set problem travelling salesman problem

来源：评论

学校读者我要写书评

暂无评论

primal methods for variational inequality problems with functional constraints

引用

MATHEMATICAL PROGRAMMING 2025年 1-32页

作者： Zhang, Liang He, Niao Muehlebach, Michael Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Max Planck Inst Intelligent Syst Tubingen Germany

Variational inequality problems are recognized for their broad applications across various fields including machine learning and operations research. First-order methods have emerged as the standard approach for solving these problems due to their simplicity and scalability. However, they typically rely on projection or linear minimization oracles to navigate the feasible set, which becomes computationally expensive in practical scenarios featuring multiple functional constraints. Existing efforts to tackle such functional constrained variational inequality problems have centered on primal-dual algorithms grounded in the Lagrangian function. These algorithms along with their theoretical analysis often require the existence and prior knowledge of the optimal Lagrange multipliers. In this work, we propose a simple primal method, termed Constrained Gradient Method (CGM), for addressing functional constrained variational inequality problems, without requiring any information on the optimal Lagrange multipliers. We establish a non-asymptotic convergence analysis of the algorithm for Minty variational inequality problems with monotone operators under smooth constraints. Remarkably, our algorithms match the complexity of projection-based methods in terms of operator queries for both monotone and strongly monotone settings, while using significantly cheaper oracles based on quadratic programming. Furthermore, we provide several numerical examples to evaluate the efficacy of our algorithms.

关键词： Variational inequality problems Functional constrained optimization Monotone operator Convex optimization primal algorithms

来源：评论

学校读者我要写书评

暂无评论

primal cutting plane algorithms revisited

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2002年第1期56卷 67-81页

作者： Letchford, AN Lodi, A Univ Lancaster Dept Management Sci Lancaster LA1 4YW England Univ Bologna DEIS I-40136 Bologna Italy

Dual functional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost nonexistent. In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.

关键词： integer programming cutting planes primal algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis

引用

INFORMS JOURNAL ON COMPUTING 2015年第4期27卷 773-787页

作者： Omer, Jeremy Rosat, Samuel Raymond, Vincent Soumis, Francois Ecole Polytech Res Grp Decis Anal Montreal PQ H3C 3A7 Canada

In this article, we propose a general framework for an algorithm derived from the primal simplex that guarantees a strict improvement in the objective after each iteration. Our approach relies on the identification of compatible variables that ensure a nondegenerate iteration if pivoted into the basis. The problem of finding a strict improvement in the objective function is proved to be equivalent to two smaller problems, respectively, focusing on compatible and incompatible variables. We then show that the improved primal simplex (IPS) is a particular implementation of this generic theoretical framework. The resulting new description of IPS naturally emphasizes what should be considered as necessary adaptations of the framework versus specific implementation choices. This provides original insight into IPS that allows for the identification of weaknesses and potential alternative choices that would extend the efficiency of the method to a wider set of problems. We perform experimental tests on an extended collection of data sets including instances of Mittelmann's benchmark for linear programming. The results confirm the excellent potential of IPS and highlight some of its limits while showing a path toward an improved implementation of the generic algorithm.

关键词： linear programming simplex degeneracy decomposition primal algorithms

来源：评论

学校读者我要写书评

暂无评论

Integral simplex using decomposition with primal cutting planes

引用

MATHEMATICAL PROGRAMMING 2017年第1-2期166卷 327-367页

作者： Rosat, Samuel Elhallaoui, Issmail Soumis, Francois Lodi, Andrea GERAD CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Ecole Polytech Montreal CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada CERC CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada

This paper concentrates on the addition of cutting planes to the integral simplex using decomposition (ISUD) of Zaghrouti et al. (Oper Res 62(2):435-449, 2014). This method solves the set partitioning problem by iteratively improving an existing feasible solution. We present the algorithm in a primal language and relate it to existing augmenting methods. The resulting theoretical properties, stronger than the ones already known, simplify termination proofs and deepen the geometrical insights on ISUD in particular. We show that primal cuts, that is, cutting planes that are tight at the current feasible integer solution, can be used to improve the performance of the algorithm, and further that such cutting planes are enough to solve each augmentation problem. We propose efficient separation procedures for well-known polyhedral inequalities, namely primal clique and odd-cycle cuts. Numerical results demonstrate the effectiveness of primal cutting planes;tests are performed on small and large-scale set partitioning problems from aircrew and bus-driver scheduling instances up to 1600 constraints and 570,000 variables.

关键词： {0,1}-Programming Integral simplex primal algorithms Set partitioning primal cutting-planes Scheduling

来源：评论

学校读者我要写书评

暂无评论

Integral Simplex Using Decomposition with primal Cuts

引用

13th International Symposium on Experimental algorithms (SEA)

作者： Rosat, Samuel Elhallaoui, Issmail Soumis, Francois Lodi, Andrea Gerad 2920 Ch Tour Montreal PQ H3T 1J4 Canada Polytech Montreal Montreal PQ H3T 1J4 Canada Univ Bologna DEIS I-40136 Bologna Italy

ISBN: (纸本)9783319079592;9783319079585

The integral simplex using decomposition (ISUD) algorithm [22] is a dynamic constraint reduction method that aims to solve the popular set partitioning problem (SPP). It is a special case of primal algorithms, i.e. algorithms that furnish an improving sequence of feasible solutions based on the resolution, at each iteration, of an augmentation problem that either determines an improving direction, or asserts that the current solution is optimal. To show how ISUD is related to primal algorithms, we introduce a new augmentation problem, MRA. We show that MRA canonically induces a decomposition of the augmentation problem and deepens the understanding of ISUD. We characterize cuts that adapt to this decomposition and relate them to primal cuts. These cuts yield a major improvement over ISUD, making the mean optimality gap drop from 33.92% to 0.21% on some aircrew scheduling problems.

关键词： Integer Programming primal algorithms Cutting Planes primal Cuts Constraint Aggregation Decomposition Set Partitioning

来源：评论

学校读者我要写书评

暂无评论

Dynamic penalization of fractional directions in the integral simplex using decomposition: Application to aircrew scheduling

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期263卷 1007-1018页

作者： Rosat, Samuel Quesnel, Frederic Elhallaoui, Issmail Soumis, Francois Polytech Montreal CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada GERAD 3000 Ch Cote St Catherine Montreal PQ H3T 2A7 Canada

To solve integer linear programs, primal algorithms follow an augmenting sequence of integer solutions leading to an optimal solution. In this work, we focus on a particular primal algorithm, the integral simplex using decomposition (ISUD). To find the next point, one solves a linear program to select an augmenting direction for the current point from a cone of feasible directions. To ensure that this linear program is bounded, a normalization constraint is added and the optimization is performed on a section of the cone. The solution of the linear program, i.e., the direction proposed by the algorithm, strongly depends on the chosen normalization weights, and so does the likelihood that the next solution is integer. We modify ISUD so that the normalization is dynamically updated whenever the direction leads to a fractional solution, to penalize that direction. We propose update strategies, based on new theoretical and experimental results. To prove the efficiency of our strategies, we show that our version of the algorithm yields better results than the former version and than classical branch-and-bound techniques on a benchmark of industrial aircrew scheduling instances. The benchmark that we propose here is, to the best of our knowledge, comparable to no other from the literature. It provides large-scale instances with up to 1700 flights and 115,000 pairings, hence as many constraints and variables, and the instances are given in a set-partitioning form together with initial solutions that accurately mimic those of industrial applications. Our work shows the strong potential of primal algorithms for the crew scheduling problem, which is a key challenge for large airlines. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Integer programming primal algorithms Integral simplex Normalization Aircrew scheduling

来源：评论

学校读者我要写书评

暂无评论

Influence of the normalization constraint on the integral simplex using decomposition

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part1期217卷 53-70页

作者： Rosat, Samuel Elhallaoui, Issmail Soumis, Francois Chakour, Driss Polytech Montreal CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Ecole Polytech Route Saclay F-91128 Palaiseau France Gerad 3000 Ch Cote St Catherine Montreal PQ H3T 2A7 Canada

Since its introduction in 1969, the set partitioning problem has received much attention, and the structure of its feasible domain has been studied in detail. In particular, there exists a decreasing sequence of integer feasible points that leads to the optimum, such that each solution is a vertex of the polytope of the linear relaxation and adjacent to the previous one. Several algorithms are based on this observation and aim to determine that sequence;one example is the integral simplex using decomposition (ISUD) of Zaghrouti et al. (2014). In ISUD, the next solution is often obtained by solving a linear program without using any branching strategy. We study the influence of the normalization-weight vector of this linear program on the integrality of the next solution. We extend and strengthen the decomposition theory in ISUD, prove theoretical properties of the generic and specific normalization constraints, and propose new normalization constraints that encourage integral solutions. Numerical tests on scheduling instances (with up to 500,000 variables) demonstrate the potential of our approach. (C) 2016 Elsevier B.V. All rights reserved.

关键词： 0-1 programming Set partitioning problem primal algorithms Normalization constraint Augmenting algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear programming decomposition focusing on the span of the nondegenerate columns

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第2期245卷 371-383页

作者： Omer, Jeremy Soumis, Francois Ecole Polytech Montreal PQ H3T 1J4 Canada HEC Montral Grp Res Decis Anal Montreal PQ H3T 2A7 Canada

The improved primal simplex (IPS) was recently developed by Elhalaloui et al. to take advantage of degeneracy when solving linear programs with the primal simplex. It implements a dynamic constraint reduction based on the compatible columns, i.e., those that belong to the span of a given subset of basic columns including the nondegenerate ones. The identification of the compatible variables may however be computationally costly and a large number of linear programs are solved to enlarge the subset of basic variables. In this article, we first show how the positive edge criterion of Raymond et al. can be included in IPS for a fast identification of the compatible variables. Our algorithm then proceeds through a series of reduction and augmentation phases until optimality is reached. In a reduction phase, we identify compatible variables and focus on them to make quick progress toward optimality. During an augmentation phase, we compute one greatest normalized improving direction and select a subset of variables that should be considered in the reduced problem. Compared with IPS, the linear program that is solved to find this direction involves the data of the original constraint matrix. This new algorithm is tested over Mittelmann's benchmark for linear programming and on instances arising from industrial applications. The results show that the new algorithm outperforms the primal simplex of CPLEX on most highly degenerate instances in which a sufficient number of nonbasic variables are compatible. In contrast, IPS has difficulties on the eleven largest Mittelmann instances. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Linear programming Degeneracy Improved primal simplex Decomposition primal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：