IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v70y2018i4d10.1007_s10898-017-0602-1.html
   My bibliography  Save this article

An interleaved depth-first search method for the linear optimization problem with disjunctive constraints

Author

Listed:
  • Yinrun Lyu

    (Chinese Academy of Sciences
    University of Chinese Academy of Sciences)

  • Li Chen

    (Chinese Academy of Sciences
    University of Chinese Academy of Sciences)

  • Changyou Zhang

    (Chinese Academy of Sciences)

  • Dacheng Qu

    (Beijing Institute of Technology)

  • Nasro Min-Allah

    (University of Dammam)

  • Yongji Wang

    (Chinese Academy of Sciences
    University of Chinese Academy of Sciences)

Abstract

Being an extension of classical linear programming, disjunctive programming has the ability to express the problem constraints as combinations of linear equalities and inequalities linked with logic AND and OR operations. All the existing theories such as generalized disjunctive programming, optimization modulo theories, linear optimization over arithmetic constraint formula, and mixed logical linear programming pose one commonality of branching among different solving techniques. However, branching constructs a depth-first search which may traverse a whole bad subtree when the branching makes a mistake ordering a bad successor. In this paper, we propose the interleaved depth-first search with stochastic local optimal increasing (IDFS-SLOI) method for solving the linear optimization problem with disjunctive constraints. Our technique searches depth-first several subtrees in turn, accelerates the search by subtree splitting, and uses efficient backtracking and pruning among the subtrees. Additionally, the local optimal solution is improved iteratively by constructing and solving a stochastic linear programming problem. We evaluate our approach against existing counterparts on the rate-monotonic optimization problem (RM-OPT) and the linear optimization with fuzzy relation inequalities problem (LOFRI). Experimental results show that for the tested instances, the IDFS-SLOI method performs better from performance perspective, especially promising results have been obtained for the larger three groups where the execution time is reduced by 85.6 and 51.6% for RM-OPT and LOFRI, respectively.

Suggested Citation

  • Yinrun Lyu & Li Chen & Changyou Zhang & Dacheng Qu & Nasro Min-Allah & Yongji Wang, 2018. "An interleaved depth-first search method for the linear optimization problem with disjunctive constraints," Journal of Global Optimization, Springer, vol. 70(4), pages 737-756, April.
    • Handle: RePEc:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0602-1
    DOI: 10.1007/s10898-017-0602-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0602-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-017-0602-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Francisco Trespalacios & Ignacio E. Grossmann, 2016. "Cutting Plane Algorithm for Convex Generalized Disjunctive Programs," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 209-222, May.
    2. Ruiz, Juan P. & Grossmann, Ignacio E., 2012. "A hierarchy of relaxations for nonlinear convex generalized disjunctive programming," European Journal of Operational Research, Elsevier, vol. 218(1), pages 38-47.
    3. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    4. Li Chen & Yinrun Lyu & Chong Wang & Jingzheng Wu & Changyou Zhang & Nasro Min-Allah & Jamal Alhiyafi & Yongji Wang, 2017. "Solving linear optimization over arithmetic constraint formula," Journal of Global Optimization, Springer, vol. 69(1), pages 69-102, September.
    5. Juan P. Ruiz & Ignacio E. Grossmann, 2017. "Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques," Journal of Global Optimization, Springer, vol. 67(1), pages 43-58, January.
    6. Sawaya, Nicolas & Grossmann, Ignacio, 2012. "A hierarchy of relaxations for linear generalized disjunctive programming," European Journal of Operational Research, Elsevier, vol. 216(1), pages 70-82.
    7. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Francisco Trespalacios & Ignacio E. Grossmann, 2015. "Algorithmic Approach for Improved Mixed-Integer Reformulations of Convex Generalized Disjunctive Programs," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 59-74, February.
    2. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    3. Dimitri J. Papageorgiou & Francisco Trespalacios, 2018. "Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 55-83, March.
    4. Francisco Trespalacios & Ignacio E. Grossmann, 2016. "Cutting Plane Algorithm for Convex Generalized Disjunctive Programs," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 209-222, May.
    5. Harsha Nagarajan & Mowen Lu & Site Wang & Russell Bent & Kaarthik Sundar, 2019. "An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs," Journal of Global Optimization, Springer, vol. 74(4), pages 639-675, August.
    6. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    7. Shuming Wang & Yan-Fu Li & Tong Jia, 2020. "Distributionally Robust Design for Redundancy Allocation," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 620-640, July.
    8. Alidaee, Bahram, 2014. "Zero duality gap in surrogate constraint optimization: A concise review of models," European Journal of Operational Research, Elsevier, vol. 232(2), pages 241-248.
    9. Li, Haitao & Womer, Keith, 2012. "Optimizing the supply chain configuration for make-to-order manufacturing," European Journal of Operational Research, Elsevier, vol. 221(1), pages 118-128.
    10. Can Li & Ignacio E. Grossmann, 2019. "A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables," Journal of Global Optimization, Springer, vol. 75(4), pages 921-947, December.
    11. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    12. Juan P. Ruiz & Ignacio E. Grossmann, 2017. "Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques," Journal of Global Optimization, Springer, vol. 67(1), pages 43-58, January.
    13. Relich Marcin, 2012. "An evaluation of project completion with application of fuzzy set theory," Management, Sciendo, vol. 16(1), pages 216-229, May.
    14. Réal Carbonneau & Gilles Caporossi & Pierre Hansen, 2014. "Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization," Journal of Classification, Springer;The Classification Society, vol. 31(2), pages 219-241, July.
    15. Robert Fourer & David M. Gay, 2002. "Extending an Algebraic Modeling Language to Support Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 322-344, November.
    16. Kevin C. Furman & Nicolas W. Sawaya & Ignacio E. Grossmann, 2020. "A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function," Computational Optimization and Applications, Springer, vol. 76(2), pages 589-614, June.
    17. Andrew J. Collins & Kasi Bharath Vegesana & Michael J. Seiler & Patrick O’Shea & Prasanna Hettiarachchi & Frederic McKenzie, 2013. "Simulation and mathematical programming decision-making support for smallholder farming," Environment Systems and Decisions, Springer, vol. 33(3), pages 427-439, September.
    18. Li Chen & Yinrun Lyu & Chong Wang & Jingzheng Wu & Changyou Zhang & Nasro Min-Allah & Jamal Alhiyafi & Yongji Wang, 2017. "Solving linear optimization over arithmetic constraint formula," Journal of Global Optimization, Springer, vol. 69(1), pages 69-102, September.
    19. Jian, Jinbao & Pan, Shanshan & Yang, Linfeng, 2019. "Solution for short-term hydrothermal scheduling with a logarithmic size mixed-integer linear programming formulation," Energy, Elsevier, vol. 171(C), pages 770-784.
    20. Daniel Jornada & V. Jorge Leon, 2020. "Filtering Algorithms for Biobjective Mixed Binary Linear Optimization Problems with a Multiple-Choice Constraint," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 57-73, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0602-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.