共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Constraint Programming and Operations Research: Comments from an Operations Researcher 总被引:4,自引:0,他引:4
Michel Gendreau 《Journal of Heuristics》2002,8(1):19-24
This paper relates the author's personal experience with constraint programming and gives a personal assessment of the relationships between constraint programming and operations research. 相似文献
3.
本文研究了文[1]中提出的较多约束规划的基本问题,在给出问题的较多约束集结构表示的基础上,证明了这类问题的较多约束最优解要满足的Fritz John条件和Kuhn-Tucker条件。 相似文献
4.
Amal de Silva 《Annals of Operations Research》2001,108(1-4):277-291
This paper provides details of a successful application where the Column Generation algorithm was used to combine Constraint Programming and Linear Programming. In the past, constraint programming and linear programming were considered to be two competing technologies that solved similar types of problems. Both these technologies had their strengths and weaknesses. This paper shows that the two technologies can be combined together to extract the strengths of both these technologies. Details of a real-world application to optimize bus driver duties is given here. This system was developed by ILOG for a major software house in Japan using ILOG-Solver and ILOG-CPLEX, constraint programming and linear programming C/C++ libraries. 相似文献
5.
提出了一类特殊类型的数学规划模型并给出了一种新的分枝定界算法.这类数学模型尽管可以转化为0-1规划模型,但它相对于转化后的0-1规划模型:①决策意义明确,表达形式相对简单;②不需要引入参数M并在求解前确定其上界;③相对于求解转化后的0-1规划模型的分枝定界法,新分枝定界算法在最好情形下计算量最多为原算法的八分之一.作为本模型的一个应用,可以用来解决一些要么不实施要么有一定数量下限限制才可以实施的决策问题. 相似文献
6.
In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics. 相似文献
7.
8.
E. Castillo A. J. Conejo C. Castillo R. Mínguez D. Ortigosa 《Journal of Optimization Theory and Applications》2006,128(1):49-74
This paper presents a perturbation approach for performing sensitivity analysis of mathematical programming problems. Contrary
to standard methods, the active constraints are not assumed to remain active if the problem data are perturbed, nor the partial
derivatives are assumed to exist. In other words, all the elements, variables, parameters, Karush–Kuhn–Tucker multipliers,
and objective function values may vary provided that optimality is maintained and the general structure of a feasible perturbation
(which is a polyhedral cone) is obtained. This allows determining: (a) the local sensitivities, (b) whether or not partial
derivatives exist, and (c) if the directional derivative for a given direction exists. A method for the simultaneous obtention
of the sensitivities of the objective function optimal value and the primal and dual variable values with respect to data
is given. Three examples illustrate the concepts presented and the proposed methodology. Finally, some relevant conclusions
are drawn.
The authors are indebted to the Ministry of Science and Education of Spain, Projects CICYT DPI2002-04172-C04-02 and CICYT
DPI2003-01362, and to the Fulbright Commission for partial support. The authors are grateful to the referees for comments
improving the quality of the paper. 相似文献
9.
L.Venkateswara Reddy R.N. Mukherjee 《Journal of Mathematical Analysis and Applications》1999,240(2):37
In this paper, a generalized ratio invexity concept has been applied for single objective fractional programming problems. A concept which has been invoked seems to be more general than the one used earlier by Khan and Hanson in such contexts. Further, duality results for fractional programs have also been obtained. 相似文献
10.
In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This paper presents a study using Constraint Logic Programming (CLP) to solve the cane transport scheduling problem. Tailored heuristic labelling order and constraints strategies are proposed and encouraging results of application to several test problems and one real-life case are presented. The preliminary results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem, with a potential decrease in development costs of the scheduling system. It can also be used as an efficient tool for rescheduling tasks which the existing cane transport scheduling system cannot perform well. 相似文献
11.
Dmitry I. Belov Ronald D. Armstrong 《Computational Optimization and Applications》2006,33(2-3):319-332
This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection
of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems
(MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate
lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including
combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented.
An erratum to this article is available at . 相似文献
12.
We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm. 相似文献
13.
DC Programming: Overview 总被引:13,自引:0,他引:13
Mathematical programming problems dealing with functions, each of which can be represented as a difference of two convex functions, are called DC programming problems. The purpose of this overview is to discuss main theoretical results, some applications, and solution methods for this interesting and important class of programming problems. Some modifications and new results on the optimality conditions and development of algorithms are also presented. 相似文献
14.
In this article,the authors discuss the optimal conditions of the linear fractional programming problem and prove that a locally optional solution is a globally optional so- lution and the locally optimal solution can be attained at a basic feasible solution with constraint condition. 相似文献
15.
神经网络技术最为成功的应用领域之一是用于求解优化问题,本文就近年来的求解优化问题的神经网络方法进行了综述 相似文献
16.
A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints 总被引:18,自引:0,他引:18
Masao Fukushima Zhi-Quan Luo Jong-Shi Pang 《Computational Optimization and Applications》1998,10(1):5-34
This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported. 相似文献
17.
The semantic constructions and results for definite programs do not extend when dealing with negation. The main problem is
related to a well-known problem in the area of algebraic specification: if we fix a constraint domain as a given model, its
free extension by means of a set of Horn clauses defining a set of new predicates is semicomputable. However, if the language
of the extension is richer than Horn clauses its free extension (if it exists) is not necessarily semicomputable. In this
paper we present a framework that allows us to deal with these problems in a novel way. This framework is based on two main
ideas: a reformulation of the notion of constraint domain and a functorial presentation of our semantics. In particular, the
semantics of a logic program P is defined in terms of three functors: that apply to constraint domains and provide the operational, the least fixpoint and the logical semantics of P, respectively. To be more concrete, the idea is that the application of to a specific constraint solver provides the operational semantics of P that uses this solver; the application of to a specific domain provides the least fixpoint of P over this domain; and, the application of to a theory of constraints provides the logic theory associated to P. In this context, we prove that these three functors are in some sense equivalent.
相似文献
18.
《Optimization》2012,61(12):2139-2155
ABSTRACTBy using an implicit function theorem and a result of error bound, we provide new constraint qualifications ensuring the Karush–Kuhn–Tuker necessary optimality conditions for both smooth and nonsmooth optimization problems in normed spaces or Banach spaces. 相似文献
19.
Whereas CP methods are strong with respect to the detection of local infeasibilities, OR approaches have powerful optimization abilities that ground on tight global bounds on the objective. An integration of propagation ideas from CP and Lagrangian relaxation techniques from OR combines the merits of both approaches. We introduce a general way of how linear optimization constraints can strengthen their propagation abilities via Lagrangian relaxation. The method is evaluated on a set of benchmark problems stemming from a multimedia application. The experiments show the superiority of the combined method compared with a pure OR approach and an algorithm based on two independent optimization constraints. 相似文献
20.
A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints 总被引:1,自引:0,他引:1
The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation
is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC.
A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global
convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy
condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported.
Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore. 相似文献