Facets for node packing

The Node Packing Problem is an extremely important problem given that it comprises the underlying structure of numerous optimization problems either directly or indirectly. This paper presents a constraint approach which produces new facets for the Node Packing Problem. A number of different problem applications are solved incorporating this new constraint approach using a commercial software package on a personal computer demonstrating the effectiveness of the underlying facets in practice. The new facet structures provide a means for addressing general dispersion and separation requirements using mathematical programming.     

Constraint Programming and Hybrid Formulations for Three Life Designs

Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/integer programming methods. We consider three Life pattern-creation problems: finding maximum density still-Lifes, finding smallest immediate predecessor patterns, and finding period-2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.     

线性规划的约束条件“滚雪球”算法

为使线性规划的每个约束条件部分或全部地拥有原整个约束条件所包含的信息,将线性规划的约束条件“滚雪球”后得到与原约束条件等价的新约束条件,对新约束条件所构成的线性规划采用目标函数最速递减算法.有一定规模的随机数值算例显示了该算法只需进行m(约束条件数)次迭代即可求得最优解.     

SARPlan: A decision support system for Canadian Search and Rescue Operations

We present SARPlan, a geographic decision support system designed to assist the Canadian Forces in the optimal planning of search missions for missing aircraft. Its primary purpose is to ensure that the available search resources are deployed in a way that will maximize the mission's probability of success. The optimization modules are based on search theory, on gradient search methods and on constraint satisfaction programming. We include results that demonstrate that SARPlan improves the performance when compared to the current manual method. This improvement translates to an increase in the chances of finding lost aircraft and survivors, resulting in more saved lives. Another benefit of using SARPlan is a potential decrease in the operations costs. In 2001, SARPlan was the winner of three prestigious excellence awards in the information technology domain.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

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.     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

一些类型的数学规划问题的全局最优解

本文对严格单调函数给出了几个凸化和凹化的方法，利用这些方法可将一个严格单调的规划问题转化为一个等价的标准D．C．规划或凹极小问题．本文还对只有一个严格单调的约束的非单调规划问题给出了目标函数的一个凸化和凹化方法，利用这些方法可将只有一个严格单调约束的非单调规划问题转化为一个等价的凹极小问题．再利用已有的关于D．C．规划和凹极小的算法，可以求得原问题的全局最优解．     

A branch-and-bound algorithm for solving a fixed charge problem in the profit optimization of sawn timber production

This paper deals with the problem of profit optimization in sawn timber production, utilizing a special type of sawmill. Expected rejects and resetting costs are taken into consideration. The present problem is formulated as a fixed charge linear programming problem involving identical fixed charges, one equality constraint and explicit bounds on the variables. Based on the greedy sorting of the variables we develop a branch-and-bound algorithm working on a special subset of all solutions. Through usage of the problem structure for constructing bounds we arrive at an acceptable CPU-time (on a 80386 personal computer) for practical purposes.     

New Constraint Qualifications and Optimality Conditions for Second Order Cone Programs

We introduce three new constraint qualifications for nonlinear second order cone programming problems that we call constant rank constraint qualification, relaxed constant rank constraint qualification and constant rank of the subspace component condition. Our development is inspired by the corresponding constraint qualifications for nonlinear programming problems. We provide proofs and examples that show the relations of the three new constraint qualifications with other known constraint qualifications. In particular, the new constraint qualifications neither imply nor are implied by Robinson’s constraint qualification, but they are stronger than Abadie’s constraint qualification. First order necessary optimality conditions are shown to hold under the three new constraint qualifications, whereas the second order necessary conditions hold for two of them, the constant rank constraint qualification and the relaxed constant rank constraint qualification.

     

Constraint propagation,relational arithmetic in AI systems and mathematical programs

This paper explores the interrelationships between methods developed in mathematical programming to discover the structure of constraint (feasibility) sets and constraint propagation over networks used by some AI systems to perform inferences about quantities. It is shown that some constraint set problems in mathematical programming are equivalent to inferencing problems for constraint networks with interval labels. This makes the inference and query capabilities associated with AI systems that use logic programming, directly accessible to mathematical programming systems. On the other hand, traditional and newer methods which mathematical programming uses to obtain information about its associated feasibility set can be used to determine the propagation of constraints in a network of nodes of an AI system. When viewed from this point of view, AI problems can access additional mathematical programming analytical tools including new ways to incorporate qualitative data into constraint sets via interval and fuzzy arithmetic.This work was partially supported by the Industrial Consortium to Develop an Intelligent Mathematical Programming System — Amoco Oil Company, General Research Corporation, Ketron Management Science, Shell Oil Company, MathPro, and US West Advanced Technologies.     

