The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.     

Uniform duality in semi-infinite convex optimization

We study infinite sets of convex functional constraints, with possibly a set constraint, under general background hypotheses which require closed functions and a closed set, but otherwise do not require a Slater point. For example, when the set constraint is not present, only the consistency of the conditions is needed. We provide hypotheses, which are necessary as well as sufficient, for the overall set of constraints to have the property that there is no gap in Lagrangean duality for every convex objective function defined on ℝⁿ. The sums considered for our Lagrangean dual are those involving only finitely many nonzero multipliers. In particular, we recover the usual sufficient condition when only finitely many functional constraints are present. We show that a certain compactness condition in function space plays the role of finiteness, when there are an infinite number of functional constraints. The author's research has been partially supported by Grant ECS8001763 of the National Science Foundation.     

Partial differential equations with differential constraints

A geometric setting for constrained exterior differential systems on fibered manifolds with n-dimensional bases is proposed. Constraints given as submanifolds of jet bundles (locally defined by systems of first-order partial differential equations) are shown to carry a natural geometric structure, called the canonical distribution. Systems of second-order partial differential equations subjected to differential constraints are modeled as exterior differential systems defined on constraint submanifolds. As an important particular case, Lagrangian systems subjected to first-order differential constraints are considered. Different kinds of constraints are introduced and investigated (Lagrangian constraints, constraints adapted to the fibered structure, constraints arising from a (co)distribution, semi-holonomic constraints, holonomic constraints).     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

Constraint classification in mathematical programming

Consider a set of algebraic inequality constraints defining either an empty or a nonempty feasible region. It is known that each constraint can be classified as either absolutely strongly redundant, relatively strongly redundant, absolutely weakly redundant, relatively weakly redundant, or necessary. We show that is is worth making a distinction between weakly necessary constraints and strongly necessary constraints. We also present afeasible set cover method which can detect both weakly and strongly necessary constraints.The main interest in constraint classification is due to the advantages gained by the removal of redundant constraints. Since classification errors are likely to occur, we examine how the removal of a single constraint can affect the classification of the remaining constraints.     

A hierarchical location model for public facility planning

In this article, we present a discrete hierarchical location model for public facility planning. The main features of the model are: an accessibility maximization objective; several levels of demand and of facilities; a nested hierarchy of facilities (i.e. a facility of a given level can serve demand of equal and lower levels); maximum and minimum capacity constraints; and user-to-facility assignment constraints. The latter include single-assignment and closest-assignment constraints, as well as a new type of constraints called path-assignment constraints. Their purpose is to enforce some desirable properties for the spatial pattern of assignments. If they are not included, model solutions are difficult to interpret and to explain in a public facility planning context, therefore being less likely to be accepted by the users. The usefulness of the model is illustrated through a real-world application to school network planning.     

Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CF of constraints critical to feasibility.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

On constrained optimization problems with nonsmooth cost functionals

In this paper we present a computational procedure for minimizing a class ofL ₁-functionals subject to conventional as well as functional constraints. The computational procedure is based on the idea of enforced smoothing together with a method of converting the functional constraints into conventional equality constraints. For illustration, two examples are solved using the proposed procedure.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

Second-order conditions in extremal problems. The abnormal points

In this paper we study a minimization problem with constraints and obtain first- and second-order necessary conditions for a minimum. Those conditions - as opposed to the known ones - are also informative in the abnormal case. We have introduced the class of 2-normal constraints and shown that for them the ``gap" between the sufficient and the necessary conditions is as minimal as possible. It is proved that a 2-normal mapping is generic.

     

New minimax algorithm

The purpose of this paper is to suggest a new, efficient algorithm for the minmax problem $$\mathop {min}\limits_x \mathop {max}\limits_i f_i (x), x \in \Re ^n , i = 1, \ldots ,m,$$ wheref _i ,i=1,...,m, are real-valued functions defined on ? ⁿ . The problem is transformed into an equivalent inequality-constrained minimization problem, mint, s.t.f _i (x)?t≤0, for alli, i=1,...,m. The algorithm has these features: an active-set strategy with three types of constraints; the use of slack variables to handle inequality constraints; and a trust-region strategy taking advantage of the structure of the problem. Following Tapia, this problem is solved by an active set strategy which uses three types of constraints (called here nonactive, semiactive, and active). Active constraints are treated as equality constraints, while semiactive constraints are treated as inequality constraints and are assigned slack variables. This strategy helps to prevent zigzagging. Numerical results are provided.     

Zero-sum constrained stochastic games with independent state processes

