By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler … Read more
We prove that cutting-plane proofs which use split cuts have exponential length in the worst case. Split cuts, defined by Cook, Kannan, Schrijver (1993), are known to be equivalent to a number of other classes of cuts, namely mixed-integer rounding (MIR) cuts, Gomory mixed-integer cuts, and disjunctive cuts. Our result thus implies the exponential worst-case … Read more
Nonnegative tensor factorization (NTF) is a technique for computing a parts-based representation of high-dimensional data. NTF excels at exposing latent structures in datasets, and at finding good low-rank approximations to the data. We describe an approach for computing the NTF of a dataset that relies only on iterative linear-algebra techniques and that is comparable in … Read more
Adverse drug reactions (ADRs) are estimated to be one of the leading causes of death. Many national and international agencies have set up databases of ADR reports for the express purpose of determining the relationship between drugs and adverse reactions that they cause. We formulate the drug-reaction relationship problem as a continuous optimization problem and … Read more
This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose … Read more
We present computational approaches for optimizing beam angles and fluence maps in Intensity Modulated Radiation Therapy (IMRT) planning. We assume that the number of angles to be used for the treatment is given by the treatment planner. A mixed integer programming (MIP) model and a linear programming (LP) model are used to find an optimal … Read more
We consider the effectiveness of a lookahead branching method for the selection of branching variable in branch-and-bound method for mixed integer programming. Specifically, we ask the following question: by taking into account the impact of the current branching decision on the bounds of the child nodes two levels deeper than the current node, can better … Read more
In this work we present a family of variable metric interior proximal methods for solving optimization problems under nonnegativity constraints. We define two algorithms, in the inexact and exact forms. The kernels are metrics generated by diagonal matrices in each iteration and the regularization parameters are conveniently chosen to force the iterates to be interior … Read more
We study the second-order feasibility cone F = { y : \| My \| \le g^Ty } for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix M^TM – gg^T. This representation is used to efficiently solve the problem of projecting an … Read more
The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width t of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/t^2, see Rosenblatt 1962. Dunagan and … Read more