Disjunctive programming and relaxations of polyhedra

Conforti, Michele; Del Pia, Alberto
April 2014
Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p307
Academic Journal
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 consider all relaxations of $$P$$ defined by at most $$n(h-1)$$ among the inequalities defining $$P$$. This extends a result by Andersen, Cornuéjols, and Li.


Related Articles

  • 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...

  • A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527 

    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...

  • 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...

  • Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation. Grossmann, Ignacio; Lee, Sangbum // Computational Optimization & Applications;Oct2003, Vol. 26 Issue 1, p83 

    Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous...

  • 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...

  • Exact and approximate methods for a one-dimensional minimax bin-packing problem. Brusco, Michael; Köhn, Hans; Steinley, Douglas // Annals of Operations Research;Jul2013, Vol. 206 Issue 1, p611 

    One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the 'weights' of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign...

  • AN IMPROVED DIRECT SEARCH APPROACH FOR SOLVING MIXED-INTEGER NONLINEAR PROGRAMMING PROBLEMS. Mawengkang, Herman; Guno, Mangku M.; Hartama, Dedy; Siregar, Arie S.; Adam, Hikmah A.; Alfina, Ommi // Global Journal of Technology & Optimization;Jun2012, Vol. 3 Issue 1, p94 

    The special class of a nonlinear mathematical programming problem which is addressed in this paper has a structure characterized by a subset of variables restricted to assume discrete values, which are linear and separable from the continuous variables. The strategy of releasing non-basic...

  • A Mathematical Programming Model for Tactical Planning with Set-up Continuity in a Two-stage Ceramic Firm. Peralesal, David Perez; Alemanya, M. M. Eva // International Journal of Production Management & Engineering;Jul-Dec2016, Vol. 4 Issue 2, p53 

    It is known that capacity issues in tactical production plans in a hierarchical context are relevant since its inaccurate determination may lead to unrealistic or simply non-feasible plans at the operational level. Semi-continuous industrial processes, such as ceramic ones, often imply large...

  • Security-Aware Scheduling for FlexRay-Based Real-Time Automotive Systems. Zhao, R.; Qin, G. H.; Chen, H. P.; Qin, J.; Yan, J. // Mathematical Problems in Engineering;6/13/2019, p1 

    FlexRay is a hybrid communication protocol tailored to the requirements of safety-critical distributed real-time automotive systems, providing support for the transmission of time-critical periodic frames in a static segment and event-triggered frames in a dynamic segment. With the development...


Read the Article


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

Try another library?
Sign out of this library

Other Topics