A branch and bound method for the solution of multiparametric mixed integer linear programming problems

Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios
July 2014
Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527
Academic Journal
In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the mp-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.


Related Articles

  • Global optimization of general nonconvex problems with intermediate polynomial substructures. Zorn, Keith; Sahinidis, Nikolaos // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p673 

    This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations...

  • Disjunctive programming and relaxations of polyhedra. Conforti, Michele; Del Pia, Alberto // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p307 

    Given a polyhedron $$L$$ with $$h$$ facets, whose interior contains no integral points, and a polyhedron $$P$$, recent work in integer programming has focused on characterizing the convex hull of $$P$$ minus the interior of $$L$$. We show that to obtain such a characterization it suffices to...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model. Brooks, J. Paul; Lee, Eva K. // INFORMS Journal on Computing;Summer2014, Vol. 26 Issue 3, p567 

    Solution methods are presented for a mixed-integer program (MIP) associated with a method for constrained discrimination. In constrained discrimination, one wishes to maximize the probability of correct classification subject to intergroup misclassification limits. The misclassification limits...

  • Extension of the Firefly Algorithm and Preference Rules for Solving MINLP Problems. Costa, M. Fernanda P.; Francisco, Rogério B.; Rocha, Ana Maria A. C.; Fernandes, Edite M. G. P. // AIP Conference Proceedings;2017, Vol. 1863 Issue 1, p1 

    An extension of the firefly algorithm (FA) for solving mixed-integer nonlinear programming (MINLP) problems is presented. Although penalty functions are nowadays frequently used to handle integrality conditions and inequality and equality constraints, this paper proposes the implementation...

  • Dynamic Facility Location with Generalized Modular Capacities. Jena, Sanjay Dominik; Cordeau, Jean-François; Gendron, Bernard // Transportation Science;Aug2015, Vol. 49 Issue 3, p484 

    Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule...

  • Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems. Castro, Pedro; Grossmann, Ignacio // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p277 

    We address nonconvex mixed-integer bilinear problems where the main challenge is the computation of a tight upper bound for the objective function to be maximized. This can be obtained by using the recently developed concept of multiparametric disaggregation following the solution of a...

  • Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets. Sanjeevi, Sujeevraja; Masihabadi, Sina; Kianfar, Kiavash // Mathematical Programming;Sep2016, Vol. 159 Issue 1/2, p571 

    Based on a bijective mapping between two mixed integer sets, we introduce a new perspective on developing cuts for the mixed integer polyhedral conic (MIPC) set by establishing a one-to-one correspondence between the cuts for this set and those for a related mixed integer knapsack (MIK) set. The...

  • Surrogate-RLT cuts for zero-one integer programs. Yuh, Junsang; Lee, Youngho // Journal of Global Optimization;Oct2016, Vol. 66 Issue 2, p173 

    In this paper, we consider the class of 0-1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation-linearization technique (RLT) to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics