We propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the … Read more
With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most … Read more
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more
We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to arrive at a set of tools that does well across all of these scenarios. We formulate the problem as a mixed-integer program in which expected value of the … Read more
Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more
Inspired by an algorithm due to Minieka, we develop a simple and yet very efficient exact algorithm for the problem of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility it is assigned to. After a lower bounding phase, the algorithm iteratively sets … Read more
It is well known that the eigenvalues of a real symmetric matrix are not everywhere differentiable. A classical result of Ky Fan states that each eigenvalue of a symmetric matrix is the difference of two convex functions. This directly implies that the eigenvalues of a symmetric matrix are semismooth everywhere. Based on a very recent … Read more
We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps and symmetry aspects which make them harder to both exact methods and heuristics than the test problems currently in use for the evaluation and comparison of existing and newly developed algorithms. Our … Read more
This article considers continuous trajectories of the vector fields induced by two different primal-dual potential-reduction algorithms for solving linear programming problems. For both algorithms, it is shown that the associated continuous trajectories include the central path and the duality gap converges to zero along all these trajectories. For the algorithm of Kojima, Mizuno, and Yoshise, … 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