On a Generalization of the Master Cyclic Group Polyhedron

We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for the MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory (1969) and for the Master Knapsack Polyhedron … Read more

A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs

This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it … Read more

Efficient Formulations for the Multi-Floor Facility Layout Problem with Elevators

The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more

Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more

A conic duality Frank–Wolfe type theorem via exact penalization in quadratic optimization

The famous Frank–Wolfe theorem ensures attainability of the optimal value for quadratic objective functions over a (possibly unbounded) polyhedron if the feasible values are bounded. This theorem does not hold in general for conic programs where linear constraints are replaced by more general convex constraints like positive-semidefiniteness or copositivity conditions, despite the fact that the … Read more

Lattice based extended formulations for integer linear equality systems

We study different extended formulations for the set $X =\{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good … Read more

Separation of convex polyhedral sets with uncertain data

This paper is a contribution to the interval analysis and separability of convex sets. Separation is a familiar principle and is often used not only in optimization theory, but in many economic applications as well. In real problems input data are usually not known exactly. For the purpose of this paper we assume that data … Read more

Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat … Read more

Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization

Recently we investigated in “The operator $\Psi$ for the Chromatic Number of a Graph” hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. In particular, we introduced two hierarchies of lower bounds, the `$\psi$’-hierarchy converging to the fractional chromatic number, and the `$\Psi$’-hierarchy converging to the chromatic number of a graph. … Read more

The operator $\Psi$ for the Chromatic Number of a Graph

We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi\left( {\ol G} \right)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\alpha (\ol G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if … Read more