We consider a zero-sum stochastic game with side constraints for both players with a special structure. There are two independent controlled Markov chains, one for each player. The transition probabilities of the chain associated with a player as well as the related side constraints depend only on the actions of the corresponding player; the side constraints also depend on the player’s controlled chain. The global cost that player 1 wishes to minimize and that player 2 wishes to maximize, depend however on the actions and Markov chains of both players. We obtain a linear programming formulations that allows to compute the value and saddle point policies for this problem. We illustrate the theoretical results through a zero-sum stochastic game in wireless networks in which each player has power constraints     

Separable nonlinear least squares fitting with linear bound constraints and its application in magnetic resonance spectroscopy data quantification

An application in magnetic resonance spectroscopy quantification models a signal as a linear combination of nonlinear functions. It leads to a separable nonlinear least squares fitting problem, with linear bound constraints on some variables. The variable projection (VARPRO) technique can be applied to this problem, but needs to be adapted in several respects. If only the nonlinear variables are subject to constraints, then the Levenberg–Marquardt minimization algorithm that is classically used by the VARPRO method should be replaced with a version that can incorporate those constraints. If some of the linear variables are also constrained, then they cannot be projected out via a closed-form expression as is the case for the classical VARPRO technique. We show how quadratic programming problems can be solved instead, and we provide details on efficient function and approximate Jacobian evaluations for the inequality constrained VARPRO method.     

Possibility and necessity constraints and their defuzzification—A multi-item production-inventory scenario via optimal control theory

In this paper, analogous to chance constraints, real-life necessity and possibility constraints in the context of a multi-item dynamic production-inventory control system are defined and defuzzified following fuzzy relations. Hence, a realistic multi-item production-inventory model with shortages and fuzzy constraints has been formulated and solved for optimal production with the objective of having minimum cost. Here, the rate of production is assumed to be a function of time and considered as a control variable. Also the present system produces some defective units along with the perfect ones and the rate of produced defective units is constant. Here demand of the good units is time dependent and known and the defective units are of no use. The space required per unit item, available storage space and investment capital are assumed to be imprecise. The space and budget constraints are of necessity and/or possibility types. The model is formulated as an optimal control problem and solved for optimum production function using Pontryagin’s optimal control policy, the Kuhn–Tucker conditions and generalized reduced gradient (GRG) technique. The model is illustrated numerically and values of demand, optimal production function and stock level are presented in both tabular and graphical forms. The sensitivity of the cost functional due to the changes in confidence level of imprecise constraints is also presented.     

Distribution requirements and compactness constraints in school timetabling

This paper provides the following contributions: First, distribution requirements for lessons of different lengths are modelled in a novel way by the use of the so-called multiple mode concept with mode identity constraints. Second, we show that several types of constraints may be modelled using the unifying framework of partially renewable resources. Among these constraints are: No class, subject, room, and teacher overlaps; class, subject, room, and teacher unavailabilities; compactness constraints; preassignment constraints; lectures to be given simultaneously; lunch breaks, etc. Third, we present two-phase parallel greedy randomized and genetic methods. Fourth, we provide an instance generator for the generation of a representative set of instances. Fifth, the generator along with a statistical model is used for a thorough experimental evaluation of the methods. Computational results show that the methods solve the instances investigated close to optimality.     

Closed formulas in local sensitivity analysis for some classes of linear and non-linear problems

This paper presents an integrated approach to sensitivity analysis in some linear and non-linear programming problems. Closed formulas for the sensitivities of the objective function and primal and dual variables with respect to all parameters for some classes of problems are obtained. As particular cases, the sensitivities with respect to all data values, i.e., cost coefficients, constraints coefficients and right hand side terms of the constraints are provided for these classes of problems as closed formulas. The method is illustrated by its application to several examples.      

Tests of ignoring and eliminating in nonsymmetric correspondence analysis

Nonsymmetric correspondence analysis (NSCA) aims to examine predictive relationships between rows and columns of a contingency table. The predictor categories of such tables are often accompanied by some auxiliary information. Constrained NSCA (CNSCA) incorporates such information as linear constraints on the predictor categories. However, imposing constraints also means that part of the predictive relationship is left unaccounted for by the constraints. A method of NSCA is proposed for analyzing the residual part along with the part accounted for by the constraints. The CATANOVA test may be invoked to test the significance of each part. The two tests parallel the distinction between tests of ignoring and eliminating, and help gain some insight into what is known as Simpson’s paradox in the analysis of contingency tables. Two examples are given to illustrate the distinction.