Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets

Sanjeevi, Sujeevraja; Masihabadi, Sina; Kianfar, Kiavash
September 2016
Mathematical Programming;Sep2016, Vol. 159 Issue 1/2, p571
Academic Journal
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 face/facet-defining properties of the corresponding cuts are identical for their respective sets. We further show that the cut generation approach for the MIPC set resulting from this new perspective always produces cuts that dominate those generated based on any of the two individual MIK constraints corresponding to the MIPC constraint. Our computational results show this dominance can be quite significant. As a special case of this new perspective, the conic MIR inequality of Atamtürk and Narayanan for the MIPC set and its properties can be directly derived from the MIR inequality for the MIK set and its properties. We also generalize these cuts to the n-step conic MIR inequalities, which are directly derived form the n-step MIR inequalities for the MIK set.


Related Articles

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

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

  • Tight polyhedral approximation for mixed-integer linear programming unit commitment formulations. Jabr, R. A. // IET Generation, Transmission & Distribution;Nov2012, Vol. 6 Issue 11, p1104 

    The perspective reformulation has been recently proposed for constructing tight relaxations of the unit commitment (UC) problem with quadratic cost functions. In this case, it has been shown that the perspective reformulation can be cast as a second-order cone program. Conic quadratic...

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

  • Bilevel Programming, Equilibrium, and Combinatorial Problems with Applications to Engineering 2016. Kalashnikov, Vyacheslav V.; Dempe, Stephan; Matis, Timothy I.; Camacho-Vallejo, José-Fernando; Kavun, Sergii V. // Mathematical Problems in Engineering;11/17/2016, p1 

    No abstract available.

  • Microgrid Operation Optimization Considering Storage Devices, Electricity Transactions and Reserve. Fan, Wen; Liao, Yuan // International Journal of Emerging Electric Power Systems;Oct2019, Vol. 20 Issue 5, p1 

    This paper presents a new method for optimizing the operation of a microgrid, which minimizes the operating cost or maximizes solar generation of the microgrid. The microgrid consists of loads, storage devices, and distributed generations. The generation cost, capacity, ramp up and down rate,...

  • MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. Ling Sun; Wei Wang; Wang, Meiqin Q. // IET Information Security;2020, Vol. 14 Issue 1, p12 

    In this study, the authors settle the feasibility of mixed integer linear programming (MILP)-aided bit-based division property for ciphers with non-bit-permutation linear layers. First, they transform the complicated linear layers to their primitive representations. Then, the original Copy and...


Read the Article


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

Try another library?
Sign out of this library

Other Topics