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. 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.
    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. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    5. 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.
    6. 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.
    7. 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.
    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. 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. 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.
    5. 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.
    6. 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.
    7. Tallys Yunes & Ionuţ D. Aron & J. N. Hooker, 2010. "An Integrated Solver for Optimization Problems," Operations Research, INFORMS, vol. 58(2), pages 342-356, April.
    8. Amin Hosseininasab & Willem-Jan van Hoeve, 2021. "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 721-738, May.
    9. 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.
    10. 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.
    11. 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.
    12. Gedik, Ridvan & Rainwater, Chase & Nachtmann, Heather & Pohl, Ed A., 2016. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals," European Journal of Operational Research, Elsevier, vol. 251(2), pages 640-650.
    13. 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.
    14. Joey Huchette & Joey Huchette, 2019. "A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 793-820, August.
    15. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    16. 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.
    17. Relich Marcin, 2012. "An evaluation of project completion with application of fuzzy set theory," Management, Sciendo, vol. 16(1), pages 216-229, May.
    18. Peter Kirst & Oliver Stein, 2019. "Global optimization of generalized semi-infinite programs using disjunctive programming," Journal of Global Optimization, Springer, vol. 73(1), pages 1-25, January.
    19. 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.
    20. Patrick Mehlitz, 2020. "A comparison of solution approaches for the numerical treatment of or-constrained optimization problems," Computational Optimization and Applications, Springer, vol. 76(1), pages 233-275, May.

    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.