Stanford University. Systems Optimization Laboratory

G. Dobson

We give a worst case analysis for two greedy heuristics for the integer programming problem minimize cx, Ax> or = b, O

Worst case analysis of greedy heuristics for integer programming with non-negative data

A. N. Rosenberg

Numerical Solution of Systems of Simultaneous Polynomial Equations

Frederick S. Hillier

Robert M. Saltzman

Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. Our heuristic approach is based upon the idea that a feasible 1-ceiling point found relatively near the optimal solution for the LP-relaxation is apt to have a high (possibly even optimal) objective function value. Having applied this Heuristic Ceiling Point Algorithm to 48 test problems taken from literature, it appears that searching for such 1-ceiling points usually does provide a very good solution with a moderate amount of computational effort."

Heuristic Ceiling Point Algorithm for General Integer Linear Programming

User's Guide for SOL/QPSOL: a FORTRAN Package for Quadratec Programming

Thomas Elken

This report gives programmers information useful for the utilization and modification of BCA and HRA, two programs for computing economic equilibria. The BCA implements the bilinear complementarity algorithm and HRA a homotopy retraction algorithm. The report describes the subroutines and variables used as well as the usual documentation: input format, sample input and output for two problems, and program listings. (Author).

BCA and HRA: Two Programs for Computing Economic Equilibria

This paper discusses problems that arose in calendaring cases for an appellate court. The first problem is to distribute cases among panels of judges so as to equalize work loads. We give a worst case analysis of a heuristic for this NP-complete problem. For a given distribution denote by z the heaviest work load. We wish to minimize z. The ratio of the heuristic value z-bar to that of the true optimum z* is shown to be z-bar/z*

Exact and approximation algorithms for a scheduling problem

Hui Hu

Upper bounds for finding an [epsilon]-optimal solution and for the distance between an [epsilon]-optimal solution and an optimal solution are given. (4) Applications of the above algorithm to convex programming. First, a certain semi-infinite linear program is solved by this algorithm so as to obtain a feasible solution of a convex program. Then, another semi-infinite linear program is solved by this algorithm so as to obtain an optimal solution of the convex program. In particular, it is shown that for a strongly consistent convex program this algorithm can find a feasible solution after a finite number of iterations."

Stanford University. Systems Optimization Laboratory

About

Books

Join the club