Nothing Special   »   [go: up one dir, main page]

skip to main content
article

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

Published: 01 April 2018 Publication History

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.

References

[1]
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1998)
[2]
Lodi, A.: Mixed integer programming computation. In: Jnger, M., Liebling, TM., Naddef, D., Nemhauser, GL., Pulleyblank, WR., Reinelt, G., Rinaldi, G., Wolsey, LA. (eds.) 50 Years of Integer Programming 1958---2008, pp. 619---645. Springer (2010)
[3]
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
[4]
Hooker, J.N., Osorio, M.A.: Mixed logical-linear programming. Discrete Appl. Math. 96, 395---442 (1999)
[5]
Chen, L., Lyu, Y., Wang, C., Wu, J., Zhang, C., Min-Allah, N., Alhiyafi, J., Wang, Y.: Solving linear optimization over arithmetic constraint formula. J. Glob. Optim. 69, 1---34 (2017)
[6]
Sebastiani, R., Tomasi, S.: Optimization modulo theories with linear rational costs. ACM Trans. Comput. Log. (TOCL) 16(2), 12 (2015)
[7]
Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. MSRR No. 330 (1974)
[8]
Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89(1), 3---44 (1998)
[9]
Raman, R., Grossmann, I.E.: Modelling and computational techniques for logic based integer programming. Comput. Chem. Eng. 18(7), 563---578 (1994)
[10]
Vecchietti, A., Grossmann, I.: Computational experience with LogMIP solving linear and nonlinear disjunctive programming problems. In: Proceeding of FOCAPD, pp. 587---590. Citeseer (2004)
[11]
Sawaya, N., Grossmann, I.: A hierarchy of relaxations for linear generalized disjunctive programming. Eur. J. Oper. Res. 216(1), 70---82 (2012)
[12]
Trespalacios, F., Grossmann, I.E.: Algorithmic approach for improved mixed-integer reformulations of convex generalized disjunctive programs. INFORMS J. Comput. 27(1), 59---74 (2014)
[13]
Trespalacios, F., Grossmann, I.E.: Cutting plane algorithm for convex generalized disjunctive programs. INFORMS J. Comput. 28(2), 209---222 (2016)
[14]
Kirst, P., Rigterink, F., Stein, O.: Global optimization of disjunctive programs. J. Glob. Optim. 69, 1---25 (2017)
[15]
Ruiz, J.P., Grossmann, I.E.: Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques. J. Glob. Optim. 67(1), 43---58 (2017)
[16]
Barrett, C., Tinelli, C.: Satisfiability modulo theories. In: Biere, A., Heule, M., van Maaren, H. (eds.) Handbook of Satisfiability, vol. 185, pp. 825---885. IOS Press (2009)
[17]
De Moura, L., BjØrner, N.: Satisfiability modulo theories: introduction and applications. Commun. ACM 54(9), 69---77 (2011)
[18]
Monniaux, D.: A survey of satisfiability modulo theory. In: International Workshop on Computer Algebra in Scientific Computing, pp. 401---425. Springer (2016)
[19]
Silva, J.P.M., and Sakallah, K.A.: GRASP: a new search algorithm for satisfiability. In: Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, pp. 220---227. IEEE Computer Society (1997)
[20]
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: engineering an efficient sat solver. In: Proceedings of the 38th Annual Design Automation Conference, pp. 530---535. ACM (2001)
[21]
Gomes, C.P., Selman, B., Kautz, H., et al.: Boosting combinatorial search through randomization. In: AAAI/IAAI, vol. 98, pp. 431---437 (1998)
[22]
Goldberg, E., Novikov, Y.: BerkMin: a fast and robust sat-solver. Discrete Appl. Math. 155(12), 1549---1561 (2007)
[23]
Hooker, J.N.: Logic, optimization, and constraint programming. INFORMS J. Comput. 14(4), 295---321 (2002)
[24]
Meseguer, P.: Interleaved depth-first search. In: IJCAI, vol. 97, pp. 1382---1387 (1997)
[25]
Plaisted, D.A., Greenbaum, S.: A structure-preserving clause form translation. J. Symb. Comput. 2(3), 293---304 (1986)
[26]
de la Tour, T.B.: An optimality result for clause form translation. J. Symb. Comput. 14(4), 283---301 (1992)
[27]
Li, Y., Albarghouthi, A., Kincaid, Z., Gurfinkel, A., Chechik, M.: Symbolic optimization with SMT solvers. In: ACM SIGPLAN Notices, vol. 49, pp. 607---618. ACM (2014)
[28]
Sebastiani, R., Tomasi, S.: Optimization in SMT with $${\cal{LA}}({\mathbb{Q}})$$LA(Q) cost functions. In: Gramlich, B., Miller, D., Sattler, U. (eds.) Automated Reasoning, pp. 484---498. Springer (2012)
[29]
Sawaya, N.W., Grossmann, I.E.: A cutting plane method for solving linear generalized disjunctive programming problems. Comput. Chem. Eng. 29(9), 1891---1913 (2005)
[30]
Trespalacios, F., Grossmann, I.E.: Improved Big-M reformulation for generalized disjunctive programs. Comput. Chem. Eng. 76, 98---103 (2015)
[31]
Vielma, J.P.: Mixed integer linear programming formulation techniques. SIAM Rev. 57(1), 3---57 (2015)
[32]
Liu, J., Wang, Y., Wang, Y., Xing, J., Zeng, H.: Real-time system design based on logic or constrained optimization. J. Softw. 17(7), 1641---1649 (2006)
[33]
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM (JACM) 20(1), 46---61 (1973)
[34]
Min-Allah, N., Khan, S.U., Yongji, W.: Optimal task execution times for periodic tasks using nonlinear constrained optimization. J. Supercomput. 59(3), 1120---1138 (2012)
[35]
Bini, E., Buttazzo, G.C.: The space of rate monotonic schedulability. In: 23rd IEEE on Real-Time Systems Symposium, 2002. RTSS 2002, pp. 169---178. IEEE (2002)
[36]
Fang, S., Li, G.: Solving fuzzy relation equations with a linear objective function. Fuzzy Sets Syst. 103(1), 107---113 (1999)
[37]
Ghodousian, A., Khorram, E.: Fuzzy linear optimization in the presence of the fuzzy relation inequality constraints with max---min composition. Inf. Sci. 178(2), 501---519 (2008)
[38]
Su, C., Guo, F.: Solving interval-valued fuzzy relation equations with a linear objective function. In: International Conference on Fuzzy Systems and Knowledge Discovery, pp. 380---385 (2009)
[39]
Guo, F., Pang, L., Meng, D., Xia, Z.: An algorithm for solving optimization problems with fuzzy relational inequality constraints. Inf. Sci. 252, 20---31 (2013)
[40]
Miyagi, H., Kinjo, I., Fan, Y.: Qualified decision-making using the fuzzy relation inequalities. In: IEEE International Conference on Systems, Man, and Cybernetics, vol. 2, pp. 2014---2018 (1998)
[41]
Wang, H., Wang, C.H.: A fixed-charge model with fuzzy inequality constraints composed by max-product operator. Comput. Math. Appl. 36(7), 23---29 (1998)

