Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

Duality for Anticonvex Programs

Calling anticonvex a program which is either a maximization of a convex function on a convex set or a minimization of a convex function on the set of points outside a convex subset, we introduce several dual problems related to each of these problems. We give conditions ensuring there is no duality gap. We show how solutions to the dual problems can serve to locate solutions of the primal problem.     

Sign reversion approach to concave minimization problems

We consider a problem of minimization of a concave function subject to affine constraints. By using sign reversion techniques we show that the initial problem can be transformed into a family of concave maximization problems. This property enables us to suggest certain algorithms based on the parametric dual optimization problem.     

Maximizing breaks and bounding solutions to the mirrored traveling tournament problem

We investigate the relation between two aspects of round robin tournament scheduling problems: breaks and distances. The distance minimization problem and the breaks maximization problem are equivalent when the distance between every pair of teams is equal to 1. We show how to construct schedules with a maximum number of breaks for some tournament types. The connection between breaks maximization and distance minimization is used to derive lower bounds to the mirrored traveling tournament problem and to prove the optimality of solutions found by a heuristic for the latter.     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

Level‐based heuristics and hill climbing for the antibandwidth maximization problem

The antibandwidth maximization problem aims to maximize the minimum distance of entries of a sparse symmetric matrix from the diagonal and as such may be regarded as the dual of the well‐known bandwidth minimization problem. In this paper, we consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level‐based heuristic, we obtain an initial ordering that we refine using a hill‐climbing algorithm. This approach performs well on matrices coming from a range of practical problems with an underlying mesh. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being significantly faster and applicable to much larger problems. Copyright © 2012 John Wiley & Sons, Ltd.     

An improved enumerative algorithm for solving quadratic zero-one programming

An improved algorithm is proposed for the minimization of a quadratic function in zero-one variables under quadratic constraints which is based on the idea of additive penalties proposed by P. Hansen. At first, the quadratic function in which all the coefficients except the constant term are nonnegative is obtained by the introduction of the negative variables, and the constant term is a tighter bound of the function. Starting from the tighter bound, some properties are obtained and some efficient tests are established. To obtain a much tighter bound, a simple heuristic method is suggested instead of solving a linear programming problem. Furthermore, the flexibility dealing with some tests is discussed and it is also helpful to the algorithm.     

Analytic solutions for the approximated 1-D Monge–Kantorovich mass transfer problems

This paper mainly investigates the approximation of a global maximizer of the 1-D Monge–Kantorovich mass transfer problem through the approach of nonlinear differential equations with Dirichlet boundary. Using an approximation mechanism, the primal maximization problem can be transformed into a sequence of minimization problems. By applying the canonical duality theory, one is able to derive a sequence of analytic solutions for the minimization problems. In the final analysis, the convergence of the sequence to a global maximizer of the primal Monge–Kantorovich problem will be demonstrated.     

非光滑向量极值问题的真有效解与最优性条件

讨论了赋范线性空间中非光滑向量极值问题的Hatley,Borwein,Benson真有效解之间的关系,指出了它们共同的标量极值问题的等价刻画,建立了问题（VMP）的广义KT-真有效解的充分条件,并给出了向量极小值问题在锥局部凸、拟凸、伪凸等条件下的最优性条件。     

Adjoint Coexhausters in Nonsmooth Analysis and Extremality Conditions

In the classical (“smooth”) mathematical analysis, a differentiable function is studied by means of the derivative (gradient in the multidimensional space). In the case of nondifferentiable functions, the tools of nonsmooth analysis are to be employed. In convex analysis and minimax theory, the corresponding classes of functions are investigated by means of the subdifferential (it is a convex set in the dual space), quasidifferentiable functions are treated via the notion of quasidifferential (which is a pair of sets). To study an arbitrary directionally differentiable function, the notions of upper and lower exhausters (each of them being a family of convex sets) are used. It turns out that conditions for a minimum are described by an upper exhauster, while conditions for a maximum are stated in terms of a lower exhauster. This is why an upper exhauster is called a proper one for the minimization problem (and an adjoint exhauster for the maximization problem) while a lower exhauster will be referred to as a proper one for the maximization problem (and an adjoint exhauster for the minimization problem). The directional derivatives (and hence, exhausters) provide first-order approximations of the increment of the function under study. These approximations are positively homogeneous as functions of direction. They allow one to formulate optimality conditions, to find steepest ascent and descent directions, to construct numerical methods. However, if, for example, the maximizer of the function is to be found, but one has an upper exhauster (which is not proper for the maximization problem), it is required to use a lower exhauster. Instead, one can try to express conditions for a maximum in terms of upper exhauster (which is an adjoint one for the maximization problem). The first to get such conditions was Roshchina. New optimality conditions in terms of adjoint exhausters were recently obtained by Abbasov. The exhauster mappings are, in general, discontinuous in the Hausdorff metric, therefore, computational problems arise. To overcome these difficulties, the notions of upper and lower coexhausters are used. They provide first-order approximations of the increment of the function which are not positively homogeneous any more. These approximations also allow one to formulate optimality conditions, to find ascent and descent directions (but not the steepest ones), to construct numerical methods possessing good convergence properties. Conditions for a minimum are described in terms of an upper coexhauster (which is, therefore, called a proper coexhauster for the minimization problem) while conditions for a maximum are described in terms of a lower coexhauster (which is called a proper one for the maximization problem). In the present paper, we derive optimality conditions in terms of adjoint coexhausters.     

