Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

Branching Constraint Satisfaction Problems (BCSPs) model a class of uncertain dynamic resource allocation problems. We describe the features of BCSPs, and show that the associated decision problem is NP-complete. Markov Decision Problems could be used in place of BCSPs, but we show analytically and empirically that, for the class of problems in question, the BCSP algorithms are more efficient than the related MDP algorithms.     

一种部分约束满足车辆路线问题及其求解算法

描述了一类过度约束车辆路线问题，其中可用车辆数较少而时间窗口等其它约束又不允许放松，因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理，相应的优化目标是最小化未访问顾客的损失和。本给出了求解这类特殊问题的一种禁忌搜索算法设计，并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。     

Weight-based Heuristics for Constraint Satisfaction and Combinatorial Optimization Problems

In this paper, we propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight-based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy-based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time-lags, considering various parameter settings and variants of the methods.The results show that weighting mechanisms reduce the tree size and then speed up the solving time, especially for the discrepancy-based search method.     

Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.     

解带有等式约束的可能性线性规划问题

本文给出了等式约束与不等式约束的关系定理,解决了带等式约束的可能性线性规划问题。     

Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

与GA-凸函数有关的若干单调函数

利用GA-凸函数的定义及其Hermite-Hadamard型不等式,得到与GA-凸函数有关的若干单调函数.     

An Accelerated Algorithm Involving Quasi-$\phi$-Nonexpansive Operators for Solving Split Problems

In this paper, an algorithm of inertial type for approximating solutions of split equality fixed point problems involving quasi-$\phi$-nonexpansive maps is proposed and studied in the setting of certain real Banach spaces. Weak and strong convergence theorems are proved under some conditions. Some applications of the theorems are presented. The results presented extend and improve some existing results. Finally, some numerical illustrations are presented to support our theorems and their applications.     

多元函数条件极值的四种求解方法

多元函数条件极值是高等数学的重要内容之一,本文从等式约束、区域约束、拉格朗日乘子法和单位向量约束下二次型最值问题四个角度切入,力图全面介绍高等数学中有关多元函数极值的问题.     

Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

Let C_n,cn^2,k,t be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish upper bounds for the tightness threshold for C_n,cn^2,k,t to have an exponential resolution complexity. The upper bounds partly answers the open problems regarding the CSP resolution complexity with the tightness between the existing upper and lower bound [1].     

Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0–1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak.     

Solving Continuous-Time Linear Programming Problems Based on the Piecewise Continuous Functions

The numerical method is proposed in this article to solve a general class of continuous-time linear programming problems in which the functions appeared in the coefficients of this problem are assumed to be piecewise continuous. In order to make sure that all the subintervals of time interval will not contain the discontinuities, a different methodology for not equally partitioning the time interval is proposed. The main issue of this article is to obtain an analytic formula of error upper bound. In this article, we shall propose two kinds of computational procedure to evaluate the error upper bounds. One needs to solve the dual problem of the discretized linear programming problem, and another one does not need to solve the dual problem. Finally, we present a numerical example to demonstrate the usefulness of the numerical method.     

涉及Jensen函数的不等式

引入了Jensen函数及Jensen平均的概念,借助于数学分析和代数工具给出了Jensen函数的分解公式,利用这个公式给出了推广和加强Jensen不等式的一种崭新的思路,作为应用,给出了Jensen不等式成立的一个有趣的充分条件．旨在为数学研究提供一些有用的解析不等式．     

Solving a Class of Brouwer Fixed-point Problems via a Modified Aggregate Constraint Homotopy Method

In this paper, we provide an aggregate function homotopy interior point method to solve a class of Brouwer fixed-point problems. Compared with the homotopy method （proposed by Yu and Lin, Appl. Math. Comput., 74（1996）, 65）, the main adavantages of this method are as foUows： on the one hand, it can solve the Brouwer fixed-point problems in a broader class of nonconvex subsets Ω in R^n （in this paper, we let Ω={x∈ R^n ： gi（x） ≤0, i= 1,... , m}）; on the other hand, it can also deal with the subsets Ω with larger amount of constraints more effectively.     

求解非线性方程根四阶收敛的迭代格式

提出了求解非线性方程根新的四阶收敛迭代方法,新方法每次迭代只需要两次函数计算,一次一阶导数值计算,效能指数达到1.587.通过几个数值算例来解释该方法的有效性.     

用改进的凝聚约束同伦方法求解一类Brouwer不动点问题

In this paper, we provide an aggregate function homotopy interior point method to solve a class of Brouwer fixed-point problems. Compared with the homotopy method (proposed by Yu and Lin, Appl. Math. Comput., 74(1996), 65), the main adavantages of this method are as follows: on the one hand, it can solve the Brouwer fixed-point problems in a broader class of nonconvex subsets Ω in Rn (in this paper, we let Ω = [x ∈ Rn: gi(x) ≤ 0, i = 1,… ,m]); on the other hand, it can also deal with the subsets Ω with larger amount of constraints more effectively.     

Inequalities Involving Superquadratic Functions and Operators

By the use of some integral inequalities containing superquadratic functions, we obtain an inequality which generalizes some previous results. We also present an inequality for positive linear mappings of operators on Hilbert spaces. Some applications and examples are given as well.