Necessary and sufficient conditions for some constraint qualifications in quasiconvex programming

In this paper, we investigate relations between constraint qualifications in quasiconvex programming. At first, we show a necessary and sufficient condition for the closed cone constraint qualification for quasiconvex programming (Q-CCCQ), and investigate some sufficient conditions for the Q-CCCQ. Also, we consider a relation between the Q-CCCQ and the basic constraint qualification for quasiconvex programming (Q-BCQ) and we compare the Q-BCQ with some constraint qualifications.     

MCS—A new algorithm for multicriteria optimisation in constraint programming

In this paper we propose a new algorithm called MCS for the search for solutions to multicriteria combinatorial optimisation problems. To quickly produce a solution that offers a good trade-off between criteria, the MCS algorithm alternates several Branch & Bound searches following diversified search strategies. It is implemented in CP in a dedicated framework and can be specialised for either complete or partial search.     

Integration and propagation of a multi-criteria decision making model in constraint programming

In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in Constraint Programming. We introduce the Choquet integral as a general aggregation function for multi-criteria optimization problems and define the Choquet global constraint that propagates this function during the Branch-and-Bound search. Finally the benefits of the propagation of the Choquet constraint are evaluated on the examination timetabling problem.     

Optimality conditions and the basic constraint qualification for quasiconvex programming

In this paper, we consider optimality conditions and a constraint qualification for quasiconvex programming. For this purpose, we introduce a generator and a new subdifferential for quasiconvex functions by using Penot and Volle’s theorem.     

Branch-and-price and constraint programming for solving a real-life technician dispatching problem

We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. A branch-and-price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with constraint programming in the column generation phase. The column generation takes advantage of the fact that each technician can satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice.     

A constraint qualification for convex programming

1. IntroductionLet X be the n-dimensional Euclidean space Rad. Denote the transpose of the columnvector y by yT. Suppose that R7 and nit R= are the n-dimensional vector sets with nonnegative and positive components, whose elements are denoted by y 3 0 and y > 0, respectively.Write R for the nonnegative real number set.Consider a nondiffereatiable convex programming problem:We assume that f(x), gi(x),..', g.(x) are finite reaLvalued continuous, convex functions on X, but not necessarily d…     

Separable programming/duality approach to solving the multi-product Newsboy/Gardener Problem with linear constraints

The Gardener Problem is an extension of the multi-product Newsboy Problem with constraints. It deals with situations where not only the demand is random but also the yield (the supply). Separable programming and duality approaches are utilized to solve the constrained Newsboy/Gardener Problem. The solution methodologies are developed for the common probability distribution functions for the demand, and uniform distribution for the supply, rendering exact and approximate solutions to the problem. Numerical examples are given and when applicable, the performance of the developed approach is compared to those of existing works in this arena. The results reveal that the developed solution methods efficiently converge to the optimal or near optimum solutions. Also, a salient feature of the proposed methodologies is that they can utilize readily available commercial software to solve the considered problems. This feature facilitates the portability of the developed models to the classroom environment.     

Generalised graph colouring by a hybrid of local search and constraint programming

The IMPASSE class of local search algorithms have given good results on many vertex colouring benchmarks. Previous work enhanced IMPASSE by adding the constraint programming technique of forward checking, in order to prune colouration neighbourhoods during search. On several large graphs the algorithm found the best known colourings. This paper extends the work by improving the heuristics and generalising the approach to bandwidth multicolouring. It is shown to give better results than a related search algorithm on an integer programming model, and to be competitive with published results. Experiments indicate that stronger constraint propagation further improves search performance, but that a symmetry breaking technique has unpredictable effects.     

A constraint programming approach for a batch processing problem with non-identical job sizes

This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price.     

Using separable programming to solve the multi-product multiple ex-ante constraint newsvendor problem and extensions

This paper provides an approximating programming technique to solve the multi-product newsvendor model in which product demands are independent and stocking quantities are subject to two or more ex-ante linear contraints, such as budget or volume constraints. Previous research has attempted to solve this problem with Lagrange relaxation techniques or by limiting the distribution of demand. However, by taking advantage of the separable nature of the problem, a close approximation of the optimal solution can be found using convex separable programming for any demand distribution in the traditional newsvendor model and extensions. Sensitivity analysis of the linear program provides managerial insight into the effects of parameters of the problem on the optimal solution and future decisions.     

Mathematical programming in the Netherlands

Results of an exhaustive survey of mathematical programming in the Netherlands held in 1982 are presented and, where applicable, compared to a survey held in 1976. It appears that the growth rate has levelled off, that about half of the largest one hundred industrial firms in the Netherlands now apply MP and that the users are quite satisfied with LP programs except for input, output and documentation.     

A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.     

Enhancing set constraint solvers with lexicographic bounds

Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit and combinatorial design. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinatorial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable, and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.     

Mathematical programming techniques in majorization

In this paper, we are concerned with mathematical programs which construct nonmajorizing vectors for several specific majorization applications. In particular, we develop a linear integer program and two integer goal programs which solve the assignment majorization problem. We also develop a quadratic program for solving majorization problems which arise in probability and statistics. In the appendix, we present a general goal-programming algorithm for these, as well as others, goal programs.The authors would like to thank Professor Y. Tong for introducing them to majorization and its applications. They would also like to thank Professors Y. Tong and D. Mesner for helpful discussions.     

A simple constraint qualification in infinite dimensional programming

A new, simple, constraint qualification for infinite dimensional programs with linear programming type constraints is used to derive the dual program; see Theorem 3.1. Applications include a proof of the explicit solution of the best interpolation problem presented in [8].     

A procedure for parameterizing a constraint in linear programming

A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.     

On stability of minimizers in convex programming

In this paper, we establish conditions ensuring Hölder and Lipschitz continuity of minimizers in convex programming. Lipschitz continuity is proved by establishing and applying a generalized version of the implicit function theorem.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.