The dependency diagram of a mixed integer linear programme

The Dependency Diagram of a Linear Programme (LP) shows how the successive inequalities of an LP depend on former inequalities, when variables are projected out by Fourier-Motzkin Elimination. This is explained in a paper referenced below. The paper, given here, extends the results to the Mixed Integer case (MILP). It is shown how projection of a MILP leads to a finite disjunction of polytopes. This is expressed as a set of inequalities (mirroring those in the LP case) augmented by correction terms with finite domains which are subject to linear congruences.     

The finite-to-finite strand of a learning progression for the concept of function: A research synthesis and cognitive analysis

In this paper we report validation efforts around the finite-to-finite strand of a provisional learning progression (LP) for the concept of function. We regard an LP as an empirically-verified account of how student understandings form over time and in response to instruction. The finite-to-finite strand of the LP was informed by literature on students’ thinking and learning related to functions as well as the Algebra Project’s curricular approach, which is designed for students who are traditionally underserved by mathematics education. Developing and validating an LP is a multi-step, cyclic process. Here we report on one step in this process, an item and response analysis. Data sources include 680 students’ responses to 13 multipart computer-delivered tasks. Results suggest that revisions to the items, associated scoring rubrics, and in some instances the LP are warranted. We illustrate this task, rubric, and LP revision process through an item analysis for a selected task.     

On discrete lot-sizing and scheduling on identical parallel machines

We consider the multi-item discrete lot-sizing and scheduling problem on identical parallel machines. Based on the fact that the machines are identical, we introduce aggregate integer variables instead of individual variables for each machine. For the problem with start-up costs, we show that the inequalities based on a unit flow formulation for each machine can be replaced by a single integer flow formulation without any change in the resulting LP bound. For the resulting integer lot-sizing with start-ups subproblem, we show how inequalities for the unit demand case can be generalized and how an approximate version of the extended formulation of Eppen and Martin can be constructed. The results of some computational experiments carried out to compare the effectiveness of the various mixed-integer programming formulations are presented.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

Inequalities,assessment and computer algebra

The goal of this paper is to examine single variable real inequalities that arise as tutorial problems and to examine the extent to which current computer algebra systems (CAS) can (1) automatically solve such problems and (2) determine whether students’ own answers to such problems are correct. We review how inequalities arise in contemporary curricula. We consider the formal mathematical processes by which such inequalities are solved, and we consider the notation and syntax through which solutions are expressed. We review the extent to which current CAS can accurately solve these inequalities, and the form given to the solutions by the designers of this software. Finally, we discuss the functionality needed to deal with students’ answers, i.e. to establish equivalence (or otherwise) of expressions representing unions of intervals. We find that while contemporary CAS accurately solve inequalities there is a wide variety of notation used.     

An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution

This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any bigM initialization assumption. The complexity of the algorithm is sensitive to and is dependent on the quality of the starting point, as assessed by suitable measures of the extent of infeasibility and the extent of nonoptimality of the starting point. Two new measures of the extent of infeasibility and of nonoptimality of a starting point are developed. We then present an algorithm for solving LP whose complexity depends explicitly and only on how close the starting point is to the set of LP feasible and optimal solutions (using these and other standard measures), and also onn (the number of inequalities). The complexity results using these measures of infeasibility and nonoptimality appear to be consistent with the observed practical sensitivity of interior-point algorithms to certain types of starting points. The starting point can be any pair of primal and dual vectors that may or may not be primal and/or dual feasible, and that satisfies a simple condition that typically arises in practice or is easy to coerce.Research supported in part by the MIT-NTU Collaboration Agreement.     

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

On the polyhedral structure of a multi–item production planning model with setup times

 We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results for lifting valid inequalities for 0–1 continuous knapsack problems. Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002 Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network flow Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

Extended formulations in combinatorial optimization

This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski-Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set, and we present the proof of Fiorini, Massar, Pokutta, Tiwary and de Wolf of an exponential lower bound for the cut polytope. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.     

An integrated model for logistics network design

In this paper we introduce a new formulation of the logistics network design problem encountered in deterministic, single-country, single-period contexts. Our formulation is flexible and integrates location and capacity choices for plants and warehouses with supplier and transportation mode selection, product range assignment and product flows. We next describe two approaches for solving the problem---a simplex-based branch-and-bound and a Benders decomposition approach. We then propose valid inequalities to strengthen the LP relaxation of the model and improve both algorithms. The computational experiments we conducted on realistic randomly generated data sets show that Benders decomposition is somewhat more advantageous on the more difficult problems. They also highlight the considerable performance improvement that the valid inequalities produce in both solution methods. Furthermore, when these constraints are incorporated in the Benders decomposition algorithm, this offers outstanding reoptimization capabilities.     

On formulations of the stochastic uncapacitated lot-sizing problem

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (?,S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions.     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.