Some heuristic methods for solving p-median problems with a coverage constraint

The aim of this paper is to solve p-median problems with an additional coverage constraint. These problems arise in location applications, when the trade-off between distance and coverage is being calculated. Three kinds of heuristic algorithms are developed. First, local search procedures are designed both for constructing and improving feasible solutions. Second, a multistart GRASP heuristic is developed, based on the previous local search methods. Third, by employing Lagrangean relaxation methods, a very efficient Lagrangean heuristic algorithm is designed, which extends the well known algorithm of Handler and Zang, for constrained shortest path problems, to constrained p-median problems. Finally, a comparison of the computational efficiency of the developed methods is made between a variety of problems of different sizes.     

Parametric approaches to fractional programs

The fractional program P is defined by maxf(x)/g(x) subject tox∈X. A class of methods for solving P is based on the auxiliary problem Q(λ) with a parameter λ: maxf(x)?λg(x) subject tox∈X. Starting with two classical methods in this class, the Newton method and the binary search method, a number of variations are introduced and compared. Among the proposed methods. the modified binary search method is theoretically interesting because of its superlinear convergence and the capability to provide an explicit interval containing the optimum parameter value \(\bar \lambda \) . Computational behavior is tested by solving fractional knapsack problems and quadratic fractional programs. The interpolated binary search method seems to be most efficient, while other methods also behave surprisingly well.     

Swap-vertex based neighborhood for Steiner tree problems

Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swap-vertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swap-vertex moves. Additionally, in order to discriminate different swap-vertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swap-vertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.     

A preference-based approach to spanning trees and shortest paths problems****

Comparison of solutions in combinatorial problems is often based on an additive cost function inducing a complete order on solutions. We investigate here a generalization of the problem, where preferences take the form of a quasi-transitive binary relation defined on the solutions space. We first propose preference-based search algorithms for two classical combinatorial problems, namely the preferred spanning trees problem (a generalization of the minimum spanning tree problem) and the preferred paths problem (a generalization of the shortest path problem). Then, we introduce a very useful axiom for preference relations called independence. Using this axiom, we establish admissibility results concerning our preference-based search algorithms. Finally, we address the problem of dealing with non-independent preference relations and provide different possible solutions for different particular problems (e.g. lower approximation of the set of preferred solutions for multicriteria spanning trees problems, or relaxation of the independence axiom for interval-valued preferred path problems).     

Periodic solutions for second order differential inclusions with the scalar p-Laplacian

We study periodic problems driven by the scalar p-Laplacian with a multivalued right-hand side nonlinearity. We prove two existence theorems. In the first, we assume nonuniform nonresonance conditions between two successive eigenvalues of the negative p-Laplacian with periodic boundary conditions. In the second, we employ certain Landesman-Lazer type conditions. Our approach is based on degree theory.     

Is the new ECTS system better than the traditional one? An application to the ECTS pilot-project at the University Pablo de Olavide

At the meeting of the joint Bologna Declaration, EU representatives agreed on the establishment of a common European Higher Education Area by 2010. Since then, several universities have implemented pilot projects, although no formal research has been carried out to analyse their results. In this study, we analysed one of these pilot-projects with two objectives. First, we examined the performance of the new system as compared to that of the traditional system. We used a procedure based on a modified model of Data Envelopment Analysis that is able to distinguish students’ efficiency (managerial efficiency) from efficiency based on the educational programme used (programme efficiency). Then we analysed whether the different systems perform differently for different types of students.     

Positive solutions for nonlinear hemivariational inequalities

In this paper we study the existence of positive solutions for nonlinear problems driven by the p-Laplacian or more generally, by multivalued p-Laplacian-like operators. Both problems have a nonsmooth locally Lipschitz potential (hemivariational inequalities). Using variational methods based on the nonsmooth critical point theory, we prove two existence results with the p-Laplacian and multivalued p-Laplacian-like operators.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

On p-norm linear discrimination

We consider a p-norm linear discrimination model that generalizes the model of Bennett and Mangasarian (1992) and reduces to a linear programming problem with p-order cone constraints. The proposed approach for handling linear programming problems with p-order cone constraints is based on reformulation of p-order cone optimization problems as second order cone programming (SOCP) problems when p is rational. Since such reformulations typically lead to SOCP problems with large numbers of second order cones, an “economical” representation that minimizes the number of second order cones is proposed. A case study illustrating the developed model on several popular data sets is conducted.     

Remarks on the blowup criteria for Oldroyd models

We provide a new method to prove and improve the Chemin-Masmoudi criterion for viscoelastic systems of Oldroyd type in [J.Y. Chemin, N. Masmoudi, About lifespan of regular solutions of equations related to viscoelastic fluids, SIAM J. Math. Anal. 33 (1) (2001) 84-112] in two space dimensions. Our method is much easier than the one based on the well-known losing a priori estimate and is expected to be easily adopted to other problems involving the losing a priori estimate.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

