Facets of a mixed-integer bilinear covering set with bounds on variables

被引:5
|
作者
Rahman, Hamidur [1 ]
Mahajan, Ashutosh [1 ]
机构
[1] Indian Inst Technol, Ind Engn & Operat Res, Mumbai 400076, Maharashtra, India
关键词
Bilinear constraints; Mixed-integer programming; Separation; Global optimization; Cutting-stock problem;
D O I
10.1007/s10898-019-00783-0
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We derive a closed form description of the convex hull of mixed-integer bilinear covering set with bounds on the integer variables. This convex hull description is determined by considering some orthogonal disjunctive sets defined in a certain way. This description does not introduce any new variables, but consists of exponentially many inequalities. An extended formulation with a few extra variables and much smaller number of constraints is presented. We also derive a linear time separation algorithm for finding the facet defining inequalities of this convex hull. We study the effectiveness of the new inequalities and the extended formulation using some examples.
引用
收藏
页码:417 / 442
页数:26
相关论文
共 50 条
  • [31] Generalized Nash Equilibrium Problems with Mixed-Integer Variables
    Hark, Tobias
    Schwarz, Julian
    WEB AND INTERNET ECONOMICS, WINE 2021, 2022, 13112 : 552 - 552
  • [32] Algorithms for generalized potential games with mixed-integer variables
    Simone Sagratella
    Computational Optimization and Applications, 2017, 68 : 689 - 717
  • [33] Generalized Nash equilibrium problems with mixed-integer variables
    Harks, Tobias
    Schwarz, Julian
    MATHEMATICAL PROGRAMMING, 2025, 209 (1-2) : 231 - 277
  • [34] Algorithms for generalized potential games with mixed-integer variables
    Sagratella, Simone
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2017, 68 (03) : 689 - 717
  • [35] A Distributed Algorithm for Demand Response With Mixed-Integer Variables
    Mhanna, Sleiman
    Chapman, Archie C.
    Verbic, Gregor
    IEEE TRANSACTIONS ON SMART GRID, 2016, 7 (03) : 1754 - 1755
  • [36] Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems
    Pedro M. Castro
    Journal of Global Optimization, 2016, 64 : 765 - 784
  • [37] Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems
    Castro, Pedro M.
    JOURNAL OF GLOBAL OPTIMIZATION, 2016, 64 (04) : 765 - 784
  • [38] Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
    Hildebrand, Robert
    Weismantel, Robert
    Zenklusen, Rico
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 2342 - 2350
  • [39] Valid Linear Programming Bounds for Exact Mixed-Integer Programming
    Steffy, Daniel E.
    Wolter, Kati
    INFORMS JOURNAL ON COMPUTING, 2013, 25 (02) : 271 - 284
  • [40] Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
    Cevallos, Alfonso
    Weltge, Stefan
    Zenklusen, Rico
    SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 788 - 807