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 solvi...
详细信息
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.
Integral simplex using decomposition (ISUD) is a method that efficiently solves set partitioning problems. It is an iterative method that starts from a known integer solution and moves through a sequence of integer so...
详细信息
Integral simplex using decomposition (ISUD) is a method that efficiently solves set partitioning problems. It is an iterative method that starts from a known integer solution and moves through a sequence of integer solutions, decreasing the cost at each iteration. At each iteration, the method decomposes the original problem into a reduced problem (RP) and a complementary problem (CP). Given an integer solution to RP (that is also solution to the original problem), CP finds a descent direction having the minimum ratio between its cost and the number of its positive variables. We loop on until an optimal or near-optimal solution to the original problem is reached. In this paper, we introduce a modified model for CP. The new model finds a descent direction that minimizes the ratio between the cost of the direction and an overestimation of the number of variables taking one in the next solution. The new CP presents higher chances of finding improved integer solutions without branching. We present results for the same large instances (with up to 570,000 columns) as the ones previously used to test ISUD. For all the instances, optimality is always reached with a speedup factor of at least five.
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 itera...
详细信息
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.
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 usin...
详细信息
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.
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 integ...
详细信息
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.
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...
详细信息
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.
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 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.
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. al...
详细信息
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.
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...
详细信息
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.
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 objectiv...
详细信息
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.
暂无评论