In this paper, we show that the Chatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver 1980 and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex sets (Dadush et. al 2010). In … Read more
The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more
The lift-and-project closure is the relaxation obtained by computing all lift-and-project cuts from the initial formulation of a mixed integer linear program or equivalently by computing all mixed integer Gomory cuts read from all tableau’s corresponding to feasible and infeasible bases. In this paper, we present an algorithm for approximating the value of the lift-and-project … Read more
We propose a partial replication strategy to construct risk-averse enhanced index funds. Our model takes into account the parameter estimation risk by defining the asset returns and the return covariance terms as random variables. The variance of the index fund return is forced to be below a low-risk threshold with a large probability, thereby limiting … Read more
In this paper we consider a relaxation of the corner polyhedron introduced by Andersen et al., which we denote by RCP. We study the relative strength of the split and triangle cuts of RCP’s. Basu et al. showed examples where the split closure can be arbitrarily worse than the triangle closure under a `worst-cost’ type … Read more
In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation … Read more
Although well studied, important questions on the rank of the Chvátal-Gomory operator when restricting to polytopes contained in the n-dimensional 0/1 cube have not been answered yet. In particular, the question on the maximal rank of the Chvátal-Gomory procedure for this class of polytopes is still open. So far, the best-known upper bound is O(n^2 … Read more
The cutting plane tree (CPT) algorithm provides a finite disjunctive programming procedure to obtain the solution of general mixed-integer linear programs (MILP) with bounded integer variables. In this paper, we present our computational experience with variants of the CPT algorithm. Because the CPT algorithm is based on discovering multi-term disjunctions, this paper is the first … Read more
This article extends a previous work focused on a mixed integer programming (MIP) based heuristic approach, aimed at solving non-standard three-dimensional problems with additional conditions. The paper that follows considers a mixed integer non-linear (MINLP) reformulation of the previous model, to improve the former heuristic, based on linear relaxation. The approach described herewith is addressed, … Read more
Geometric random walks have been proposed and analyzed for solving optimization problems. In this paper we report our computational experience with generating feasible integer solutions of mixed-integer linear programs using geometric random walks, and a random ray approach. A feasibility pump is used to heuristically round the generated points. Computational results on MIPLIB2003 and COR@L … Read more