Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In … Read more
The paper proposes a polynomial algorithm for solving systems of linear inequalities. The algorithm uses a polynomial relaxation-type procedure which either finds a solution for Ax = b, 0
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the dual simplex method with the most negative pivoting rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (2010) for the primal simplex method. We apply the result to the … Read more
We give an upper bound for the number of different basic feasible solutions generated by Dantzig’s simplex method (the simplex method with the most negative pivoting rule) for LP with bounded variables by extending the result of Kitahara and Mizuno (2010). We refine the analysis by them and improve an upper bound for a standard … Read more
Continuous linear programs have attracted considerable interest due to their potential for modelling manufacturing, scheduling and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (non-separated) problem instances. In this paper we propose a more generic approximation scheme for … Read more
Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization … Read more
The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more
The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, … Read more
Up to orthogonal transformation, a solid closed convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is the epigraph of a nonnegative sublinear function $f:\mathbb{R}^n\to \mathbb{R}$. This work explores the link between the geometric properties of $K$ and the analytic properties of $f$. CitationJOURNAL OF CONVEX ANALYSIS, 2011, in press. ArticleDownload View PDF
This is the second part of a work devoted to the theory of epigraphical cones and their applications. A convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is an epigraphical cone if it can be represented as epigraph of a nonnegative sublinear function $f: \mathbb{R}^n\to \mathbb{R}$. We explore the link between the geometric properties of … Read more