Reasoning with doubly uncertain soft constraints

We describe the basic ideas of the theory of approximate reasoning and indicate how it provides a framework for representing human sourced soft information. We discuss how to translate linguistic knowledge into formal representations using generalized constraints. We consider the inference process within the theory of approximate reasoning and introduce the entailment principle and describe its centrality to this inference process. Next we introduce the idea of doubly uncertain statements such as John’s friend is young. In these statements there exists uncertainty both with respect to value of the age, young, and the object associated with the age, John’s friend. We suggest a method for representing these complex statements and investigate the problem of making inferences about specific objects.     

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic optimization problems. The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

A logic of soft constraints based on partially ordered preferences

Representing and reasoning with an agent’s preferences is important in many applications of constraints formalisms. Such preferences are often only partially ordered. One class of soft constraints formalisms, semiring-based CSPs, allows a partially ordered set of preference degrees, but this set must form a distributive lattice; whilst this is convenient computationally, it considerably restricts the representational power. This paper constructs a logic of soft constraints where it is only assumed that the set of preference degrees is a partially ordered set, with a maximum element 1 and a minimum element 0. When the partially ordered set is a distributive lattice, this reduces to the idempotent semiring-based CSP approach, and the lattice operations can be used to define a sound and complete proof theory. A generalised possibilistic logic, based on partially ordered values of possibility, is also constructed, and shown to be formally very strongly related to the logic of soft constraints. It is shown how the machinery that exists for the distributive lattice case can be used to perform sound and complete deduction, using a compact embedding of the partially ordered set in a distributive lattice.     

Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints

In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A Branch-and-Bound method that does not use derivatives for solving the reduced problem is proposed. The method either determines the infeasibility of the original problem or finds lower and upper bounds for the global solution. Not all the constraints are evaluated during every iteration of the algorithm, providing a significant acceleration of the search. Convergence conditions of the new method are established. Extensive numerical experiments are presented.     

An algorithm for solving global optimization problems with nonlinear constraints

In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.     

On-line algorithms for networks of temporal constraints

We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. We show how to maintain the path-consistency in O(nR³) amortized time on a sequence of Θ(n²) insertions, where n is the number of vertices of the network and R is its range, defined as the maximum size of the minimum interval containing all the intervals of a single constraint.Furthermore we extend our algorithms to deal with more general temporal networks where variables can be points and/or intervals and constraints can also be defined on pairs of different kinds of variables. For such cases our algorithms maintain their performance. Finally, we adapt our algorithms to also maintain the arc-consistency of such generalized networks in O(R) amortized time for Θ(n²) insertions.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

Systems of linear fuzzy constraints

Linear Fuzzy constraints are linear constraints where coefficients are fuzzy numbers. This paper demonstrates that two points of view can be considered to extend classical linear constraints: either tolerance constraints, or approximate (in)equality constraints can be obtained. Resolution of systems of linear fuzzy constraints is shown to be made easier by the use of fuzzy numbers analytically represented through a given type of membership function and three parameters. Solution methods are provided in the case of non fuzzy variables; as an illustration, some numerical examples are presented. The fuzzy variable case is also evoked.This paper is part of Purdue University Electrical Engineering technical report TR-EE 78-13.     

A parallel algorithm for partially separable non-convex global minimization: Linear constraints

The global minimization of large-scale partially separable non-convex problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of a separable concave part, an unseparated convex part, and a strictly linear part, which are all coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. An important special class of problems which can be reduced to this form are the synomial global minimization problems. Such problems often arise in engineering design, and previous computational methods for such problems have been limited to the convex posynomial case. In the current work, a convex underestimating function to the objective function is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and convex underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results obtained on the four processor Cray 2, both sequentially and in parallel on all four processors, are also presented.     

Hard and soft constraints for reasoning about qualitative conditional preferences

Many real life optimization problems are defined in terms of both hard and soft constraints, and qualitative conditional preferences. However, there is as yet no single framework for combined reasoning about these three kinds of information. In this paper we study how to exploit classical and soft constraint solvers for handling qualitative preference statements such as those captured by the CP-nets model. In particular, we show how hard constraints are sufficient to model the optimal outcomes of a possibly cyclic CP-net, and how soft constraints can faithfully approximate the semantics of acyclic conditional preference statements whilst improving the computational efficiency of reasoning about these statements. This material is based in part upon works supported by the Science Foundation Ireland under Grant No. 00/PI.1/C075     

A family of global classical solutions to 3D incompressible nematic liquid crystal flows

In this paper we construct a family of finite energy smooth solutions to the three-dimensional incompressible nematic liquid crystal flows. We achieve this by choosing the steady state Beltrami flows which have infinite energies as the initial data and using a special cut-off technique.     

ODE methods for optimization with equality constraints

In an optimization problem with equality constraints we define an accessory function that is similar but different from a normal penalty function. In the accessory function we demonstrate the need to use small values of the parameter associated with an equality constraint. Large values of the parameter create extraneous stationary points which destroy the global convergence properties of steepest descent methods. By using small values of the parameters in the accessory function, when the current point is far away from the solution and when the constraint violations are large we are led to a refined version of the established SUMT method.     

On nonconvex optimization with integral constraints

We consider the problem of minimizing f(y)dm with y dm=c,c fixed. The functionf is assumed to be continuous, but need not be convex. For this problem, we give necessary and sufficient conditions for the existence of solutions. We also give conditions under which uniqueness in a certain sense holds, and we show a relation which holds between the minimizers of two different problems and the corresponding values of the constraintsc.This research was supported by FINEP-Brazil, Grant Nos. 62.24-0416-00 and 4.2.82.0719-00.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

The quickest path problem with batch constraints

The quickest path problem has been proposed to cope with flow problems through networks whose arcs are characterized by both travel times and flowrate constraints. Basically, it consists in finding a path in a network to transmit a given amount of items from a source node to a sink in as little time as possible, when the transmission time depends on both the traversal times of the arcs and the rates of flow along arcs. This paper is focused on the solution procedure when the items transmission must be partitioned into batches with size limits. For this problem we determine how many batches must be made and what the sizes should be.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

On global periodicity of difference equations

In this research, we consider a difference equation of order k?2 of the following form:

     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.