共查询到20条相似文献,搜索用时 578 毫秒
1.
J Little 《The Journal of the Operational Research Society》2001,52(1):82-92
Constraint Programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer Programming (IP), can still give a better performance on the same problem types. Central to IP's success is its reliance on a fast Linear Programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IP. Overall, CP+LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems. 相似文献
2.
3.
提出了一类特殊类型的数学规划模型并给出了一种新的分枝定界算法.这类数学模型尽管可以转化为0-1规划模型,但它相对于转化后的0-1规划模型:①决策意义明确,表达形式相对简单;②不需要引入参数M并在求解前确定其上界;③相对于求解转化后的0-1规划模型的分枝定界法,新分枝定界算法在最好情形下计算量最多为原算法的八分之一.作为本模型的一个应用,可以用来解决一些要么不实施要么有一定数量下限限制才可以实施的决策问题. 相似文献
4.
The generalization of policies in reinforcement learning is a main issue, both from the theoretical model point of view and for their applicability. However, generalizing from a set of examples or searching for regularities is a problem which has already been intensively studied in machine learning. Thus, existing domains such as Inductive Logic Programming have already been linked with reinforcement learning. Our work uses techniques in which generalizations are constrained by a language bias, in order to regroup similar states. Such generalizations are principally based on the properties of concept lattices. To guide the possible groupings of similar states of the environment, we propose a general algebraic framework, considering the generalization of policies through a partition of the set of states and using a language bias as an a priori knowledge. We give a practical application as an example of our theoretical approach by proposing and experimenting a bottom-up algorithm. 相似文献
5.
《European Journal of Operational Research》2006,173(2):519-530
This paper applies algorithms integrating Integer Programming (IP) and Constraint Programming (CP) to the Mutually Orthogonal Latin Squares (MOLS) problem. We investigate the behaviour of these algorithms against traditional IP and CP schemes. Computational results are obtained with respect to various aspects of the algorithms, using instances of the 2 MOLS and 3 MOLS problems. The benefits of integrating IP with CP on this feasibility problem are clearly exhibited, especially in large problem instances. 相似文献
6.
Ramayya Krishnan 《Annals of Operations Research》1989,21(1):195-226
Attempts to integrate Artificial Intelligence (AI) techniques into Decision Support Systems (DSS) have received much attention in recent years. Significant among these has been the application of knowledge-based techniques to support various phases of the modeling process. This paper describes a logic based approach to mechanically construct Linear Programming (LP) models from qualitative problem specifications and illustrates it in the context of production, distribution and inventory planning problems. Specifically, we describe the features of a first-order logic based formal language called PM which is at the heart of an implemented knowledge-based tool for model construction. Problems specified in PM define a logic model which is then used to generate problem-specific inferences, and as input to a set of logic programming procedures that perform model construction. 相似文献
7.
We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. 相似文献
8.
Jeroen Janssen Steven Schockaert Dirk Vermeir Martine De Cock 《International Journal of Approximate Reasoning》2012,53(4):660-692
A number of different Fuzzy Answer Set Programming (FASP) formalisms have been proposed in the last years, which all differ in the language extensions they support. In this paper we investigate the expressivity of these frameworks. Specifically we show how a variety of constructs in these languages can be implemented using a considerably simpler core language. These simulations are important as a compact and simple language is easier to implement and to reason about, while an expressive language offers more options when modeling problems. 相似文献
9.
Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree
search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the
neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming
(CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original
contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a
cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily
far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in
CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with
Time Windows. 相似文献
10.
11.
Gautam Mitra Cormac Lucas Shirley Moody Bjarni Kristjansson 《Computational Optimization and Applications》1995,4(3):263-283
LP models are usually constructed using index sets and data tables which are closely related to the attributes and relations of relational database (RDB) systems. We extend the syntax of MPL, an existing LP modelling language, in order to connect it to a given RDB system. This approach reuses existing modelling and database software, provides a rich modelling environment and achieves model and data independence. This integrated software enables Mathematical Programming to be widely used as a decision support tool by unlocking the data residing in corporate databases. 相似文献
12.
F Polimeno T Rehman H Neal C M Yates 《The Journal of the Operational Research Society》1999,50(9):931-942
Despite many refinements that have been made to the basic Linear Programming model used to find economically optimal diets for dairy cows, the sequential nature of the physical and physiological changes that a cow goes through during lactation have not been incorporated into the modelling process satisfactorily. This paper demonstrates how it can be achieved by integrating the use of both Linear and Dynamic Programming methods to optimise the economic performance of a dairy cow over its entire lactation. Linear Programming generates solutions for each potential liveweight change occurring during each of eleven four week periods over the lactation, then the use of DP allows both the selection of the optimal sequence of liveweight changes during the lactation and the specification of rations associated with this optimal path. 相似文献
13.
Jim Morey 《International Journal of Computers for Mathematical Learning》2006,11(2):147-175
This paper introduces the language associated with a polygon microworld called PolygonR&D, which has the mathematical crispness
of Logo and has the discreteness and simplicity of a Turing machine. In this microworld, polygons serve two purposes: as agents
(similar to the turtles in Logo), and as data (landmarks in the plane). Programming the spatial behaviour of polygon agents
is achieved by a simple variable-free language. Although limited in the number of instructions, the language allows for complex
outcomes such as creation of sophisticated tilings, algorithm visualization, simulations, and even numerical computation.
The ease of constructing the variety of examples shown in this paper indicates the microworld’s potential in both secondary
and post-secondary education.
An erratum to this article can be found at 相似文献
14.
The common difficulty in solving a Binary Linear Programming (BLP) problem is uncertainties in the parameters and the model structure. The previous studies of BLP problems normally focus on parameter uncertainty or model structure uncertainty, but not on both types of uncertainties. This paper develops an interval-coefficient Fuzzy Binary Linear Programming (IFBLP) and its solution for BLP problems under uncertainties both on parameters and model structure. In the IFBLP, the parameter uncertainty is represented by the interval coefficients, and the model structure uncertainty is reflected by the fuzzy constraints and a fuzzy goal. A novel and efficient methodology is used to solve the IFLBP into two extreme crisp-coefficient BLPs, which are called the ‘best optimum model’ and the ‘worst optimum model’. The results of these two crisp-coefficient extreme models can bound all outcomes of the IFBLP. One of the contributions in this paper is that it provides a mathematical sound approach (based on some mathematical developments) to find the boundaries of optimal alpha values, so that the linearity of model can be maintained during the conversions. The proposed approach is applied to a traffic noise control plan to demonstrate its capability of dealing with uncertainties. 相似文献
15.
H.P Williams 《Journal of Combinatorial Theory, Series A》1976,21(1):118-123
This paper describes how the Fourier-Motzkin Elimination Method, which can be used for solving Linear Programming Problems, can be extended to deal with Integer Programming Problems. The extension derives from a known decision procedure for the formal theory of a fragment of arithmetic which excludes multiplication. 相似文献
16.
Abundant and continuous old forest tend to be fragmented into isolated and small patches because of human harvest activities.
Dispersive and isolated old forest patches cannot provide abundant interior habitat to wildlife, which is a fatal threat for
specific plant communities and wildlife species. In this paper, an Integer Programming model for forest planning is designed
to maximize the economical benefit of the forest and to guarantee a minimum area of interior old forest for wildlife habitat,
the so-called core area satisfying minimum mature age requirements. The minimum core area constraints, to some degree, can
help mitigate the negative impact of harvest activities to divide forest habitat into many small patches. The model is implemented
in a commercial Integer Programming solver and it is applied to several hypothetical landscapes. The results show the possibility
of incorporating a core area requirement into a forest planning model, and the possibility to obtain solutions within a reasonable
computational time. Instances with up to 1600 management units have been solved in seconds to an optimality gap of 1% (0.1%
in some cases). 相似文献
17.
Aïda Kharrat Habib Chabchoub Belaïd Aouni Soulef Smaoui 《European Journal of Operational Research》2007
The Goal Programming (GP) model was used as a time-series analysis tool that incorporates a Serial Correlation where the dependent variable is considered as precise. This formulation does not take into consideration the decision-maker’s preferences. However, the dependent variable can be imprecise and its value can be expressed through an interval. The aim of this paper is to develop a new formulation of the GP model for regression with Serial Correlation where the dependent variable is imprecise. The proposed model will also integrate explicitly the decision-maker’s preferences. A numerical example was used to illustrate our model. 相似文献
18.
Alberto Delgado Rune Møller Jensen Kira Janstrup Trine Høyer Rose Kent Høj Andersen 《European Journal of Operational Research》2012
Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for large container vessels within a few minutes. It decomposes the problem into a master planning phase that distributes the containers to bay sections and a slot planning phase that assigns containers of each bay section to slots. In this paper, we focus on the slot planning phase of this approach and present a Constraint Programming and Integer Programming model for stowing a set of containers in a single bay section. This so-called slot planning problem is NP-hard and often involves stowing several hundred containers. Using state-of-the-art constraint solvers and modeling techniques, however, we were able to solve 90% of 236 real instances from our industrial collaborator to optimality within 1 second. Thus, somewhat to our surprise, it is possible to solve most of these problems optimally within the time required for practical application. 相似文献
19.
Ricardo C. Silva Carlos Cruz José L. Verdegay 《Fuzzy Optimization and Decision Making》2013,12(3):231-248
Although quadratic programming problems are a special class of nonlinear programming, they can also be seen as general linear programming problems. These quadratic problems are of the utmost importance in an increasing variety of practical fields. As, in addition, ambiguity and vagueness are natural and ever-present in real-life situations requiring operative solutions, it makes perfect sense to address them using fuzzy concepts formulated as quadratic programming problems with uncertainty, i.e., as Fuzzy Quadratic Programming problems. This work proposes two novel fuzzy-sets-based methods to solve a particular class of Fuzzy Quadratic Programming problems which have vagueness coefficients in the objective function. Moreover, two other linear approaches are extended to solve the quadratic case. Finally, it is shown that the solutions reached from the extended approaches may be obtained from two proposed parametric multiobjective approaches. 相似文献
20.
A novel approach to Bilevel nonlinear programming 总被引:3,自引:3,他引:0
Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex
optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional
programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the
monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into
a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound
method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.
相似文献