课题基金 / 基金详情

Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization

Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization
混合整数和组合优化中的多面体和图论方法
批准号:
0352885
负责人:
Egon Balas
金额:
$42.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2004
资助国家:
美国
项目状态:
已结题
起止时间:
2004-09-01 至 2007-08-31

项目摘要

项目成果

Egon Balas的其他基金

相似基金

相关文献

中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
This project addresses theoretical and computational aspects of integer programming and combinatorial optimization, using the tools of linear algebra and graph theory. It is focused on the approach called lift-and-project, developed in the nineties and recently incorporated into state-of-the-art software. Lift-and-project cuts are generated from a disjunction involving a combination of inequalities. One topic for investigation is how to simultaneously optimize the weighted combination of inequalities used in the disjunction underlying the cut, and the choice of multipliers in the monoidal strengthening of the resulting cut. Another topic in the same direction offers to improve the performance of Gomory cuts for mixed integer linear programs, by combining inequalities in well-defined ways. Other topics, aimed at understanding the structure of Lehman matrices and almost totally unimodular matrices, or an algorithm for finding an odd hole in a graph, are related to two important classes of problems: set packing and set covering. A better understanding of these classes of problems is a central aspect of the very active research currently occurring in the field of combinatorial optimization.To the extent that this project will be successful, it will advance the state of the art in mixed integer and combinatorial optimization, and thereby enhance our problem solving ability in a broad range of activities, from industrial production to logistics and telecommunications. The tools created here may be as useful in improving homeland security, as they may be instrumental in reinforcing our technological leadership. From the late fifties to the early nineties, integer programming was a way to formulate almost any optimization problem, yet the available computer codes could only handle toy problems of minuscule size. During the last decade the state of the art has radically changed, and today well over half of the integer programs formulated can also be solved. This project is expected to significantly accelerate this change.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Mixed Integer Optimization: New Cut Generation Paradigms
  • 批准号:
    1560828
  • 项目类别:
    Standard Grant
  • 资助金额:
    $50.0万
  • 财政年份:
    2016
  • 负责人:
    Egon Balas
  • 依托单位:
(Mixed) Integer and Combinatorial Optimization: New Convexification Techniques
  • 批准号:
    1263239
  • 项目类别:
    Standard Grant
  • 资助金额:
    $47.5万
  • 财政年份:
    2013
  • 负责人:
    Egon Balas
  • 依托单位:
Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows
  • 批准号:
    1024554
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.09万
  • 财政年份:
    2010
  • 负责人:
    Egon Balas
  • 依托单位:
Mixed Integer and Combinatorial Optimization: Lift-and-Project and Polyhedral Combinatorics
  • 批准号:
    0653419
  • 项目类别:
    Standard Grant
  • 资助金额:
    $37.96万
  • 财政年份:
    2007
  • 负责人:
    Egon Balas
  • 依托单位:
国内基金
海外基金
基于Graph-PINN的层结稳定度参数化建模与沙尘跨介质耦合传输模拟研
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2025
  • 负责人:
    梅奥
  • 依托单位:
平面三角剖分flip graph的强凸性研究
  • 批准号:
    12301432
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    30.00万元
  • 批准年份:
    2023
  • 负责人:
    王子丽
  • 依托单位:
基于graph的多对比度磁共振图像重建方法
  • 批准号:
    61901188
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    24.5万元
  • 批准年份:
    2019
  • 负责人:
    赖宗英
  • 依托单位:
基于de bruijn graph梳理的宏基因组拼接算法开发
  • 批准号:
    61771009
  • 项目类别:
    面上项目
  • 资助金额:
    50.0万元
  • 批准年份:
    2017
  • 负责人:
    李国君
  • 依托单位: