We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima can be computed quickly; the corresponding optimization problems are equivalent to trust-region subproblems. We present several ideas that allow to accelerate the solution of the continuous relaxation within a branch-and-bound scheme and examine the performance of the overall algorithm by computational experiments.

We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results.

The integer quadratic programming problem is formulated as follows. Let $n$ and $m$ be positive integers, $A$ an $m \times n$-matrix with integral coefficients, $b \in \Z^m$, and $f \st \R^n \to \R$ a quadratic polynomial with integral coefficients. The question is to find a vector $\bar x \in \Z^n$ satisfying the system of $m$ inequalities $Ax \le b$ that minimizes the function $f$. It is shown that the integer quadratic programming problem with $n=2$ is polynomially solvable.

We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably de?ned matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2-eps} )-approximations for CLIQUE require linear programs of size 2^{n^{\Omega(eps)}}. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem.) Moreover, we establish a similar result for approximations of semide?nite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov’s rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjointness matrix. Joint work with Gábor Braun, Sebastian Pokutta and David Steurer.

Given a finite list of convex bodies in Euclidean space, a packing is a union of nonoverlapping congruent copies of the bodies given. A natural question concerning packings is how dense they can be made, that is, what is the maximum fraction of space that can be covered by a packing of some given bodies? I wil show how harmonic analysis and semidefinite programming can be used to give upper bounds for the maximum density of a packing of bodies. In particular I will discuss the case of binary sphere packings, when one considers packings of spheres of two different sizes, and show how the computer can be used to find upper bounds for the densities of such packings. This is joint work with David de Laat and Frank Vallentin. Paper on arXiv:1206.2608.

Semidefinite relaxations proved to be very successful for max-cut. Tightening the basic relaxation for max-cut, underlying the Goemans-Williamson hyperplane rounding procedure, can be done very efficient by adding the so-called triangle-inequalities. Based on this tightened relaxation we present a further strengthening: We identify sub-matrices of the optimal matrix $X$ and require thesemsub-matrices to be in the corresponding cut polytope $CUT(K_r)$. The dimension $r$ of the sub-matrices is chosen small enough (say $r=5$ or $r=6$), so that the resulting SDP is still fast to compute. First computational results demonstrate that the bound improves significantly after a few rounds of adding such sub-matrix constraints, while keeping computation times reasonable.

We consider the classical 0-1 knapsack problem and add binary constraints for pairs of items. These can be either conflict constraints stating that certain pairs of items cannot be simultaneously contained in a feasible solution, or forcing constraints requiring that at least one of the two items of each given pair must be included in the knapsack. These constraints can be represented by a conflict (or forcing) graph where each item corresponds to a vertex and an edge in the graph corresponds to a conflicting (enforced) pair of items. Note that this problem can also be seen as a weighted independent set problem with an additional budget constraint. In this talk we will concentrate on the identification of special graph classes as conflict graphs which permit (Fully) Polynomial Approximations Schemes ((F)PTASs). After showing briefly that chordal graphs and graphs of bounded treewidth allow an FPTAS, we present a PTAS for planar conflict graphs based on the method by Baker. In contrast to this positive approximability result, the knapsack problem with a planar forcing graph is inapproximable. Finally, we also consider clique and modular decompositions of the conflict graph. For a number of graph classes defined by the exclusion of certain induced subgraphs we can show structural results that allow the construction of dynamic programming schemes leading to FPTASs. joint work with Joachim Schauer

We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into k sets of equal size. This is called the k-BALANCED PARTITIONING problem. The problem is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes. We show that the k-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate within n^c, for any constant c < 1. If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1 + ?, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log^{1.5}(n)/?^2) [Andreev and Racke TCS 2006] to O(log n). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of ?.

The timetable variant of a combinatorial optimization (CO) problem is defined as follows. The input specifies an instance of the CO problem comprising a set system (A,F) with ground set A and a collection F of feasible sets, a linear cost function w, a positive integer T and positive integers t_a <= T for every ground set element a. The goal is to find T feasible sets X_1,...,X_T of maximal total cost that satisfy the following duration property. For every ground set element a, the set L_a subset {1,...,T} of indices j such that a is in X_j is a disjoint union of intervals of length t_a. The class of timetable variant of CO problems corresponding to independence systems is a rich class of problems containing many Knapsack, scheduling and packing problems. For p ~= 1.691 we present a polynomial pq-approximation algorithm for this class of problems whenever the static maximization problem admits a polynomial q-approximation algorithm. For the more general timetable counterpart that also provides upper bounds on the cardinality of L_a for every ground set element a, we show polynomial constant factor approximation algorithms for the case that underlying set system is a Matroid. A combination of combinatorial and LP-based techniques is employed both in the algorithms and in their analysis.

