Generalized Branch-and-Cut Method for Mixed Integer Programming
Generalized Branch-and-Cut Method for Mixed Integer Programming
批准号:
0200151
负责人:
Sanjay Mehrotra
金额:
$28.72万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2002
资助国家:
美国
项目状态:
已结题
起止时间:
2002-09-01 至 2006-08-31
中文摘要
含有一般整数变量和非线性约束的模型很难求解。 已经有一些,但有限的进展,以解决这种类型的大规模模型。 实际测试问题的计算结果表明,最佳目标值和从放松的问题的解决方案在根节点的界限之间的差距是显着更大的线性情况下得到的界限相比,枚举树的大小爆炸迅速。 为了克服在解决这种类型的大规模问题的困难,在几个方向的进步是必要的。 需要进一步开发生成良好切割平面的方法,以及需要开发更先进的快速识别可行解决方案的方法。 然而,我们认为,最根本的进步可能来自于分支切割方法中先进分支方案的发展。 标准分支方案每次在单个变量析取上进行分支。 Lenstra表明,通过分支一般超平面,我们可以解决一个混合整数线性规划问题的多项式时间。 Lenstra算法的实用价值有限。 这是因为在他的算法中找到分支超平面的计算成本非常高。 然而,有可能找到“质量好”但计算成本不高的分支平面。 本研究将集中于此问题以及解决非线性混合整数规划的相关问题。一些工程和管理问题导致模型是非线性的,可能是随机的,整数规划。 这些问题领域包括库存、生产和化学工艺规划、布局、位置、物流和财务优化。 例如,当使用二阶矩对不确定性进行建模时,自然会出现非线性。 该提案要求资金支持我们正在进行的研究,以寻找解决此类模型的有效技术。 非线性整数规划问题的通用求解方法的发展将产生广泛的影响,因为它将有助于解决来自许多不同领域的此类问题。
英文摘要
Models involving general integer variables with nonlinear constraints are very hard to solve. There has been some, but limited progress towards solving large scale models of this type. Computational results on practical test problems suggest that the gap between the optimum objective value and a bound from the solution of the relaxed problem at the root node is significantly larger when compared with bounds obtained in the linear case, and the size of the enumeration tree explodes quickly. To overcome the difficulties in solving large scale problems of this type, advances in several directions are needed. Methods for generating good cutting planes need to be developed further, as well as more advanced heuristics for identifying a feasible solution quickly need to be developed. However, we think that the most fundamental advance may come from the development of advanced branching schemes in a branch-and-cut method. The standard branching schemes branch on a single variable disjunction at a time. Lenstra showed that by branching on general hyperplanes we can solve a mixed integer linear programming problem in polynomial time. Lenstra's algorithm has found limited practical value. This is because the computational cost of finding the branching hyperplane in his algorithm is very high. However, there is a possibility for finding branching planes that are ``good quality'' but computationally not as expensive. This research will focus on this problem as well as related issues towards solving nonlinear mixed integer programs.Several engineering and management problems lead to models that are nonlinear, possibly stochastic, integer programs. These problem areas include inventory, production and chemical process planning, layout, location, logistics and financial optimization. For example, nonlinearity arises naturally while modeling uncertainty using the second moment. This proposal request funds to support our ongoing research for finding efficient techniques for solving such models. The development of general purpose solution methodology for solving nonlinear integer programming problem will have a wide ranging impact, as it would facilitate solving such problems arising from many different areas.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: AMPS: Robust Failure Probability Minimization for Grid Operational Planning with Non-Gaussian Uncertainties
-
批准号:2229410
-
项目类别:Standard Grant
-
资助金额:$28.4万
-
财政年份:2022
-
负责人:Sanjay Mehrotra
-
依托单位:
Equitable and Efficient Resource Allocation using Stochastic Fractional Optimization
-
批准号:1763035
-
项目类别:Standard Grant
-
资助金额:$37.81万
-
财政年份:2018
-
负责人:Sanjay Mehrotra
-
依托单位:
RAPID: Addressing Geographic Disparities in the National Organ Transplant Network
-
批准号:1743886
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2017
-
负责人:Sanjay Mehrotra
-
依托单位:
I-Corps: Clinical Workforce Schedule Optimization Technology
-
批准号:1764312
-
项目类别:Standard Grant
-
资助金额:$5.0万
-
财政年份:2017
-
负责人:Sanjay Mehrotra
-
依托单位:
Collaborative Research: Analysis and Solution Methods for Function Robust Optimization Models
-
批准号:1361942
-
项目类别:Standard Grant
-
资助金额:$23.54万
-
财政年份:2014
-
负责人:Sanjay Mehrotra
-
依托单位:
Managing Downstream Patient Flow Processes Using Improved Coordination and Staffing
-
批准号:1335585
-
项目类别:Standard Grant
-
资助金额:$14.0万
-
财政年份:2013
-
负责人:Sanjay Mehrotra
-
依托单位:
Models and Algorithms for Risk Adjusted Optimization with Robust Utilities
-
批准号:1131386
-
项目类别:Standard Grant
-
资助金额:$20.0万
-
财政年份:2011
-
负责人:Sanjay Mehrotra
-
依托单位:
Addressing Geographical Disparities in Transplant Organ Accessibility Across United States
-
批准号:1131568
-
项目类别:Standard Grant
-
资助金额:$31.5万
-
财政年份:2011
-
负责人:Sanjay Mehrotra
-
依托单位:
Distribution and Moment-Robust Optimization Models and Algorithms
-
批准号:1100868
-
项目类别:Standard Grant
-
资助金额:$20.0万
-
财政年份:2011
-
负责人:Sanjay Mehrotra
-
依托单位:
Multi-objective Robust Stochastic Planning and Scheduling of Healthcare Service Providers
-
批准号:0928936
-
项目类别:Standard Grant
-
资助金额:$45.5万
-
财政年份:2009
-
负责人:Sanjay Mehrotra
-
依托单位:
Methods for Solving Mixed Integer Programs Using Adjoint Lattices
-
批准号:0522765
-
项目类别:Continuing Grant
-
资助金额:$36.06万
-
财政年份:2005
-
负责人:Sanjay Mehrotra
-
依托单位:
Methods for Solving Linear and Nonlinear Mixed Integer Programs
-
批准号:9908038
-
项目类别:Continuing Grant
-
资助金额:$20.32万
-
财政年份:1999
-
负责人:Sanjay Mehrotra
-
依托单位:
Interior Point Methods in Optimization
-
批准号:9019469
-
项目类别:Continuing Grant
-
资助金额:$12.0万
-
财政年份:1991
-
负责人:Sanjay Mehrotra
-
依托单位:
Research Initiation: Interior Point Algorithms for Linear and Convex Programming
-
批准号:8810107
-
项目类别:Standard Grant
-
资助金额:$6.64万
-
财政年份:1988
-
负责人:Sanjay Mehrotra
-
依托单位:
国内基金
海外基金
基于ladder-branch HCR和Fe3O4-QCS-PEI-Cu的血小板细菌检测与灭活平台及其响应机制研究
-
批准号:82400274
-
项目类别:青年科学基金项目
-
资助金额:30.00万元
-
批准年份:2024
-
负责人:任冬霞
-
依托单位: