Jon Lee The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more
Motivated by Bland’s linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using “discrete steepest-descent augmentations” (i.e., directions with the best … Read more
This is the “front matter” of a new open-source book on Linear Optimization. The book and associated Matlab/AMPL/Mathematica programs are freely available from: https://sites.google.com/site/jonleewebpage/home/publications/#book CitationJon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017.ArticleDownload View PDF
Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an … Read more
Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a non-simplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out … Read more
Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A {\em probing} algorithm is a bound-tightening procedure that explores the consequences of restricting a variable to a subinterval with the goal of tightening its bounds. We propose a variant of probing where exploration is based on iteratively applying a … Read more
CitationIBM Research Report RC24999ArticleDownload View PDF
We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdos-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $\rho n$-best solution … Read more
Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is … Read more
Global optimization algorithms, e.g., spatial branch-and-bound approaches like those implemented in codes such as BARON and COUENNE, have had substantial success in tackling complicated, but generally small scale, non-convex MINLPs (i.e., mixed-integer nonlinear programs having non-convex continuous relaxations). Because they are aimed at a rather general class of problems, the possibility remains that larger instances … Read more