Applying mod-k-cuts for solving linear ordering problems

The linear ordering problem consists of finding an ordering of the nodes of the weighted complete digraph on n nodes such that the sum of the weights of the arcs compatible with the ordering is maximized. In this paper, we report about the usefulness of mod-k cuts in a branch-and-cut algorithm for solving linear ordering problems to optimality.      

A scaling algorithm for polynomial constraint satisfaction problems

Good scaling is an essential requirement for the good behavior of many numerical algorithms. In particular, for problems involving multivariate polynomials, a change of scale in one or more variable may have drastic effects on the robustness of subsequent calculations. This paper surveys scaling algorithms for systems of polynomials from the literature, and discusses some new ones, applicable to arbitrary polynomial constraint satisfaction problems.     

The SAT-UNSAT transition for random constraint satisfaction problems

We study threshold phenomena for a large class of random constraint satisfaction problems over finite domains. Our main contribution is a complete classification of the nature (sharp or coarse) of the SAT-UNSAT transition for random Boolean CSPs, which is based on easily decidable properties.     

Stabilized dynamic constraint aggregation for solving set partitioning problems

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solving linear programs. The first uses a projection to reduce the primal space whereas the second acts in the dual space. In this paper, we develop a new method, called stabilized dynamic constraint aggregation (SDCA), that combines DCA and DVS for solving set partitioning problems. It allows to fight degeneracy from both primal and dual perspectives simultaneously. To assess the effectiveness of SDCA, we report computational results obtained for highly degenerate multi-depot vehicle scheduling problem instances solved by column generation. These results indicate that SDCA can reduce the average computational time of the master problem by a factor of up to 7 with respect to the best of the two combined methods. Furthermore, they show that its performance is robust with regard to increasing levels of degeneracy in test problems.     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

Combining VNS with constraint programming for solving anytime optimization problems

This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcspValued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the “cost to pay” when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Li, Y.H., 1997. Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.     

Experience with a framework for developing heuristics for solving rich vehicle routing problems

According to Cordeau et al. (J Oper Res Soc 53(5):512–522, 2002) a good VRP heuristic should fulfill four criteria: accuracy, speed, simplicity, and flexibility. In this paper we report experience with a heuristic framework for solving rich vehicle routing problems (RVRP), which is based on rather simple heuristics. This heuristic framework has been implemented as flexible software framework. The user-friendly design enables flexible customization of problem-specific solvers. Our computational study on five RVRP reveals that the heuristic approach is rather robust with respect to parameterization and that the solvers which have been customized from the framework can compete with state-of-the-art special purpose developments.     

Optimality conditions for vector optimization problems with variable ordering structures

Our main concern in this article are concepts of nondominatedness w.r.t. a variable ordering structure introduced by Yu [P.L. Yu, Cone convexity, cone extreme points, and nondominated solutions in decision problems with multiobjectives, J. Optim. Theory Appl. 14 (1974), pp. 319–377]. Our studies are motivated by some recent applications e.g. in medical image registration. Restricting ourselves to the case when the values of a cone-valued map defining the ordering structure are Bishop–Phelps cones, we obtain for the first time scalarizing functionals for nondominated elements, Fermat rule, Lagrange multiplier rule and duality results for a single- or set-valued vector optimization problem with a variable ordering structure.     

Vector complementarity problems with a variable ordering relation

In this paper, we investigate vector complementarity problems with a variable ordering relation. We establish existence results of a solution of a vector complementarity problem under an inclusive type condition. We obtain equivalence results among a vector complementarity problem, a vector variational inequality problem and other related problems.     

Linear phase transition in random linear constraint satisfaction problems

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n and m = cn for a constant c. Namely, there exists a critical value c^* such that, when c < c^*, the problem is feasible or is asymptotically almost feasible, as n, but, when c>c^*, the distance to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let (n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n , the limit lim_n (n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).     

The property of being polynomial for Mal’tsev constraint satisfaction problems

A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal’tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 655–686, November–December, 2006.     

Secant variable projection method for solving nonnegative separable least squares problems

Numerical Algorithms - The variable projection method is a classical and efficient method for solving separable nonlinear least squares (SNLLS) problems. However, it is hard to handle the...     

Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently

Logic programming languages, such asProlog, allow a declarative specification of Constraint Satisfaction Problems (CSPs), freeing the user from specifying more or less complex control directives. However, the price to pay for such flexibility is a loss of efficiency, which makes Logic Programming inadequate to solve CSPs of even moderate size and complexity. To extend the range of applicability of logic programming, several improvements have been proposed. The use of heuristics is one such improvement. Although this usually forces the user to specify some form of control (thus abandoning the pure declarative nature of a logic program), these specifications can be made declarative by making use of some appropriate meta-predicates. Another extension to logic programming that improves its efficiency, is the active use of constraints, as done in the various formulations of constraint logic programming languages. In particular, the use of finite domains is quite adequate to implement look-ahead schemes to efficiently solve several types of CSPs. In this paper, we discuss the complementary nature of heuristics and look-ahead schemes and present a constraint logic programming framework that integrates both these techniques. Results obtained with a time-tabling problem executed on a prototype that implements such a framework are presented, and show that significant efficiency improvements can be achieved when compared with the separate use of the two techniques.     

A variable projection method for solving separable nonlinear least squares problems

Consider the separable nonlinear least squares problem of findinga εR ⁿ and α εR ^k which, for given data (y _i ,t _i ),i=1,2,...m, and functions ? _j (α,t),j=1,2,...,n(m>n), minimize the functional $$r(a,\alpha ) = \left\| {y - \Phi (\alpha )a} \right\|_2^2$$ where θ(α) _ij =? _j (α,t _i ). Golub and Pereyra have shown that this problem can be reduced to a nonlinear least squares problem involvingα only, and a linear least squares problem involvinga only. In this paper we propose a new method for determining the optimalα which computationally has proved more efficient than the Golub-Pereyra scheme.     

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.     

MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems

This paper discusses the use of probabilistic or randomized algorithms for solving vehicle routing problems with non-smooth objective functions. Our approach employs non-uniform probability distributions to add a biased random behavior to the well-known savings heuristic. By doing so, a large set of alternative good solutions can be quickly obtained in a natural way and without complex configuration processes. Since the solution-generation process is based on the criterion of maximizing the savings, it does not need to assume any particular property of the objective function. Therefore, the procedure can be especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods—both of exact and approximate nature—may fail to reach their full potential. The results obtained so far are promising enough to suggest that the idea of using biased probability distributions to randomize classical heuristics is a powerful one that can be successfully applied in a variety of cases.     

Numerical algorithm for solving mathematical programming problems with a smooth surface as a constraint

A numerical algorithm for minimizing a convex function on a smooth surface is proposed. The algorithm is based on reducing the original problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.