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 条
  • [41] FPTAS for mixed-integer polynomial optimization with a fixed number of variables
    De Loera, J. A.
    Hemmecke, R.
    Koeppe, M.
    Weismantel, R.
    PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 743 - +
  • [42] A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
    Kronqvist, Jan
    Li, Boda
    Rolfes, Jan
    OPTIMIZATION AND ENGINEERING, 2024, 25 (03) : 1271 - 1296
  • [43] Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds
    Brand, Cornelius
    Koutecký, Martin
    Lassota, Alexandra
    Ordyniak, Sebastian
    Leibniz International Proceedings in Informatics, LIPIcs, 2024, 308
  • [44] Efficient upper and lower bounds for global mixed-integer optimal control
    Sebastian Sager
    Mathieu Claeys
    Frédéric Messine
    Journal of Global Optimization, 2015, 61 : 721 - 743
  • [45] APPROXIMATION PROPERTIES AND TIGHT BOUNDS FOR CONSTRAINED MIXED-INTEGER OPTIMAL CONTROL
    Kirches, C.
    Lenders, F.
    Manns, P.
    SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2020, 58 (03) : 1371 - 1402
  • [46] Efficient upper and lower bounds for global mixed-integer optimal control
    Sager, Sebastian
    Claeys, Mathieu
    Messine, Frederic
    JOURNAL OF GLOBAL OPTIMIZATION, 2015, 61 (04) : 721 - 743
  • [47] Mixed-Integer DAE Optimal Control Problems: Necessary Conditions and Bounds
    Gerdts, Matthias
    Sager, Sebastian
    CONTROL AND OPTIMIZATION WITH DIFFERENTIAL-ALGEBRAIC CONSTRAINTS, 2012, (23): : 189 - +
  • [48] Mixed-Integer Quadrangulation
    Bommes, David
    Zimmer, Henrik
    Kobbelt, Leif
    ACM TRANSACTIONS ON GRAPHICS, 2009, 28 (03):
  • [49] Mixed-Integer Programming for Signal Temporal Logic With Fewer Binary Variables
    Kurtz, Vincent
    Lin, Hai
    IEEE CONTROL SYSTEMS LETTERS, 2022, 6 : 2635 - 2640
  • [50] Valid inequalities for mixed-integer programmes with fixed charges on sets of variables
    Letchford, Adam N.
    Souli, Georgia
    OPERATIONS RESEARCH LETTERS, 2020, 48 (03) : 240 - 244