We study the relationship between the approximation factor for the Set-Cover problem and the parameters $\Delta$ : the maximum cardinality of any subset, and $k$ : the maximum number of subsets containing any element of the ground set. We show an LP rounding based approximation of $(k-1)(1-e^{-\frac{\ln \Delta}{k-1}}) +1$, which is substantially better than the classical algorithms in the range $k \approx \ln \Delta$, and also improves on related previous works [Krivelevich, Okun]. For the interesting case when $k = \theta(\log \Delta)$ we also exhibit an integrality gap which essentially matches our approximation algorithm. We also prove a hardness of approximation factor of $\Omega\left(\frac{\log \Delta}{(\log\log \Delta)^2}\right)$ when $k = \theta(\log \Delta)$. This is the first study of the hardness factor specifically for this range of $k$ and $\Delta$, and improves on the only other such result implicitly proved in [Khot, Saket].

We discuss optimality-based domain reductions for Global Optimization problems both from the theoretical and from the computational point of view. When applying an optimality-based domain reduction we can easily define a lower limit for the reduction which can be attained, but we can hardly guarantee that such limit is reached. Here, we theoretically prove that, for a nontrivial class of problems, appropriate strategies exist that are always able to reach this lower limit. On the other hand, we will also show that the same strategies lose this property as soon as we slightly enlarge the class of problems. Finally, we present some computational experiments with a standard branch-and-bound approach applied to Linear Multiplicative Programming problems, to establish a good trade off between the quality of the domain reduction (the higher the quality, the lower the number of nodes in the tree), and the computational cost of the domain reduction (thus, the effort per node). (joint work with Alberto Caprara and Marco Locatelli)

In this paper, we propose a new method to compute lower bounds for Curriculum-based Course Timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones).

Bilevel programming research is motivated by the possibility of modelling a wide range of real world problems with an hierarchical structure. In this presentation and using Alberto Caprara's words, a natural, clean and mathematical challenging bilevel knapsack model is considered. The model describes an interdiction situation where two decision makers, called leader and follower, have a knapsack of their own; the follower can only choose from those items not packed by the leader; the leader aim is to minimize the maximum profit of the follower. Along with other bilevel knapsack variants, our complexity results will be stated indicating its computational difficulty. The main focus of the presentation will be in the algorithmic approach developed which is a novel viable way to solve it. Computational results will be presented supporting its efficiency in the instances treated in the literature and rising benchmarks. Comments about generalizing our method to interdiction problems will be provided.

We study the relative performances of three existing approaches to solve the minimum-cost linear MultiCommodity Flow Problem (MCFP). The first approach is solving the LP corresponding to the natural node-arc formulation with state-of-the-art, general-purpose commercial software. The second is to take advantage of the block-diagonal structure with complicating constraints of the LP to develop Dantzig-Wolfe decomposition/column generation approaches. The third is a decomposition-based pricing procedure, proposed by Mamer and McBride, in which the same subproblems of the D-W decomposition are used to identify new columns in a reduced master problem that has the same structure of the node-arc formulation. With a particular focus on degeneracy and instability issues of the column generation, different classes of MCFP instances are solved in order to study the connections between the structure of a specific instance and the performances of the most common solving approaches for this class of problems. This may be useful in choosing the correct approach when a particular MCFP shall be solved, as well as improving the effectiveness of the approaches themselves.

Robust optimisation is a well established concept to deal with uncertainty. In particular, recovery-robust models are suitable for real-world contexts, where a certain amount of recovery – although limited – is often available. In this paper we describe a general framework to optimise event-based problems against delay propagation. We also present a real-world application to train platforming in the Italian railways, in order to show the practical effectiveness of our framework.

In the so-called lattice reformulation of an IP, the variable vector is written as an integer linear combination of kernel lattice basis vectors. This reformulation has been proven useful in several small but very hard instances. We investigate this technique for larger instances with no particular structure and observe that the lattice bases contain an identity matrix as a submatrix. Hence, some of the variables will have a "rich" translation in terms of the lattice basis vectors, and others represent a variable substitution. We present a theoretical analysis of this phenomenon, using probabilistic methods to capture the behavior of randomly generated input.