Duality in ε-variational inequality problems

In this paper a general analysis of duality for an extended ε-variational inequality problem based on the notions of ε-convexity and ε-conjugacy is performed. Optimal solutions of both the primal and dual problems are also related to the saddle point of an associated Lagrangian. Gap functions for these problems are proposed. An existence theorem for the extended ε-variational inequality is also established by means of the KKM lemma.     

Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date

We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed.     

An empirical study of a new metaheuristic for the traveling salesman problem

We present a deceptively simple, yet empirically powerful metaheuristic, called jump search, for solving traveling salesman problems that has been found to be more effective than tabu search on both random and benchmark test problems from the literature. While the underlying philosophy of jump search — applying local search from different starting points — has been discussed in the literature previously (using random starting points), the use of construction-based heuristic solutions has heretofore not been considered. Extensive empirical analysis shows the method to be surprisingly effective vis a vis a randomized strategy and in comparison with tabu search. The approach is quite robust and suggests that a systematic search among neighborhoods of good, not random, solutions provides distinct advantages. This suggests that further research be focused on better construction heuristics and hybrid schemes that incorporate jump search in, for example, tabu search.     

Maximum principles for a fourth order equation from thin plate theory

This paper focuses on a nonlinear equation from thin plate theory of the form Δ(D(x)Δw)−(1−ν)[D,w]+c(x)f(w)=0. We obtain maximum principles for certain functions defined on the solution of this equation using P-functions or auxiliary functions of the types used by Payne [L.E. Payne, Some remarks on maximum principles, J. Anal. Math. 30 (1976) 421-433] and Schaefer [P.W. Schaefer, Solution, gradient, and laplacian bounds in some nonlinear fourth order elliptic equations, SIAM J. Math. Anal. 18 (1987) 430-434].     

Underestimating the cost of a soft constraint is dangerous: revisiting the edit-distance based soft regular constraint

Many real-life problems are over-constrained, so that no solution satisfying all their constraints exists. Soft constraints, with costs denoting how much the constraints are violated, are used to solve these problems. We use the edit-distance based SoftRegular constraint as an example to show that a propagation algorithm that sometimes underestimates the cost may guide the search to incorrect (non-optimal) solutions to an over-constrained problem. To compute correctly the cost for the edit-distance based SoftRegular constraint, we present a quadratic-time propagation algorithm based on dynamic programming and a proof of its correctness. We also give an improved propagation algorithm using an idea of computing the edit distance between two strings, which may also be applied to other constraints with propagators based on dynamic programming. The asymptotic time complexity of our improved propagator is always at least as good as the one of our quadratic-time propagator, but significantly better when the edit distance is small. Our propagators achieve domain consistency on the problem variables and bounds consistency on the cost variable. Our method can also be adapted for the violation measure of the edit-distance based Regular constraint for constraint-based local search.     

A discrete dynamic convexized method for the max-cut problem

The max-cut problem is a classical NP-hard problem in graph theory. In this paper, we adopt a local search method, called MCFM, which is a simple modification of the Fiduccia-Mattheyses heuristic method in Fiduccia and Mattheyses (Proc. ACM/IEEE DAC, pp. 175?C181, 1982) for the circuit partitioning problem in very large scale integration of circuits and systems. The method uses much less computational cost than general local search methods. Then, an auxiliary function is presented which has the same global maximizers as the max-cut problem. We show that maximization of the function using MCFM can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. An algorithm is proposed for the max-cut problem, by maximizing the auxiliary function using MCFM from random initial solutions. Computational experiments were conducted on three sets of standard test instances from the literature. Experimental results show that the proposed algorithm is effective for the three sets of standard test instances.     

Gradient estimates via linear and nonlinear potentials

We prove new potential and nonlinear potential pointwise gradient estimates for solutions to measure data problems, involving possibly degenerate quasilinear operators whose prototype is given by −Δpu=μ. In particular, no matter the nonlinearity of the equations considered, we show that in the case p?2 a pointwise gradient estimate is possible using standard, linear Riesz potentials. The proof is based on the identification of a natural quantity that on one hand respects the natural scaling of the problem, and on the other allows to encode the weaker coercivity properties of the operators considered, in the case p?2. In the case p>2 we prove a new gradient estimate employing nonlinear potentials of Wolff type.     

Polynomial time approximation schemes and parameterized complexity

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.     

Asymptotics for statistical functionals of long-memory sequences

We present two general results that can be used to obtain asymptotic properties for statistical functionals based on linear long-memory sequences. As examples for the first one we consider L- and V-statistics, in particular tail-dependent L-statistics as well as V-statistics with unbounded kernels. As an example for the second result we consider degenerate V-statistics. To prove these results we also establish a weak convergence result for empirical processes of linear long-memory sequences, which improves earlier ones.