Cited By

View all
  • (2023)Indian sign language recognition system using network deconvolution and spatial transformer networkNeural Computing and Applications10.1007/s00521-023-08860-y35:28(20889-20907)Online publication date: 1-Oct-2023
  • (2019)Effect of ordered set on feasibility analysis of static-priority systemThe Journal of Supercomputing10.1007/s11227-018-02742-075:1(475-487)Online publication date: 1-Jan-2019
  1. An interleaved depth-first search method for the linear optimization problem with disjunctive constraints

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Journal of Global Optimization
      Journal of Global Optimization  Volume 70, Issue 4
      April 2018
      205 pages

      Publisher

      Kluwer Academic Publishers

      United States

      Publication History

      Published: 01 April 2018

      Author Tags

      1. Disjunctive programming
      2. Global optimization
      3. Optimization modulo theories
      4. Search algorithm

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 25 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)Indian sign language recognition system using network deconvolution and spatial transformer networkNeural Computing and Applications10.1007/s00521-023-08860-y35:28(20889-20907)Online publication date: 1-Oct-2023
      • (2019)Effect of ordered set on feasibility analysis of static-priority systemThe Journal of Supercomputing10.1007/s11227-018-02742-075:1(475-487)Online publication date: 1-Jan-2019

      View Options

      View options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media