In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs … Read more
We study the mesh topology design problem in overlay virtual private networks. Given a set of customer nodes and associated traffic matrix, tunnels that are connecting node pairs through a public service provider network subject to degree constraints are determined so as to minimize total multihopped traffic. Valid inequalities strengthening the LP relaxation and a … Read more
In facility layout problems, a major concern is the optimal design or remodeling of the facilities of an organization. The decision-maker’s objective is to arrange the facility in an optimal way, so that the interaction among functions (i.e. machines, inventories, persons) and places (i.e. offices, work locations, depots) is efficient. A simple pure-binary LP model … Read more
This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more
We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in $2^n-1$ variables. The optimal values of both problems are identical. From every optimal solution of the former one easily find an optimal solution of the latter and conversely, from every solution of the latter one may … Read more
We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more
This paper presents the results of the application of a non-differentiable optimization method in connection with the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an extension of the Vehicle Routing Problem. In the VRPTW the service at each customer must start within an associated time window. The Shortest Path decomposition of the … Read more
The $p$-Center problem consists in locating $p$ facilities among a set of $M$ possible locations and assigning $N$ clients to them in order to minimize the maximum distance between a client and the facility to which he is allocated. We present a new integer linear programming formulation for this Min-Max problem with a polynomial number … Read more
The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more
The classical non-linear mixed integer formulation of the transmission network expansion problem cannot guarantee finding the optimal solution due to its non-convex nature. We propose an alternative mixed integer linear disjunctive formulation, which has better conditioning properties than the standard disjunctive model. The mixed integer program is solved by a commercial Branch and Bound code, … Read more