Large-scale mixed integer programming: Benders-type heuristics

The limited success of exact methods for solving integer programming problems has prompted the development of heuristic procedures which have performed surprisingly well in their search for near-optimal solutions. The present paper constitutes an attempt to generalize these procedures to the mixed integer case. The approach is based on the utilization of the Benders partitioning method (BPM) which separates the integer from the continuous variables. A number of alternatives are presented for integrating IP heuristics in the BPM thus alleviating its main limitation: the necessity of solving a sequence of integer master problems. The rationale and its usefulness are illustrated on large-scale applications from the fields of power systems and network flows.     

On convergence in mixed integer programming

Let ${P \subseteq {\mathbb R}^{m+n}}$ be a rational polyhedron, and let P _I be the convex hull of ${P \cap ({\mathbb Z}^m \times {\mathbb R}^n)}$ . We define the integral lattice-free closure of P as the set obtained from P by adding all inequalities obtained from disjunctions associated with integral lattice-free polyhedra in ${{\mathbb R}^m}$ . We show that the integral lattice-free closure of P is again a polyhedron, and that repeatedly taking the integral lattice-free closure of P gives P _I after a finite number of iterations. Such results can be seen as a mixed integer analogue of theorems by Chvátal and Schrijver for the pure integer case. One ingredient of our proof is an extension of a result by Owen and Mehrotra. In fact, we prove that for each rational polyhedron P, the split closures of P yield in the limit the set P _I .     

Conflict analysis in mixed integer programming

Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers. In contrast, it is common practice for today’s mixed integer programming solvers to discard infeasible subproblems and the information they reveal. In this paper, we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming.We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting constraints. Extensive computational experiments show the potential of our method. Conflict analysis greatly improves the performance on particular models, while it does not interfere with the solving process on the other instances. In total, the number of required branching nodes on general MIP instances was reduced by 18% in the geometric mean, and the solving time was reduced by 11%. On infeasible MIPs arising in the context of chip verification and on a model for a particular combinatorial game, the number of nodes was reduced by 80%, thereby reducing the solving time by 50%.     

MIDAS: A mixed integer dynamic approximation scheme

Mathematical Programming - Mixed integer dynamic approximation scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman...     

Application-oriented mixed integer non-linear programming

This is a summary of the author’s PhD thesis supervised by Andrea Lodi and defended on 16 April 2009 at the University of Bologna. The thesis is written in English and available for download at . The main topic of the thesis is Mixed Integer Non-Linear Programming, with focus on non-convex problems (i.e., problems for which the feasible region of the continuous relaxation is a non-convex set) and real-world applications. Different kinds of algorithms are presented: linearization methods, heuristic and global optimization algorithms. Also, different kinds of real-world applications are solved, arising, for example, from Hydraulic and Electrical Engineering problems. The last part of the thesis is devoted to software and tools for mixed integer non-linear programming problems.     

Marginal values in mixed integer linear programming

For a given optimization problem, P, considered as a function of the data, its marginal values are defined as the directional partial derivatives of the value of P with respect to perturbations in that data. For linear programs, formulas for the marginal values were given by Mills, [10], and further developed by the current author [16]. In this paper, the marginal value formulas are extended to the case of mixed integer linear programming (MIP). As in ordinary linear programming, discontinuities in the value can occur, and the analysis here identifies them. This latter aspect extends previous work on continuity by the current author, [18], Geoffrion and Nauss, [5], Nauss, [11], and Radke, [12], and work on the value function of Blair and Jeroslow, [2]. Application is made to model formulation and to post-optimal analysis.Supported in part by the Air Force Office of Scientific Research, Grant # AFSOR-0271 to Rutgers University.     

Majorization in de Branges spaces I. Representability of subspaces

In this series of papers we study subspaces of de Branges spaces of entire functions which are generated by majorization on subsets D of the closed upper half-plane. The present, first, part is addressed to the question which subspaces of a given de Branges space can be represented by means of majorization. Results depend on the set D where majorization is permitted. Significantly different situations are encountered when D is close to the real axis or accumulates to i∞.     

Strong formulations for mixed integer programming: A survey

We attempt to motivate and survey recent research on the use of strong valid inequalities and reformulation to solve mixed integer programming problems.     

Scheduling staff using mixed integer programming

This paper describes the solution of a problem of scheduling a workforce so as to meet demand which varies markedly with the time of day and moderately with the day of week. The main objectives are determining how many staff to employ and the times at which shifts should start. The problem is expressed as a large MIP problem initially presenting computational difficulties. The difficulties vanish when the formulation is modified and a package allowing the use of reduce and (especially) special ordered sets becomes available. The client has commissioned the study primarily to benchmark its existing schedule by comparing it with a theoretical optimum. The optimal schedule and comparison are very sensitive to technical and cost coefficients which are not precisely known.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Alternative formulations of mixed integer programs

We study the formation of mixed-integer programming (MIP) constraints through the development of constructions which syntactically parallel the set operations of union, intersection, Cartesian product, and linear affine transformation. In this manner, we are able to both modularize the work of constructing representations (as the representations for base sets of a composite construction need not be disjunctively derived) and to make connections to certain of the logic-based approaches to artificial intelligence which utilize the intersection (and) and union (or) operations. We provide results which allow one to calculate the linear relaxation of a composite construction, in terms of set operations on the relaxation of the base sets. We are also able to compare the size of the relaxations for different formulations of the same MIP set, when these different formulations arise from one another through distributive laws. Utilizing these results, we generalize the Davis-Putnam algorithm of propositional logic to an MIP form, and answer a question regarding the relative efficiency of two versions of this algorithm. In this context, the subroutines of the logic algorithm correspond to list processing subroutines for MIP to be used prior to running linear programs. They are similar in nature to preprocessing routines, wherein entire MIP constraint sets are manipulated as formal symbols of logic.This work has been partially supported by National Science Foundation Grant MCS-8304075.     

Strengthening cuts for mixed integer programs

We give a method for strengthening cutting planes for pure and mixed integer programs. The method improves the coefficients of the integer-constrained variables, while leaving unchanged those of the continuous variables. We first state the general principle on which the method is based; then apply it to the class of cuts that can be obtained from disjunctive constraints. Finally, we give simple procedures for calculating the improved coefficients of cats in this class, and illustrate them on a numerical example.     

An algorithm for mixed integer optimization

This paper introduces a new algorithm for solving mixed integer programs. The core of the method is an iterative technique for changing the representation of the original mixed integer optimization problem. Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202.Mathematics Subject Classification (1991):90C11     

Sequential pairing of mixed integer inequalities

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.     

Further results on an abstract model for branching and its application to mixed integer programming

Mathematical Programming - A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection...     

Classification accuracy in discriminant analysis: a mixed integer programming approach

Classification models can be developed by statistical or mathematical programming discriminant analysis techniques. Variable selection extensions of these techniques allow the development of classification models with a limited number of variables. Although stepwise statistical variable selection methods are widely used, the performance of the resultant classification models may not be optimal because of the stepwise selection protocol and the nature of the group separation criterion. A mixed integer programming approach for selecting variables for maximum classification accuracy is developed in this paper and the performance of this approach, measured by the leave-one-out hit rate, is compared with the published results from a statistical approach in which all possible variable subsets were considered. Although this mixed integer programming approach can only be applied to problems with a relatively small number of observations, it may be of great value where classification decisions must be based on a limited number of observations.