Determining the “active manifold” for a minimization problem is a large step towards solving the problem. Many researchers have studied under what conditions certain algorithms identify active manifolds in a finite number of iterations. In this work we outline a unifying framework encompassing many earlier results on identification via the Subgradient (Gradient) Projection Method, Newton-like Methods, and the Proximal Point Algorithm. This framework, prox-regular partial smoothness, has the advantage of not requiring convexity for its conclusions, and therefore extends many of these earlier results.
Given an instance of TSP together with an optimal solution, we consider the scenario in which this instance is modified locally, where a local modification consists in the alteration of the weight of a single edge. More generally, for a problem U, let LM-U (local-modification-U) denote the same problem as U, but in LM-U, we are also given an optimal solution to an instance from which the input instance can be derived by a local modification. The question is how to exploit this additional knowledge, i.e., how to devise better algorithms for LM-U than for U. Note that this need not be possible in all cases: The general problem of LM-TSP is as hard as TSP itself, i.e., unless P = NP , there is no polynomial-time p(n)-approximation algorithm for LM-TSP for any polynomial p. Moreover, LM-TSP where inputs must satisfy the -triangle inequality (LM- -TSP ) remains NP-hard for all > 12 . However, for LM- -TSP (i.e., metric LM-TSP), we will present an efficient 1.4-approximation algorithm. In other words, the additional information enables us to do better than if we simply used Christofides’ algorithm for the modified input. Similarly, for all 1 < < 3.34899, we achieve a better approximation ratio for LM- -TSP than for -TSP. For 12 ≤ < 1, we show how to obtain an approximation ratio arbitrarily close to 1, for sufficiently large input graphs.
In this paper we study the behavior of Convex Quadratic Optimization problems when variation occurs simultaneously in the right-hand side vector of the constraints and in the coefficient vector of the linear term in the objective function. It is proven that the optimal value function is piecewise-quadratic. The concepts of transition point and invariancy interval are generalized to the case of simultaneous perturbation. Criteria for convexity, concavity or linearity of the optimal value function on invariancy intervals are derived. Furthermore, differentiability of the optimal value function is studied, and linear optimization problems are given to calculate the left and right derivatives. An algorithm, that is capable to compute the transition points and optimal partitions on all invariancy intervals, is outlined. We specialize the method to Linear Optimization problems and provide a practical example of simultaneous perturbation parametric quadratic optimization problem from electrical engineering.
Discount auction is a procurement mechanism for buying M indivisible heterogeneous items. The bidders are suppliers and a bid consists of two entities: individual cost for each of the items and a non-decreasing discount function defined over the number of items. The winner determination problem faced by the buyer is to determine the winning suppliers and their corresponding winning items that minimizes the total procurement cost, subject to the supply, demand, and discount constraints. We show that this problem is N P-hard upon reduction from the set covering problem. An integer programming formulation is presented and valid inequalities are derived, which serve as cuts to the linear relaxation. A collection of branch-and-cut algorithms are developed with different cut addition techniques and branching strategies. The performance of the proposed algorithms for different problem types are studied with extensive computational experiments.
We consider a special linear assignment problem where some tasks are grouped, and in each group the tasks are ‘disjunctive’ (in the sense that at most one of them could be performed). We show this problem NP-hard. Then we present and compare two alternative decomposition based algorithms on randomly generated instances.