14 papers · ranked by Valyu relevance
Daniel Gibor
In this paper, we present a randomized polynomial-time simplex algorithm with higher probability and tighter bounds for linear programming by applying improved quasi-convex properties, a logarithmic rounding on a given polytope and its logarithmic perturbation. We base our work on the first randomized polynomial-time…
Demétrios Araújo Magalhães Coutinho, Samuel Xavier‐de‐Souza, Daniel Aloise
'Daniel Aloise'] The Simplex tableau has been broadly used and investigated in the industry and academia. With the advent of the big data era, ever larger problems are posed to be solved in ever larger machines whose architecture type did not exist in the conception of this algorithm. In this paper, we present a…
Henry W. Robbins, Samuel C Gutekunst, Frans Schalekamp, David B. Shmoys + 1 more
'David B. Shmoys' 'David P. Williamson'] The Simplex algorithm for solving linear programs—one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century—is an important topic in many algorithms courses. While the algorithm relies on intuitive geometric ideas, the…
Alexander Black, Jesús A. De Loera, Sean Kafer, Laura Sanità
We present new pivot rules for the Simplex method for LPs over 0/1 polytopes. We show that the number of non-degenerate steps taken using these rules is strongly polynomial and even linear in the dimension or in the number of variables. Our bounds on the number of steps are asymptotically optimal on several well-known…
Kirill Kukharenko, Laura Sanità
The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edgedirection of the underlying polyhedron.
Seid Miad Zandavi, Yuk Ying Chung, Ali Anaissi
The scheduling of multi-user remote laboratories is modeled as a multimodal function for the proposed optimization algorithm. The hybrid optimization algorithm, hybridization of the Nelder-Mead Simplex algorithm and Non-dominated Sorting Genetic Algorithm (NSGA), is proposed to optimize the timetable problem for the…
Eleon Bach, Sophie Huiberts
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Spielman and Teng (STOC '01) introduced the smoothed analysis framework of algorithm analysis and…
Birgit Rudloff, Fırdevs Ulus, Robert J. Vanderbei
In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm [15]. Different from it, the proposed algorithm works in the parameter space and does not aim to find…
Arash Raeisi Gahrouei, Mehdi Ghatee
Graphics Processing Units (GPUs) with high computational capabilities used as modern parallel platforms to deal with complex computational problems. We use this platform to solve large-scale linear programing problems by revised simplex algorithm. To implement this algorithm, we propose some new memory management…
Alberto Del Pia, Carla Michini
The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces 'short' simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in [0, k] n and defined via m linear inequalities. Our first contribution is a simplex algorithm that…
Friedrich Eisenbrand, Santosh Vempala
We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs max{c T x: x ∈ R n, Ax 6 b}, whose constraint matrix A satisfies a geometric property introduced by Brunsch and R¨oglin: The sine of the angle of a row of A to a hyperplane spanned by n −…
Priyam Das, Deborshee Sen, Debsurya De, Jue Hou + 4 more
'Nicole Kim' 'Zongqi Xia' 'Tianxi Cai'] Abstract Black-box optimization of objective function of parameters belonging to simplex arises in many inference and predictive models. [1] introduced Greedy Co-ordinate Descent of Varying Step-sizes on Simplex (GCDVSS) which efficiently optimizes any black-box function whose…
I. D. Coope, Rachael Tappenden
Simplex gradients are an essential feature of many derivative free optimization algorithms, and can be employed, for example, as part of the process of defining a direction of search, or as part of a termination criterion. The calculation of a general simplex gradient in Rn can be computationally expensive, and often…
Dominic Desjardins Côté
The main goal is to construct a combinatorial dynamical system in the sense of Forman from finite vector field data. We use a linear minimization problem with binary variables and linear equality constraints. The solution of the minimization problem induces an admissible matching for the combinatorial dynamical system.…