A salesman has to visit a list of cities starting in his home-city s and arriving at his week-end residence t . The place of the new 8/5 ratio among its predecessors can be explained in terms of the starting Fibonacci sequence 1, 1, 2, 3, 5, 8, 13 : Recall that the ratios a_{i+1} / a_i are alternatively below or above the golden ratio and converge to it. 1 /1 : a ratio that can never be reached. 2/1 : a ratio that can immediatly be reached. 3/2 : conjectured best approximation guarantee. Corresponds to 4/3 for s=t. For Graph Metrics 3/2 is proved and improved to 7/5 if s=t : Sebo, Vygen 5/3 : the garantee of the adapted Christofides algorithm (Hoogeveen). 8/5 : the new approximation garantee for the most general problem. The golden ratio (sqrt(5)+1)/2 proved by An, Kleinberg and Shmoys'. 13/8 : weaker ratio for a generalization (to T-joins) by Cheriyan, Friggstad et Gao. While the ratio 3/2 for the case s=t has not moved for general metrics in the last nearly forty years, the corresponding ratio moves down more easily for the path TSP, and brings in new algorithms and methods of analysis. After a survey of the main ideas for various versions I sketch the proof of the improved approximation ratio 8/5 for the path TSP problem with general metrics (and in fact for connected T-joins).

We propose an efficient Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic convex dynamic programs using the technique of $K$-approximation sets and functions introduced by Halman et al. This paper deals with the convex case only, and it has the following contributions: First, we improve on the worst-case running time given by Halman et al. Second, we design an FPTAS with excellent practical performance, and show that it is faster than an exact algorithm even for small problems instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. Our computational evaluation is based on randomly generated problem instances coming from applications in supply chain management and finance.

We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rooted-tree decompositions with matroid constraints. Our result characterizes digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result on packing of spanning arborescences and implies -- using a general orientation result of Frank -- the above result of Katoh and Tanigawa.

The hypergraph assignment problem (HAP) is the generalization of the assignment problem on bipartite graphs to bipartite hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. Even for problems with a small hyperedge size and hypergraphs with a special partitioned structure the HAP is NP-hard. We use an integer programming approach and investigate the resulting polyhedron of feasible solutions. Further, we develop combinatorial procedures for heuristic approximation results.

We investigate the problem of orienting the edges of an embedded graph in such a way that the in-degrees of both the nodes and faces meet given values. We show that the number of feasible solutions is bounded by 4^g, where g is the genus of the embedding, and all solutions can be determined within time O(4^g|E|^2 + |E|^3). In particular, for planar graphs the solution is unique if it exists, and in general the problem of finding a feasible orientation is fixed-parameter tractable in g. In sharp contrast to these results, we show that the problem becomes NP-complete even for a fixed genus if only upper and lower bounds on the in-degrees are specified instead of exact values.

Logical implications appear in a number of important mixed-integer nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, and vanishing constraints. In addition to the tightness of the respective relaxations, we also address the issue of constraint qualification and the behavior of computational methods for some formulations. As a benchmark, we formulate a truck cruise control problem with logical implications resulting from gear-choice specific constraints. Computational results for this benchmark are used to investigate feasibility gaps, integer feasibility gaps, quality of local solutions, and well-behavedness of numerical methods for the presented reformulations of the benchmark problem. Vanishing constraints give the most satisfactory results, and we are hence interested in efficient sequential solvers for nonlinear complementarity problems.

We discuss different modeling techniques and solution approaches for an application of a non-convex MINLP clustering problem in Software Engineering. Numerical results for benchmark instances compare the distinct approaches which include linearization techniques, column generation and global optimization.

We report on some recent developments in our research about the Perpective Reformulation of certain Mixed-Integer NonLinear Programs. We start with a brief recall of previous results in the area, pointing out how the whole research line started with a 100% serendipity moment, motivated by trying to prove wrong a referee who was in fact right but for the wrong reasons, and was brought forward in part by a series of other developments motivated by factors such as the need to finding another application to publish the first paper, the need of fending off competing research teams, and finding a good idea as a by-product of an original one that would never work. All this brought us to a Project-and-Lift approach to certain projected reformulations of the Perspective Reformulation which seems to be one of the few authentic violations of the "no free lunch principle": an easy reformulation of a MIQP with the very same size and structure as the original one but with a substantially stronger bound. Apart from providing an overview on a recent and potentially interesting research field in MINLP, we hope that this talk can motivate the audience to making more errors and looking at them with more interest.

