共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
S Heipcke 《The Journal of the Operational Research Society》1999,50(6):581-595
This paper is aimed at researchers and practitioners in Operational Research who are interested in the new field of Constraint Programming/Constraint Logic Programming. Due to differing terminology and problem representation they might have found it difficult to access the field. The paper focuses on discrete optimisation problems. The first part lists frequently used terms in Constraint Programming (CP), contrasting them with their counterparts in Mathematical Programming (MP). The second part explains some of the most important concepts and techniques in more detail by comparing the CP and MP implementations of a small example problem, the ‘Change Problem’. It includes an overview of the respective results. In conclusion a more generalised comparison of CP and MP techniques is given. 相似文献
3.
4.
Mathematical Programming - In this paper, we point out some corrections needed in “Complexity of Stochastic Dual Dynamic Programming”, a paper accepted to Mathematical Programming,... 相似文献
5.
Jesús M. Velásquez Bermúdez 《Annals of Operations Research》2002,117(1-4):21-31
This document presents theoretical considerations about the solution of dynamic optimization problems integrating the Benders Theory, the Dynamic Programming approach and the concepts of Control Theory. The so called Generalized Dual Dynamic Programming Theory (GDDP) can be considered as an extension of two previous approaches known as Dual Dynamic Programming (DDP): The first is the work developed by Pereira and Pinto [3–5], which was revised by Velásquez and others [8,9]. The second is the work developed by Read and others [2,6,7]. 相似文献
6.
Sven Leyffer 《Computational Optimization and Applications》2001,18(3):295-309
This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed. 相似文献
7.
H.P. Williams 《Discrete Applied Mathematics》1984,7(1):93-103
An analogous duality theorem to that for Linear Programming is presented for systems of linear congruences. It is pointed out that such a system of linear congruences is a relaxation of an Integer Programming model (for which the duality theorem does not hold). Algorithms are presented for both the resulting primal and dual problems. These algorithms serve to give a constructive proof of the duality theorem. 相似文献
8.
《European Journal of Operational Research》1997,101(1):130-139
We designed and implemented an algorithm to solve the continuos right hand side multiparametric Integer Linear Programming (ILP) problem, that is to solve a family of ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of nonparametric Mixed Integer Linear Programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems. 相似文献
9.
《European Journal of Operational Research》2001,132(3):594-602
This paper discusses two different approaches to the solution of difficult Goal Programming (GP) models. An integer Goal Programming (IGP) solver and some genetically driven multi-objective methods are developed. Specialised GP speed up techniques and analysis tools are employed in the design and development of the solution systems. A selection of linear integer models of small to medium size with an internal structure that makes solution difficult are considered. These problems are solved by both methods in order to assess their computational performance over several criteria and to compare the differences between them. From the results obtained in this research, it is observed that genetic algorithms (GA) have performed in general less efficiently than the Integer Goal Programming system for the sample of problems analysed. 相似文献
10.
《International Journal of Approximate Reasoning》2014,55(5):1269-1300
When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to the proposition a series of possibilistic criteria, namely: optimistic and pessimistic possibilistic qualitative criteria [7], possibilistic likely dominance [2], [9], binary possibilistic utility [11] and possibilistic Choquet integrals [24]. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria – when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good. 相似文献
11.
《European Journal of Operational Research》1999,114(3):569-579
We designed and implemented an algorithm to solve the continuous right-hand side parametric 0–1-Integer Linear Programming (ILP) problem, that is to solve a family of 0–1-ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of non-parametric 0–1-Mixed Integer Linear Programming (MILP) problems in order to obtain a complete parametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems. 相似文献
12.
Baardman Lennart Cristian Rares Perakis Georgia Singhvi Divya Skali Lami Omar Thayaparan Leann 《Mathematical Programming》2023,197(1):1-26
Mathematical Programming - In this paper, we present a new framework of bi-level unconstrained minimization for development of accelerated methods in Convex Programming. These methods use... 相似文献
13.
Mathematical Programming - This paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating... 相似文献
14.
Djangir A. Babayev 《Journal of Heuristics》1997,2(4):313-320
The goal of increasing computational efficiency is one of the fundamental challenges of both theoretical and applied research in mathematical modeling. The pursuit of this goal has lead to wide diversity of efforts to transform a specific mathematical problem into one that can be solved efficiently. Recent years have seen the emergence of highly efficient methods and software for solving Mixed Integer Programming Problems, such as those embodied in the packages CPLEX, MINTO, XPRESS-MP. The paper presents a method to develop a piece-wise linear approximation of an any desired accuracy to an arbitrary continuous function of two variables. The approximation generalizes the widely known model for approximating single variable functions, and significantly expands the set of nonlinear problems that can be efficiently solved by reducing them to Mixed Integer Programming Problems. By our development, any nonlinear programming problem, including non-convex ones, with an objective function (and/or constraints) that can be expressed as sums of component nonlinear functions of no more than two variables, can be efficiently approximated by a corresponding Mixed Integer Programming Problem. 相似文献
15.
Inmaculada EspejoAlfredo Marín Antonio M. Rodríguez-Chía 《European Journal of Operational Research》2012,219(1):49-58
The objective of this paper is to identify the most promising sets of closest assignment constraints in the literature of Discrete Location Theory, helping the authors in the field to model their problems when clients must be assigned to the closest plant inside an Integer Programming formulation. In particular, constraints leading to weak Linear Programming relaxations should be avoided if no other good property supports their use. We also propose a new set of constraints with good theoretical properties. 相似文献
16.
Mathematical Programming - The paper provides a connection between Commutative Algebra and Integer Programming and contains two parts. The first one is devoted to the asymptotic behavior of integer... 相似文献
17.
提出了一类特殊类型的数学规划模型并给出了一种新的分枝定界算法.这类数学模型尽管可以转化为0-1规划模型,但它相对于转化后的0-1规划模型:①决策意义明确,表达形式相对简单;②不需要引入参数M并在求解前确定其上界;③相对于求解转化后的0-1规划模型的分枝定界法,新分枝定界算法在最好情形下计算量最多为原算法的八分之一.作为本模型的一个应用,可以用来解决一些要么不实施要么有一定数量下限限制才可以实施的决策问题. 相似文献
18.
Mathematical Programming - In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing... 相似文献
19.
Mathematical Programming - This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral... 相似文献
20.
De Marchi Alberto Jia Xiaoxi Kanzow Christian Mehlitz Patrick 《Mathematical Programming》2023,201(1-2):863-896
Mathematical Programming - We investigate finite-dimensional constrained structured optimization problems, featuring composite objective functions and set-membership constraints. Offering an... 相似文献