It is well known that any feasible arc-flow solution to a network problem defined on a graph $G = (N, A)$, where $N$ is the set of nodes whereas $A$ is the set of arcs, can be expressed using at most $|A| + |N|$ paths and cycles having nonzero flow, out of these, at most … Read more
We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally “smoothed,” thereby allowing most first-order … Read more
This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more
It is shown that a recently proposed method by Chubanov for solving linear homogeneous systems with positive variables can be improved, both theoretically and computationally. CitationTU Delft, September 2014ArticleDownload View PDF
Ordering problems are a special class of combinatorial optimization problems, where weights are assigned to each ordering of n objects and the aim is to find an ordering of maximum weight. Even for the simplest case of a linear cost function, ordering problems are known to be NP-hard, i.e. it is extremely unlikely that there … Read more
The main contributions of this thesis are the comparison of existing and the design of new exact approaches based on linear, quadratic and semidefinite relaxations for row layout problems and several applications in logistic. In particular we demonstrate that our suggested semidefinite approach is the strongest exact method to date for most row layout problems. … Read more
The $k$-Parallel Row Ordering Problem (kPROP) is an extension of the Single-Row Facility Layout Problem (SRFLP) that considers arrangements of the departments along more than one row. We propose an exact algorithm for the kPROP that extends the semidefinite programming approach for the SRFLP by modelling inter-row distances as products of ordering variables. For k=2 … Read more
We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to … Read more
In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded by the dimension. Combining Orlin’s primal-based modification and Mizuno’s use of the simplex method, we introduce a modification of Tardos’ algorithm considering only the primal problem and using simplex method … Read more
A new class of matrix support functionals is presented which establish a connection between optimal value functions for quadratic optimization problems, the matrix-fractional function, the pseudo matrix-fractional function, and the nuclear norm. The support function is based on the graph of the product of a matrix with its transpose. Closed form expressions for the support … Read more