A predictor-corrector method is proposed for solving standard form linear programming problems starting from initial points that strictly satisfy the positivity constraints, but do not necessarily satisfy the equality...
详细信息
A predictor-corrector method is proposed for solving standard form linear programming problems starting from initial points that strictly satisfy the positivity constraints, but do not necessarily satisfy the equality constraints. The algorithm is globally convergent under the assumption that the linear program has an optimal solution. Under some additional assumptions on the starting point we prove that epsilon-feasibility and epsilon-complementarity can be obtained in O(nln(1/epsilon)) iterations.
In this article we propose a polynomial-time algorithm for linear programming. This algorithm augments the objective by a logarithmic penalty function and then solves a sequence of quadratic approximations of this pro...
详细信息
In this article we propose a polynomial-time algorithm for linear programming. This algorithm augments the objective by a logarithmic penalty function and then solves a sequence of quadratic approximations of this program. This algorithm has a complexity of O (m 1 2 L) iterations and O( m 3.5 L ) arithmetic operations, where m is the number of variables and L is the size of the problem encoding in binary. The novel feature of this algorithm is that it admits a very simple proof of its complexity, which makes it valuable both as a teaching and as a research tool. Moreover, its convergence can be accelerated by performing a line search and the line search stepsize is obtainable in a closed form. This algorithm maintains primal and dual feasibility at all iterations.
Influence maximization is an important research topic in social networks that has different applications such as analyzing spread of rumors, interest, adoption of innovations, and feed ranking. The goal is to select a...
详细信息
Influence maximization is an important research topic in social networks that has different applications such as analyzing spread of rumors, interest, adoption of innovations, and feed ranking. The goal is to select a limited size subset of vertices (called a seed-set) in a Social Graph, so that upon their activation, a maximum number of vertices of the graph become activated, due to the influence of the vertices on each other. The linear threshold model is one of two classic stochastic propagation models that describe the spread of influence in a network. We present a new approach called MLPR (matrix multiplication, linear programming, randomized rounding) with linear programming used as its core in order to solve the influence maximization problem in the linear threshold model. Experiments on four real data sets have shown the efficiency of the MLPR method in solving the influence maximization problem in the linear threshold model. The spread of the output seed-sets is as large as when the state-of-the-art algorithms are used;however, unlike most of the existing algorithms, the runtime of our method is independent of the seed size and does not increase with it.
This paper presents a new procedure for solving the integer linear programming problem when the objective function is a linear function and the set of constraints is in the form of linear inequality constraints. The p...
详细信息
This paper presents a new procedure for solving the integer linear programming problem when the objective function is a linear function and the set of constraints is in the form of linear inequality constraints. The proposed procedure is based on the conjugate gradient projection method together with the use of the spirit of Gomory cut. The main idea behind our method is to move through the feasible region through a sequence of points in the direction that improves the objective function. Since methods based on vertex information may have difficulties as the problem size increases, therefore, the present method can be considered as an interior point method, which had been proved to be less sensitive to problem size. A simple production example is given to clarify the theory of this new procedure.
The primal-dual infeasible-interior-point algorithm is known as one of the most efficient computational methods for linear programs. Recently, a polynomial-time computational complexity bound was established for speci...
详细信息
The primal-dual infeasible-interior-point algorithm is known as one of the most efficient computational methods for linear programs. Recently, a polynomial-time computational complexity bound was established for special variants of the algorithm. However, they impose severe restrictions on initial points and require a common step length in the primal and dual spaces. This paper presents some basic lemmas that bring great flexibility and improvement into such restrictions on initial points and step lengths, and discusses their extensions to linear and nonlinear monotone complementarity problems.
As in many primal-dual interior-point algorithms, a primal-dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the...
详细信息
As in many primal-dual interior-point algorithms, a primal-dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.
We propose a new decomposition method for large-scale linear programming. This method dualizes an (arbitrary) subset of the constraints and then maximizes the resulting dual functional by dual ascent. The ascent direc...
详细信息
We propose a new decomposition method for large-scale linear programming. This method dualizes an (arbitrary) subset of the constraints and then maximizes the resulting dual functional by dual ascent. The ascent directions are chosen from a finite set and are generated by a truncated version of the painted index algorithm of Rockafellar. Central to this method is the novel notion of (epsilon, delta)-complementary slackness (epsilon greater-than-or-equal-to 0, delta is-an-element-of [0, 1]) which allows each Lagrangian subproblem to be solved only approximately with O(epsilon-delta) accuracy and provides a lower bound of OMEGA(epsilon(1 - delta)) on the amount of improvement per dual ascent. By dynamically adjusting epsilon, the subproblems can be solved with increasing accuracy. We show that (i) the method terminates finitely, provided that epsilon and delta are bounded away from 0 and 1, respectively, (ii) the final solution produced by the method is feasible and is within O(epsilon) in cost of the optimal cost, and (iii) the final solution produced by the method is optimal for all epsilon sufficiently small.
In this paper we provide an (O) over tilde (nd + d(3)) time randomized algorithm for solving linear programs with d variables and n constraints with high probability. To obtain this result we provide a robust, primald...
详细信息
ISBN:
(纸本)9781450369794
In this paper we provide an (O) over tilde (nd + d(3)) time randomized algorithm for solving linear programs with d variables and n constraints with high probability. To obtain this result we provide a robust, primaldual (O) over tilde(root d)-iteration interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.
Given the initiatives to improve resource allocation decisions for HIV prevention activities, a linear programming model was designed specifically for use by state and local decision-makers. A pilot study using inform...
详细信息
作者：
Freund, RMMIT
ALFRED P SLOAN SCH MANAGEMENTCAMBRIDGEMA 02142
This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any ''big M'' initialization ...
详细信息
This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any ''big M'' initialization assumption. The complexity of the algorithm is sensitive to and is dependent on the quality of the starting point, as assessed by suitable measures of the extent of infeasibility and the extent of nonoptimality of the starting point. Two new measures of the extent of infeasibility and of nonoptimality of a starting point are developed. We then present an algorithm for solving LP whose complexity depends explicitly and only on how close the starting point is to the set of LP feasible and optimal solutions (using these and other standard measures), and also on n (the number of inequalities). The complexity results using these measures of infeasibility and nonoptimality appear to be consistent with the observed practical sensitivity of interior-point algorithms to certain types of starting points. The starting point can be any pair of primal and dual vectors that may or may not be primal and/or dual feasible, and that satisfies a simple condition that typically arises in practice or is easy to coerce.
暂无评论