非光滑半定规划的一阶最优性条件

首次考虑了非光滑半定规化问题．运用与非线性规划类似的技巧,把现存的理论扩展到约束是结构稀疏矩阵的情况,给出了其一阶最优性条件。考虑了严格互补条件不成立的情形．在约束矩阵为对角阵条件下,所用的正则条件与传统非线性优化意义下的是一致的．     

Some constraint qualifications for quasiconvex vector-valued systems

In this paper, we consider minimization problems with a quasiconvex vector-valued inequality constraint. We propose two constraint qualifications, the closed cone constraint qualification for vector-valued quasiconvex programming (the VQ-CCCQ) and the basic constraint qualification for vector-valued quasiconvex programming (the VQ-BCQ). Based on previous results by Benoist et al. (Proc Am Math Soc 13:1109–1113, 2002), and Suzuki and Kuroiwa (J Optim Theory Appl 149:554–563, 2011), and (Nonlinear Anal 74:1279–1285, 2011), we show that the VQ-CCCQ (resp. the VQ-BCQ) is the weakest constraint qualification for Lagrangian-type strong (resp. min–max) duality. As consequences of the main results, we study semi-definite quasiconvex programming problems in our scheme, and we observe the weakest constraint qualifications for Lagrangian-type strong and min–max dualities. Finally, we summarize the characterizations of the weakest constraint qualifications for convex and quasiconvex programming.     

0-1线性规划的连续化及其遗传算法解法

将0-1离散规划通过一个非线性等式约束表示为[0,1]区间上等价的连续变量非线性规划列式.对非线性等式约束的问题进行了两种方法的处理.第一种方法使用乘子法,第二种方法将非线性的等式约束近似为一个非线性的不等式约束,均利用遗传算法程序GENOCOP进行了求解.对多个算例进行了计算,结果表明了该方法的可行性和有效性.     

Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

This paper extends and completes the discussion by Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).     

Mixed Duality without Constraint Qualification for Nonsmooth Fractional Programming

A class of nonsmooth multiobjective fractional programming is formulated. We establish the necessary and sufficient optimality conditions without the need of a constraint qualification. Then a mixed dual is introduced for a class of nonsmooth fractional programming problems, and various duality theorems are established without a constraint qualification.     

Duality Theorems for Separable Convex Programming Without Qualifications

In the research of mathematical programming, duality theorems are essential and important elements. Recently, Lagrange duality theorems for separable convex programming have been studied. Tseng proves that there is no duality gap in Lagrange duality for separable convex programming without any qualifications. In other words, although the infimum value of the primal problem equals to the supremum value of the Lagrange dual problem, Lagrange multiplier does not always exist. Jeyakumar and Li prove that Lagrange multiplier always exists without any qualifications for separable sublinear programming. Furthermore, Jeyakumar and Li introduce a necessary and sufficient constraint qualification for Lagrange duality theorem for separable convex programming. However, separable convex constraints do not always satisfy the constraint qualification, that is, Lagrange duality does not always hold for separable convex programming. In this paper, we study duality theorems for separable convex programming without any qualifications. We show that a separable convex inequality system always satisfies the closed cone constraint qualification for quasiconvex programming and investigate a Lagrange-type duality theorem for separable convex programming. In addition, we introduce a duality theorem and a necessary and sufficient optimality condition for a separable convex programming problem, whose constraints do not satisfy the Slater condition.     

一类稀疏约束非线性规划的约束规格

研究一类带有闭凸集约束的稀疏约束非线性规划问题,这类问题在变量选择、模式识别、投资组合等领域具有广泛的应用.首先引进了限制性Slater约束规格的概念,证明了该约束规格强于限制性M-F约束规格,然后在此约束规格成立的条件下,分析了其局部最优解成立的充分和必要条件.最后,对约束集合的两种具体形式,指出限制性Slater约束规格必满足,并给出了一阶必要性条件的具体表达形式.     

Integrating Operations Research in Constraint Programming

This paper presents Constraint Programming as a natural formalism for modelling problems, and as a flexible platform for solving them. CP has a range of techniques for handling constraints including several forms of propagation and tailored algorithms for global constraints. It also allows linear programming to be combined with propagation and novel and varied search techniques which can be easily expressed in CP. The paper describes how CP can be used to exploit linear programming within different kinds of hybrid algorithm. In particular it can enhance techniques such as Lagrangian relaxation, Benders decomposition and column generation.     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000