Single machine total tardiness maximization problems: complexity and algorithms

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem

In this paper, the problem of locating new facilities in a competitive environment is considered. The problem is formulated as the firm expected profit maximization and a set of nodes is selected in a graph representing the geographical zone. Profit depends on fixed and deterministic location costs and, since customers are independent decision-makers, on the expected market share. The problem is an instance of nonlinear integer programming, because the objective function is concave and submodular. Due to this complexity a branch & bound method is developed for solving small size problems (that is, when the number of nodes is less than 50), while a heuristic is necessary for larger problems. The branch & bound is called data-correcting method, while the approximate solutions are obtained using the heuristic-concentration method.     

Dual nonlinear programming problems in partially ordered Banach spaces

Summary The concept of duality plays an important role in mathematical programming and has been studied extensively in a finite dimensional Eucledian space, (see e.g. [13, 4, 6, 8]). More recently various dual problems with functionals as objective functions have been studied in infinite dimensional vector spaces [5, 7, 1, 10, 12].In this note we consider a nonlinear minimization problem in a partially ordered Banach space. It is assumed that the objective function of this problem is given by a (nonlinear) operator and that its feasible domain is defined by a system of (nonlinear) operator inequalities. In analogy to the finite dimensional case we associate with this minimization problem a dual maximization problem which is defined in the Cartesian product of certain Banach spaces. It is shown that under suitable assumptions the main results of the finite dimensional duality theory can be extended to this general case. This extension is based on optimality conditions obtained in [11].     

A lifting method for generalized semi-infinite programs based on lower level Wolfe duality

This paper introduces novel numerical solution strategies for generalized semi-infinite optimization problems (GSIP), a class of mathematical optimization problems which occur naturally in the context of design centering problems, robust optimization problems, and many fields of engineering science. GSIPs can be regarded as bilevel optimization problems, where a parametric lower-level maximization problem has to be solved in order to check feasibility of the upper level minimization problem. The current paper discusses several strategies to reformulate this class of problems into equivalent finite minimization problems by exploiting the concept of Wolfe duality for convex lower level problems. Here, the main contribution is the discussion of the non-degeneracy of the corresponding formulations under various assumptions. Finally, these non-degenerate reformulations of the original GSIP allow us to apply standard nonlinear optimization algorithms.     

Scatter Search—Wellsprings and Challenges

This article is concerned with two global optimization problems (P1) and (P2). Each of these problems is a fractional programming problem involving the maximization of a ratio of a convex function to a convex function, where at least one of the convex functions is a quadratic form. First, the article presents and validates a number of theoretical properties of these problems. Included among these properties is the result that, under a mild assumption, any globally optimal solution for problem (P1) must belong to the boundary of its feasible region. Also among these properties is a result that shows that problem (P2) can be reformulated as a convex maximization problem. Second, the article presents for the first time an algorithm for globally solving problem (P2). The algorithm is a branch and bound algorithm in which the main computational effort involves solving a sequence of convex programming problems. Convergence properties of the algorithm are presented, and computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem (P2), provided that the number of variables is not too large.     

An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint

A problem of the maximization of the ratio of a concave function to a convex function is considered, subject to an upper bound on a single convex constraint function; all these functions are assumed to be differentiable. An incremental algorithm is defined, which solves the problem parametrically for different values of the constraint function by the solution of a set of ordinary first order differential equations. If K is the number of variables in the problem and B(K) is an upper bound—dependent of K —of the time needed to evaluate any function value or any first or second order derivative, the complexity of the algorithm is of the order O[(B(K)K + K)a], where a is the number of integration steps applied in the solution of the differential equations. In particular, a cost-effectiveness resource allocation problem with separable functions is solved numerically in a time of the order O[Ka] if B(K) is independent of K; an example of such a problem is given with analytically solvable differential equations.     

Exponential approximation schemata for some network design problems

We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28