Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or 1/2, such cuts are known as {0, 1/2}-cuts. It has been proven by Caprara and Fischetti (1996) that separation of {0, 1/2}-cuts is NP-hard. In this paper, we study … Read more
The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite … Read more
In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more
Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at … Read more
Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as … Read more
It is shown that, contrary to a claim of [D. E. Finkel, and C. T. Kelley, Additive scaling and the DIRECT algorithm, J. Glob. Optim. 36 (2006) 597-608], it is possible to divide the smallest hypercube which contains the low function value by considering hyperrectangles whose points are located on the diagonal of the center … Read more
We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth and thus finding its global solution is in principal a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes … Read more
This paper presents an outcome-space outer approximation algorithm for globally solving the linear multiplicative programming problem. We prove that the proposed algorithm is finite. To illustrate the new algorithm, we apply it to solve some sample problems. Citation 10, Hanoi University of Technology, 07/2007 Article Download View Outcome-Space Outer Approximation Algorithm for Linear Multiplicative Programming
We introduce a new measure of complexity of integer hulls of rational polyhedra called the small Chvatal rank (SCR). The SCR of an integer matrix A is the number of rounds of a Hilbert basis procedure needed to generate all normals of a sufficient set of inequalities to cut out the integer hulls of all … Read more
Robust optimization programs are hard to solve even when the constraints are convex. In previous contributions, it has been shown that approximately robust solutions (i.e. solutions feasible for all constraints but a small fraction of them) to convex programs can be obtained at low computational cost through constraints randomization. In this paper, we establish new … Read more