Computational Optimization Laboratory

Director: Yinyu Ye

The Computational Optimization Laboratory is part of the University of Iowa's College of Business Administration. Its purpose is to design, analyze, and implement large scale optimization algorithms. Particular emphasis is placed on interior point algorithms for linear and positive definite programming. Software can be downloaded for research, free of charge, from this page subject to copyright laws.

Other current members of the Computational Optimization Laboratory are:

Kurt Anstreicher, Professor of Management Science
Ken Kortanek, John F. Murray Research Professor of Management Science

Steven Benson, Postdoctor at Argonne National Lab.
Cris Choi, Graduate Assistant.
Jiawei Zhang, Graduate Assistant.
Qiaomin Han, Visiting Scholar.

Working papers available:

The new working paper: A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem is available. Click here for the Postscript file. (Posted 1/23/02. This work is supported by NSF grants DMI-9908077.)

The new working paper: Improved Analyses of Facility Location Algorithms is available. Click here for the Postscript file. (Posted 11/5/01. This work is supported by NSF grants DMI-9908077.)

The new working paper: An Approximation Algorithm for the Two-Parallel Machines Scheduling Problem with Capacity Constraints is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: Improved Approximation for Max Set Splitting and Max NAE SAT is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: Blind Channel Equalization and Approximation Algorithms is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: Solving Sparse Semidefinite Programs Using the Dual Scaling Algorithm with an Iterative Solver is available. Click here for the gzipped Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: On Approximation of Max-Vertex-Cover is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: An Improved Rounding Method and Semidefinite Programming Relaxation for Graph Partition is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: .586 Approximation of Dense-n/2-Subgraph and .602 Approximation of the Complement of Min-Bisection is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The new working paper: Approximating Maximum Stable Set and Minimum Graph Coloring Problems with the Positive Semidefinite Relaxation is available. Click here for the Postscript file.

The new working paper: Application of Semidefinite Programming to Circuit Partitioning is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077 and DMS-9703490.)

The paper: Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization is available. Click here for the Postscript file.

The paper: Solving large-scale sparse semidefinite programs for combinatorial optimization is available. Click here for the gzipped Postscript or zipped Postscript .

The working paper: A .699-Approximation Algorithm for Max-Bisection is available. Click here for the Postscript file. (This work is supported by NSF grants DMI-9908077, DBI-9730053, and DMS-9703490.)

Software packages available to the public include:

The program, DSDP4.2, solves general semidefinite programs, and is a implementation of the dual scaling algorithm. The source code, written in C, with User-Guide (postscript file) and sample problems, can be downloaded by clicking Benson's Homepage (updated on February 8, 2002).

The program, COPL_DSDP, solves most semidefinite programs arisen in combinatorial and global optimization, including max-cut or min-cut, graph-partition, max-cover, stable-set and nonconvex-qp. COPL_DSDP is a generalization and enhancement of COPL_SDP. It reads the input data from a MPS-like format. The program is a implementation of the dual scaling algorithm for mixed linear and semidefinite programming problems with rank-one matrix constraints, and of several randomized (or heuristic) rank reduction methods. It is proven to be particularly effective in solving large scale problems with sparse input matrices. The source code, written in C, with User-Guide (postscript file) and sample problems (last updated April 27, 1999), can be downloaded by clicking copldsdp.zip or copldsdp.tar.gz (use "tar -xzf" to untar it).

A linear programming solver COPL_LP (PC DOS, HP and Linux versions). This package solve linear programs with sparse data. It has options to return an optimal basic solution and to detect infeasibility or unboundedness. The input data files are in MPS format. The executable codes, with User-Guide (postscript file) and sample problems (last updated May 21, 98), can be downloaded by clicking Dos version , or HP version , or Linux version (last updated March/9/2000).

An experimental convex quadratic programming solver, COPL_QP, is available. This package tries to solve linearly constrained convex quadratic programs. The source code, written in C, with User-Guide (postscript file) and sample problems (last updated Jan 15, 2002; thanks to Alexandre Belloni for modifying qpproc.c), can be downloaded by clicking coplqp.zip or coplqp.tar.gz .

A linearly constrained convex programming solver, COPL_LC, is available. This package can solve any linearly constrained convex program with known gradient and hessian functions. The source code, written in Fortran, with User-Guide (postscript file) and sample problems, can be downloaded by clicking copllc.zip or copllc.tar.gz .

A geometric programming solver, COPL_GP, is available. The executable code (Linux or HP), with User-Guide (postscript file) and sample problems (last updated May 10, 2000), can be downloaded by clicking coplgp.zip (Linux) or coplgp-hp.zip .

The program, COPL_SDP, solves Max-Cut, Equal-Cut, Unequal-Cut, S-T Max-Cut, and Box Constrained Quadratic Programming Problems. This program is an implementation of the dual scaling algorithm for SDP and randomized (or heuristic) rank reduction, and proven to be particularly effective in large scale problems with sparse input matrices. The source code, written in C, with User-Guide (postscript file) and sample problems (last updated Feb 16, 99), can be downloaded by clicking coplsdp.zip or coplsdp.tar.gz. More test problem can be found in Gset .

The selected Matlab optimization programs, LP, LCP, Indefinite QP and Nonlinear Programming, are available. Click here for the Matlab File .

*****************************************************************
COPYRIGHT NOTIFICATION
*****************************************************************
(C) COPYRIGHT 1997, 1998 UNIVERSITY OF IOWA
*****************************************************************
These software disclose material protectable under copyright laws of the United States. Permission is hereby granted to use, reproduce, prepare derivative works, and redistribute to others at no charge, provided that the original copyright notice, Government license and disclaimer are retained and any changes are clearly documented; however, any entity desiring permission to incorporate this software or a work based on the software into a product for sale must contact Yinyu Ye at the Department of Management Science, The University of Iowa.