article

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

Authors:

Changyou Zhang,

Nasro Min-Allah,

Yongji WangAuthors Info & Claims

Journal of Global Optimization, Volume 70, Issue 4

Pages 737 - 756

https://doi.org/10.1007/s10898-017-0602-1

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)

Digital Library

[4]

Hooker, J.N., Osorio, M.A.: Mixed logical-linear programming. Discrete Appl. Math. 96, 395---442 (1999)

Digital Library

[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)

Digital Library

[6]

Sebastiani, R., Tomasi, S.: Optimization modulo theories with linear rational costs. ACM Trans. Comput. Log. (TOCL) 16(2), 12 (2015)

Digital Library

[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)

Digital Library

[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)

Digital Library

[13]

Trespalacios, F., Grossmann, I.E.: Cutting plane algorithm for convex generalized disjunctive programs. INFORMS J. Comput. 28(2), 209---222 (2016)

Digital Library

[14]

Kirst, P., Rigterink, F., Stein, O.: Global optimization of disjunctive programs. J. Glob. Optim. 69, 1---25 (2017)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[21]

Gomes, C.P., Selman, B., Kautz, H., et al.: Boosting combinatorial search through randomization. In: AAAI/IAAI, vol. 98, pp. 431---437 (1998)

Digital Library

[22]

Goldberg, E., Novikov, Y.: BerkMin: a fast and robust sat-solver. Discrete Appl. Math. 155(12), 1549---1561 (2007)

Digital Library

[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)

Digital Library

[25]

Plaisted, D.A., Greenbaum, S.: A structure-preserving clause form translation. J. Symb. Comput. 2(3), 293---304 (1986)

Digital Library

[26]

de la Tour, T.B.: An optimality result for clause form translation. J. Symb. Comput. 14(4), 283---301 (1992)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[36]

Fang, S., Li, G.: Solving fuzzy relation equations with a linear objective function. Fuzzy Sets Syst. 103(1), 107---113 (1999)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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)

Digital Library

[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

Ghorai ANandi UChangdar CSi TSingh MMondal J(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
https://dl.acm.org/doi/10.1007/s00521-023-08860-y
Min-Allah N(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
https://dl.acm.org/doi/10.1007/s11227-018-02742-0

An interleaved depth-first search method for the linear optimization problem with disjunctive constraints
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Solving linear optimization over arithmetic constraint formula

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or ...
Global optimization of bilinear programs with a multiparametric disaggregation technique

In this paper, we present the derivation of the multiparametric disaggregation technique (MDT) by Teles et al. (J. Glob. Optim., 2011 ) for solving nonconvex bilinear programs. Both upper and lower bounding formulations corresponding to mixed-integer ...
Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of ...

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

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ghorai ANandi UChangdar CSi TSingh MMondal J(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
https://dl.acm.org/doi/10.1007/s00521-023-08860-y
Min-Allah N(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
https://dl.acm.org/doi/10.1007/s11227-018-02742-0

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents