اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA double-pivot degenerate-tolerable simplex algorithm for linear programming
139
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A double pivot algorithm that combines features of two recently published papers by these authors is proposed. The proposed algorithm is implemented in MATLAB. The MATLAB code is tested, along with a MATLAB implementation of Dantzigs algorithm, for several test sets, including a set of cycling LP problems, Klee-Mintys problems, randomly generated linear programming (LP) problems, and Netlib benchmark problems. The test result shows that the proposed algorithm is (a) degenerate-tolerance as we expected, and (b) more efficient than Dantzigs algorithm for large size randomly generated LP problems but less efficient for Netlib benchmark problems and small size randomly generated problems in terms of CPU time.
قيم البحث
اقرأ أيضاً
The existence of strongly polynomial-time algorithm for linear programming is a cross-century international mathematical problem, whose breakthrough will solve a major theoretical crisis for the development of artificial intelligence. In order to mak
e it happen, this paper proposes three solving techniques based on the cone-cutting theory: 1. The principle of Highest Selection; 2. The algorithm of column elimination, which is more convenient and effective than the Ye-column elimination theorem; 3. A step-down algorithm for a feasible point horizontally shifts to the center and then falls down to the bottom of the feasible region $D$. There will be a nice work combining three techniques, the tri-skill is variant Simplex algorithm to be expected to help readers building the strong polynomial algorithms. Besides, a variable weight optimization method is proposed in the paper, which opens a new window to bring the linear programming into uncomplicated calculation.
We introduce a class of specially structured linear programming (LP) problems, which has favorable modeling capability for important application problems in different areas such as optimal transport, discrete tomography and economics. To solve these
generally large-scale LP problems efficiently, we design an implementable inexact entropic proximal point algorithm (iEPPA) combined with an easy-to-implement dual block coordinate descent method as a subsolver. Unlike existing entropy-type proximal point algorithms, our iEPPA employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence. Moreover, when solving the capacity constrained multi-marginal optimal transport (CMOT) problem (a special case of our LP problem), our iEPPA is able to bypass the underlying numerical instability issues that often appear in the popular entropic regularization approach, since our algorithm does not require the proximal parameter to be very small in order to obtain an accurate approximate solution. Numerous numerical experiments show that our iEPPA is highly efficient and robust for solving large-scale CMOT problems, in comparison to the (stabilized) Dykstras algorithm and the commercial solver Gurobi. Moreover, the experiments on discrete tomography also highlight the potential modeling power of our model.
This paper discusses the odds problem, proposed by Bruss in 2000, and its variants. A recurrence relation called a dynamic programming (DP) equation is used to find an optimal stopping policy of the odds problem and its variants. In 2013, Buchbinder,
Jain, and Singh proposed a linear programming (LP) formulation for finding an optimal stopping policy of the classical secretary problem, which is a special case of the odds problem. The proposed linear programming problem, which maximizes the probability of a win, differs from the DP equations known for long time periods. This paper shows that an ordinary DP equation is a modification of the dual problem of linear programming including the LP formulation proposed by Buchbinder, Jain, and Singh.
Column generation is often used to solve multi-commodity flow problems. A program for column generation always includes a module that solves a linear equation. In this paper, we address three major issues in solving linear problem during column gener
ation procedure which are (1) how to employ the sparse property of the coefficient matrix; (2) how to reduce the size of the coefficient matrix; and (3) how to reuse the solution to a similar equation. To this end, we first analyze the sparse property of coefficient matrix of linear equations and find that the matrices occurring in iteration are very sparse. Then, we present an algorithm locSolver (for localized system solver) for linear equations with sparse coefficient matrices and right-hand-sides. This algorithm can reduce the number of variables. After that, we present the algorithm incSolver (for incremental system solver) which utilizes similarity in the iterations of the program for a linear equation system. All three techniques can be used in column generation of multi-commodity problems. Preliminary numerical experiments show that the incSolver is significantly faster than the existing algorithms. For example, random test cases show that incSolver is at least 37 times and up to 341 times faster than popular solver LAPACK.
In this paper, we develop a new algorithm combining the idea of ``boosting with the first-order algorithm to approximately solve a class of (Integer) Linear programs(LPs) arisen in general resource allocation problems. Not only can this algorithm sol
ve LPs directly, but also can be applied to accelerate the Column Generation method. As a direct solver, our algorithm achieves a provable $O(sqrt{n/K})$ optimality gap, where $n$ is the number of variables and $K$ is the number of data duplication bearing the same intuition as the boosting algorithm. We use numerical experiments to demonstrate the effectiveness of our algorithm and several variants.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
