This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in … Read more
We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where … Read more
We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. Citation Preliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers. Article Download View Semidefinite programming and integer … Read more
This paper presents smoothing heuristics for an NP-hard combinatorial problem based on Lagrangian relaxation. We formulate the Lagrangian dual for this nonconvex quadratic problem and propose eigenvalue nonsmooth unconstrained optimization to solve the dual problem with bundle or subgradient methods. Derived heuristics are considered to obtain good primal solutions through pathfollowing methods using a projected … Read more
In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … 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
GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this chapter, … Read more
Interior point methods, the traditional methods for the $SDP$, are fairly limited in the sizes of problems they can handle. This paper deals with an $LP$ approach to overcome some of these shortcomings. We begin with a semi-infinite linear programming formulation of the $SDP$ and discuss the issue of its discretization in some detail. We … Read more
We introduce an anti-matroid as a family $\cal F$ of subsets of a ground set $E$ for which there exists an assignment of weights to the elements of $E$ such that the greedy algorithm to compute a maximal set (with respect to inclusion) in $\cal F$ of minimum weight finds, instead, the unique maximal set … Read more
Lagrangian relaxation is a tool to find upper bounds on a given (arbitrary) maximization problem. Sometimes, the bound is exact and an optimal solution is found. Our aim in this paper is to review this technique, the theory behind it, its numerical aspects, its relation with other techniques such as column generation. Citation in: Computational … Read more