CAREER: Applications of Convex Programming in Combinatorial Optimization: A Mathematical, Algorithmic and Computational Study

研究了半定规划问题，包括数值稳定内点算法的实现，可行集的数学性质，以及半定规划在组合优化中的应用。首先，实现了两个版本的原始-对偶内点SDP算法。一个版本是MATLAB的，旨在作为一个易于使用和更改的软件，用于中小型问题。另一种实现是FORTRAN 90，用于高性能并行和矢量/流水线机器，旨在解决大规模问题。此外，还研究了主动集方法在SDP中的可行性。下一步研究了SDP在一般0-1整数规划问题中的应用。分支和定界SDP技术的可行性正在研究中，这些技术在每个阶段解决一个SDP问题，但可能需要更少的分支。如果发现这种方法是可行的，那么将开发通用程序。在理论研究中，研究了SDP的以下应用：图的Lovasz数的并行计算复杂性，最小顶点覆盖问题的近似算法，一般匹配问题的应用，以及仿射变换下SDP可行集的多面性。研究了线性和半定规划的原对偶方法与二次约束二次规划问题的联系。此外，正在研究这些锥体，其相关的优化问题导致双线性形式的互补关系；规划，二次约束二次规划和SDP是这类问题的例子。在教学计划方面，计划积极参与帮助四川理工大学建立硕士项目。研究生院的半定规划和计算生物学课程，以及一门旨在调查各种可用于优化问题的软件的课程正在开发中。期望在计算机科学、数学和统计学的附属部门进行本科水平的课程教学。此外，一本关于SDP的教科书正在编写中。

The semidefinite programming problem (SDP), including implementation of numerically stable interior point algorithms, mathematical properties of the feasible sets, and in particular applications of SDP in combinatorial optimization are being investigated. First, two versions of the primal-dual interior point SDP algorithm are being implemented. One version is in MATLAB and is intended as an easy to use and change software for small to medium size problems. Another implementation is in FORTRAN 90 and is intended for high performance parallel and vector/pipelined machines and is meant to solve large scale problems. In addition feasibility of active set methods for SDP is being investigated. Next applications of SDP in general 0-1 integer programming problems are being studied. The feasibility of branch and bound SDP techniques which solve an SDP problem at each stage but may require far fewer branchings overall is being investigated. If such an approach is found to be practical, general purpose programs will be developed. In theoretical investigations, the following applications of SDP are being studied: parallel computational complexity of the Lovasz number of graphs, approximation algorithms for the minimum vertex cover problem, applications to the general matching problem, and polyhedrality of the feasible sets of SDPs under affine transformations. The connection of primal--dual method of linear and semidefinite programs to the problem of quadratically constrained quadratic programming is being investigated. In addition, those cones are being investiagted whose associated optimization problem leads to complementarity relations that are bilinear forms; programming, quadratically constrained quadratic programming and SDP are examples of such problems. For teaching plans, active participation in helping RUTCOR establish a masters program is planned. Courses in semidefinite programming and in computational biology in graduate school, and a course designed to survey various software available for optimization problems are being developed. At the undergraduate level teaching of courses in the affiliated departments of computer science, mathematics and statistics is expected. Also a textbook on SDP is in preparation.