共查询到19条相似文献,搜索用时 93 毫秒
1.
一类特殊二维0-1规划的广义指派模型求解 总被引:2,自引:2,他引:0
二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用. 相似文献
2.
3.
王延臣 《数学的实践与认识》1991,(4)
整数规划问题至今尚无一个统一有效的解决方法,本文提出一个24小时连续工作系统人员配备的数学模型,并对这个特殊的整数规划问题给出一个解法,得到了简洁、圆满的结果. 相似文献
4.
5.
本文给出了一类新的求解箱约束全局整数规划问题的填充函数,并讨论了其填充性质.基于提出的填充函数,设计了一个求解带等式约束、不等式约束、及箱约束的全局整数规划问题的算法.初步的数值试验结果表明提出的算法是可行的。 相似文献
6.
7.
8.
在使用割平面法求解整数规划时,寻找Gomory约束是其中最为关键的一步.一般地,选取非整数解变量中分数部分最大的一个基变量,写下相应行的约束.将这个约束等式中的系数进行整数和非负真分数的分解,再加上整数条件进行逼迫,得到一个小于等于0的不等式.从这个小于等于0的不等式出发,有五种方法构造Gomory约束.通过具体例子,详细讲解这五种方法,并进行比较,从而更加深刻地理解Gomory约束的构造,在以后的解题中可以灵活运用. 相似文献
9.
基于驱动-响应法,根据Lyapunov稳定性理论和分数阶微积分的相关理论研究了一类整数阶,分数阶单摆系统的混沌同步问题,针对无阻尼和有阻尼两种情况给出了控制律的设计,并给出了严格的数学证明和推理过程,研究表明一定条件下,选取适当的控制律单摆系统的主从系统是混沌同步的,最后数值仿真说明方法有效. 相似文献
10.
11.
Given a valid inequality for the mixed integer infinite group relaxation, a composite lifting approach that combines sequential lifting and the use of a fill-in function is proposed that can be used to strengthen this inequality. Properties of this composite lifting such as bounds on the solution of the lifting problem and some necessary conditions for the lifted inequality to be minimal for the mixed integer infinite group relaxation are presented. Finally, this composite lifting approach is used to generate a strengthened version of the two-row mixing inequality that provides a new class of extreme inequalities for the two-row mixed integer infinite group relaxation. 相似文献
12.
Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions
of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming
and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of
lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities
for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the
computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative
orthants, conic lifting reduces to the lifting for linear integer programming as one may expect. 相似文献
13.
Alper Atamtürk 《Mathematical Programming》2003,98(1-3):145-175
We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57 相似文献
14.
In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs.
The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier
results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting
in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent
lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong
cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear
knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained
using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the
problem.
相似文献
15.
Matthias Jach Matthias Köppe Robert Weismantel 《4OR: A Quarterly Journal of Operations Research》2006,4(1):29-46
This paper is based on the study of the set of nondecomposable integer solutions in a Gomory corner polyhedron, which was
recently used in a reformulation method for integer linear programs. In this paper, we present an algorithm for efficiently
computing this set. We precompute a database of nondecomposable solutions for cyclic groups up to order 52. As a second application
of this database, we introduce an algorithm for computing nontrivial simultaneous lifting coefficients. The lifting coefficients
are exact for a discrete relaxation of the integer program that consists of a group relaxation plus bound constraints.
Received: November 2004 / Revised version: June 2005
AMS classification:
90C10, 90C57 相似文献
16.
A linear programming-based optimization algorithm for solving nonlinear programming problems 总被引:1,自引:0,他引:1
In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems. 相似文献
17.
We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semi-assignment problem to hub location problems with some computational experiences. 相似文献
18.
Recently Andersen et al. [1], Borozan and Cornuéjols [6] and Cornuéjols and Margot [9] have characterized the extreme valid inequalities of a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible non-negative integer variables (giving the two row mixed-integer infinite-group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We show that there exists a unique lifting function that yields extreme inequalities when starting from a maximal lattice-free triangle with multiple integer points in the relative interior of one of its sides, or a maximal lattice-free triangle with integral vertices and one integer point in the relative interior of each side. In the other cases (maximal lattice-free triangles with one integer point in the relative interior of each side and non-integral vertices, and maximal lattice-free quadrilaterals), non-unique lifting functions may yield distinct extreme inequalities. For the latter family of triangles, we present sufficient conditions to yield an extreme inequality for the two row mixed-integer infinite-group problem. 相似文献
19.
Andrzej Ruszczyński 《Mathematical Programming》2002,93(2):195-215
We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions.
They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties
of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities
for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are
used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with
a numerical example.
Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002
Key words. stochastic programming – integer programming – valid inequalities 相似文献