A classical theorem in Combinatorial Optimization proves the existence of fully polynomial- time approximation schemes for the knapsack problem. In a recent paper, Van Vyve and Wolsey ask whether for each 0 < epsilon ≤ 1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables and/or 1/epsilon ... Read more
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
Recently Cambini and Carosi described a characterization of pseudolinearity of quadratic fractional functions. A reformulation of their result was given by Rapcsák. Using this reformulation, in this paper we describe an alternative proof of the Cambini–Carosi Theorem. Our proof is shorter than the proof given by Cambini–Carosi and less involved than the proof given by … Read more
In the seminal work [1] L. Lovász introduced the concept of an orthonormal representation of a graph, and also a related value, now popularly known as the Lováasz number of the graph. One of the remarkable properties of the Lovász number is that it lies sandwiched between the stability number and the complementer chromatic number. … 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
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
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
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