We describe an ambulance location optimization model that maximizes the expected coverage provided by ambulance vehicles. The service level is measured by the fraction of calls reached within a given time threshold. The response time to a call consists of a random pre-trip delay plus a normally distributed travel time. Furthermore, we incorporate the fraction of time that an ambulance is unavailable. The problem is modelled as an integer linear programming problem and is applied on the region of Amsterdam, the Netherlands. Data of the ambulance service in 2010 is used to estimate the parameters of the model. The outcome of the model is an optimal set of locations for the ambulances in order to provide adequate coverage.

Weighted congestion games are an important class of noncooperative games that constitute an elegant model for the resource usage by selfish users. Unfortunately, they need not possess a pure Nash equilibrium, in general. We give a complete characterization of the maximal set of cost functions that one allow on the resources in order to guarantee the existence of a pure Nash equilibrium.

For more than 2500 years, philosophers have debated whether mathematical results are discovered or constructed. The talks summarizes the wildly differing thoughts, arguments, and conclusions. It also covers explanations how such variety of human thought is possible.

Minimizing a convex function over the integer points of a bounded convex set is polynomial in fixed dimension. We provide an alternative, short, and geometrically motivated proof of this result. Further, we present an oracle-polynomial algorithm based on a mixed integer linear optimization oracle.

The budgeted uncertainty polytope suffers from an important drawback: it is overly conservative for vectors with small cardinality. In particular, its probabilistic interpretation is meaningless for combinatorial problems whose solution has a small cardinality compared to the total number of variables. We introduce in this talk a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. Our model overcomes the problem of budgeted uncertainty by providing a probabilistic guarantee independent of the cardinality. Experiments carried out on the knapsack problem show a reduction of the price of robustness by an average factor of 18%, for a little increase in computational time. We study then the case where only the cost are uncertain and investigate the computational complexity. We show that in many cases, the resulting optimization problems belong to the same complexity class as the original optimization problem, generalizing the result proven by Bertsimas and Sim.

Traditionally, when an optimization problem is solved, the parameters of the problem (the constraint coefficients, the right hand sides and the objective coefficients) are supposed to be constant and fully known. Unfortunately, this is not always the case, as the parameters may be affected by measurement, implementation or estimation errors and/or they may be subject to change over time. Robust optimization provides a way to take the data uncertainty into account in order to produce robust solutions, i.e. solutions that are resilient to the variation of the input data. In this talk a generalization of the robust optimization framework proposed by Bertsimas and Sim is presented. The proposed model is based on the reasonable assumption that not all the data realizations occur with the same probability, but some of them are more likely to occur than others. The probabilistic and complexity properties of the original framework are generalized to the new model.

Coauthors: Sonja Mars, Jakob Schelbert We consider finding a Steiner tree subject to mechanical constraints. The mechanics of the problem are modeled by treating the edges of the Steiner tree as so called Timoshenko beams. The objective is to minimize a global measure for the stresses acting on the structure, the so called compliance. This problem can be reformulated using known techniques to a mixed-integer second-order-cone program. From the point of view of the application it is, however, of more interest to consider the case where the stresses need also to be bounded locally. We will sketch approaches to this variant of the problem. The motivation for studying this problem is a real-world problem: Find the optimal routing of steam pipes in a power plant. These pipes transport the hot steam from the main boiler to the steam turbines. They are the part of the plant that is worn down quickest in the station. Therefore, finding a routing the minimizes the mechanical stresses that act on these during the lifetime of the plant is important to increase the lifetime of the plant. The main focus of this talk will be the modeling and preliminary results. Supported by BMBF and Bilfinger.

In this work, we introduce the Two-Level Diameter Constrained Spanning Tree Problem (2-DMSTP) which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, strengthening valid inequalities, and symmetry breaking constraints. In particular, we propose a novel modeling approach based on a three-dimensional layered graph. In an extensive computational study we show that a branch-and-cut based on the latter model is highly effective in practice.

These slides contain a brief introduction of the Optimum Communication Spanning Tree Problem and summarize our work in progress towards obtaining a MILP formulation able to deal with medium-sized instances.

