The role of rationality in integer-programming relaxations

For a finite set $X \subset \Z^d$ that can be represented as $X = Q \cap \Z^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $\rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $\rc_\Q(X)$ restricts … Read more

Distributed Projections onto a Simplex

Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, all but one of these algorithms are serial. We address this gap by developing a method that preprocesses the input vector by decomposing and distributing it … Read more

A Modified Simplex Partition Algorithm to Test Copositivity

A real symmetric matrix $A$ is copositive if $x^\top Ax\geq 0$ for all $x\geq 0$. As $A$ is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015) … Read more

Fast Projection onto the Simplex and the l1 Ball

A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or a l1-norm ball. The algorithm is demonstrated to be faster than existing methods. In addition, a wrong statement in a paper by Duchi et al. is corrected and an adversary sequence for Michelot’s algorithm … Read more

Computational and Economic Limitations of Dispatch Operations in the Next-Generation Power Grid

We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more

The Simplex Method – Computational Checks for the Simplex Calculation

The purpose of this paper is to derive computational checks for the simplex method of Linear Programming which can be applied at any iteration. The paper begins with a quick review of the simplex algorithm. It then goes through a theoretical development of the simplex method and its dual all the time focusing on the … Read more