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
In this paper we address the problem of identifying the most likely infection pattern responsible for the spread of a disease in a network. In particular, we focus on the scenario where limited information (i.e. infection reports) is available during an ongoing outbreak. For this problem we propose a maximum likelihood model and present an … Read more
We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm … Read more
We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead an edge weighted graph G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the … Read more
We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) … Read more
Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and … Read more
We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a … Read more
We introduce computable a-priori and a-posteriori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the LP relaxation of a mixed integer linear optimization problem. Treating the mesh size of integer vectors as a parameter allows us to study the effect of different `granularities’ in the … Read more
In this paper we introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches … Read more
In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more