Suppose P is polytope for which one has at hands a complete description either in the original space or by means of an extended formulation and F is a subset of the vertex set X of P. We discuss, when it is possible to derive from the description of P a description of conv(X\F). One of our results is that in case of 0/1-polytopes P the extension complexity of conv(X\F) is bounded polynomially in the extension complexity of P and the cardinality of F. The talk is based on joint work with Shabbir Ahmed, Gustavo Angulo, and Santanu Dey. (I'd be happy to talk on Monday.)

In this talk we present techniques to construct extended formulations for stable set polytopes based on different decomposition rules: cutset decomposition, amalgam decomposition, template decomposition. These techniques lead to compact extended formulations for stable set polytopes of odd-signable cap-free graphs.

We introduce the reverse Chvatal-Gomory rank r*(P) of an integral polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all rational polyhedra whose integer hull is P. A well-known example in dimension two shows that there exist integral polytopes P with r*(P) equal to infinity. In this talk, we provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite. We also sketch possible extensions, in particular to the reverse split rank. Joint work with M. Conforti, A. Del Pia, M. Di Summa, and R. Grappe

Nash-Williams' famous orientation theorem states that each undirected graph has an orientation that keeps at least half of the connectivity (rounded down) between any two vertices. We study the related problem of orienting an undirected capacitated graph with given demands and supplies at the nodes so as to maintain a network flow satisfying the demands and supplies. While this task is trivial for classical (static) network flows, it leads to fascinating results when studied in the more general context of network flows over time. In general, an optimal transshipment over time in an undirected graph might have to use an edge in opposite directions at different points in time. Moreover, it is NP-complete to decide whether there is a feasible transshipment over time that uses each edge in one direction only. Our main result is that there always exists an orientation that allows to satisfy 1/3 of the total supplies and demands and this bound is tight.

In discrete optimisation problems the progress of objects over time is frequently modelled by shortest path problems in time expanded networks, but longer time spans or finer time discretisations quickly lead to model sizes that are intractable in practice. With typical objective functions, e.g. early completion time, the arising shortest paths in convex relaxations often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks’ sizes even for infinite time horizons. It can be applied whenever objects need to be routed through a traffic or production network with coupling capacity constraints and with a preference for early paths. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of arcs being used so far. This "frontier" of the graphs can be extended automatically as required by solution processes such as column generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the non-time-expanded network with a factor depending on the basic time offsets of these arcs. We illustrate the benefits of this technique on real world instances of a large scale train timetabling problem. Joint work with Christoph Helmberg

Discrete convexity has found application in several supply chain models. We survey some of these models, with a view towards making the supply chain context clear to non-specialists. In particular, we look at various attempts to model inventory problems in supply chains using discrete convexity. We focus in particular on the paper "Order-Based Cost Optimization in Assemble-to-Order Systems" by Lu and Song (OR 2005). A main result in that paper claims that the expected cost of an assemble to order inventory system is L-natural convex in the base stock levels of each item. We develop a simple example showing that this result is wrong.

The Molecular Distance Geometry Problem (MDGP) is to determine the embedding in K dimensions of a set of points molecule from some given information. An MDGP instance can be represented by a weighted, undirected simple graph G = (V, E). Under certain conditions, the MDGP can be solved searching a discrete set of points. These conditions involve the existence of suitable total orderings on V that guarantee that a minimum number of pair-wise distances are known.The first aim of this talk is to discuss the complexity of the problem of finding such total order. To tackle real-life instance we must consider that for same distances only an interval is known. We address this problem discretizing these inteval distanecs. We propose the use of techniques from the Clifford algebra to improve the discretization and the pruning steps.

Mathematical programming problems involving nonconvexities are usually solved to optimality using a spatial Branch-and-Bound (sBB) 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 iterative procedure to tighten the variable ranges. Depending on the instance, FBBT may not converge finitely to its limit ranges, even in the case of linear constraints. Tolerance-based termination criteria yield finite termination, but not in worst-case polynomial time. We model FBBT by using fixed-point equations in terms of the variable bounding box, and we treat these equations as constraints of an auxiliary mathematical program. We demonstrate that the auxiliary mathematical problem is a linear program, which can of course be solved in polynomial time. We demonstrate the usefulness of our approach by improving the open-source sBB solver Couenne.