Bound reduction using pairs of linear inequalities

We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m ²) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n ³) for each pair. Therefore, its overall complexity O(m ² n ³) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m ² n ²), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.     

The dependency diagram of a 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. It is also explained how redundant inequalities can be removed, using the method attributed to Chernikov and to Kohler. Some new results are given. The procedure also leads to a transparent explanation of Farkas’ Lemma, LP Duality, the dual form of Caratheodory’s Theorem as well as generating all vertices and extreme rays of the Dual Polytope.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

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.     

A numerically exact implementation of the simplex method

The numerical performance of the state-of-the-art simplex based optimizers is good. At the same time, a newly arising LP problem can cause troubles still. This is exactly what happened in the Summer of 1992. The appearance of a hard LP problem motivated the development of the idea of a numerically exact implementation of the simplex method. It is based on a super register (SR) capable of accumulating inner products with arbitrary accuracy. The necessary operations of SR that require assembly level programming are introduced. Vectors of super registers would require prohibitively much memory. Therefore, a single-SR technique is proposed that entails the reorganization of parts of the simplex method. The ideas have been implemented in the MILP LP optimizer. Experiences show that solution speed decreases by 30–50 percent but robustness increases which may be important in case of critical problems. A framework is outlined for a system where the advantages of the traditional and the SR technique can co-operate efficiently.This research was partly supported by Hungarian Research Fund OTKA 2587.     

Modeling demand management strategies for evacuations

Evacuations are massive operations that create heavy travel demand on road networks some of which are experiencing major congestions even with regular traffic demand. Congestion in traffic networks during evacuations, can be eased either by supply or demand management actions. This study focuses on modeling demand management strategies of optimal departure time, optimal destination choice and optimal zone evacuation scheduling (also known as staggered evacuation) under a given fixed evacuation time assumption. The analytical models are developed for a system optimal dynamic traffic assignment problem, so that their characteristics can be studied to produce insights to be used for large-scale solution algorithms. While the first two strategies were represented in a linear programming (LP) model, evacuation zone scheduling problem inevitable included integers and resulted in a mixed integer LP (MILP) one. The dual of the LP produced an optimal assignment principle, and the nature of the MILP formulations revealed clues about more efficient heuristics. The discussed properties of the models are also supported via numerical results from a hypothetical network example.     

Symbolic integration of logic in MILP branch and bound methods for the synthesis of process networks

This paper deals with the branch and bound solution of process synthesis problems that are modelled as mixed-integer linear programming (MILP) problems. The symbolic integration of logic relations between potential units in a process network is proposed in the LP based branch and bound method to expedite the search for the optimal solution. The objective of this integration is to reduce the number of nodes that must be enumerated by using the logic to decide on the branching of variables and to determine by symbolic inference whether additional variables can be fixed at each node. The important feature of this approach is that it does not require additional constraints in the MILP and the logic can be systematically generated for process networks. Strategies for performing the integration are proposed that use the disjunctive and conjunctive normal form representations of the logic, respectively. Computational results will be presented to illustrate that substantial savings can be achieved.     

Unique lifting of integer variables in minimal inequalities

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting (This result first appeared in the proceedings of IPCO 2010). The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function.     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

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.     

A linear programming framework for free disposal hull technologies and cost functions: Primal and dual models

The free disposal hull (FDH) model, introduced by Deprins et al. [The Performance of Public Enterprises Concepts and Measurements, Elsevier, 1984], is based on a representation of the production technology given by observed production plans, imposing strong disposability of inputs and outputs but without the convexity assumption. In its traditional form, the FDH model assumes implicitly variable returns to scale (VRS) and the model was solved by a mixed integer linear program (MILP). The MILP structure is often used to compare the FDH model to data envelopment analysis (DEA) models although an equivalent FDH LP model exists (see Agrell and Tind [Journal of Productivity Analysis 16 (2) (2001) 129]). More recently, specific returns to scale (RTS) assumptions have been introduced in FDH models by Kerstens and Vanden Eeckaut [European Journal of Operational Research 113 (1999) 206], including non-increasing, non-decreasing, or constant returns to scale (NIRS, NDRS, and CRS, respectively). Podinovski [European Journal of Operational Research 152 (2004) 800] showed that the related technical efficiency measures can be computed by mixed integer linear programs. In this paper, the modeling proposed here goes one step further by introducing a complete LP framework to deal with all previous FDH models.     

Synergies from spreadsheet LP used with the theory of constraints—a case study

This paper describes a case study relating to a food-processing plant. The methods used to address the case include spreadsheets combined with Goldratt's Theory of Constraints (TOC), both of which are accessible to practising managers. The paper demonstrates how standard spreadsheet optimisation tools can be used in combination with a TOC framework to provide effective decision aids. The results from the case study indicate real productivity improvements are possible from even small models of a situation. The paper explores the interrelationships and complementaries between Linear Programming and Theory of Constraints frameworks, and details the steps involved in using them in combination. We argue that traditional LP practice should be modified in light of the ease with which LPs can be solved, and suggest that the Theory of Constraints approach provides a useful framework to guide LP use. We share some of the insights gained both by the analysts and by the company.     

An optimization-based approach to assess non-interference in labeled and bounded Petri net systems

An optimization-based approach to assess both strong non-deterministic non- interference (SNNI) and bisimulation SNNI (BSNNI) in discrete event systems modeled as labeled Petri nets is presented in this paper. The assessment of SNNI requires the solution of feasibility problems with integer variables and linear constraints, which is derived by extending a previous result given in the case of unlabeled net systems. Moreover, the BSNNI case can be addressed in two different ways. First, similarly to the case of SNNI, a condition to assess BSNNI, which is necessary and sufficient, can be derived from the one given in the unlabeled framework, requiring the solution of feasibility problems with integer variables and linear constraints. Then, a novel necessary and sufficient condition to assess BSNNI is given, which requires the solution of integer feasibility problems with nonlinear constraints. Furthermore, we show how to recast these problems into equivalent mixed-integer linear programming (MILP) ones. The effectiveness of the proposed approaches is shown by means of several examples. It turns out that there are relevant cases where the new condition to assess BSNNI that requires the solution of MILP problems is computationally more efficient, when compared to the one that requires the solution of feasibility problems.     

Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

In this paper new MILP formulations for the multiple allocation p-hub median problem are presented. These require fewer variables and constraints than those traditionally used in the literature. An efficient heuristic algorithm, based on shortest paths, is described. LP based solution methods as well as an explicit enumeration algorithm are developed to obtain exact solutions. Computational results are presented for well known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. Our algorithms are also benchmarked on a different data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network and has been treated by the authors in an earlier paper.     

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

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.     

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.