×

Decomposition of loosely coupled integer programs: a multiobjective perspective. (English) Zbl 1506.90160

Summary: We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. In this paper, we exploit the idea of resource-directive decomposition to reformulate the problem so that it can be decomposed into a resource-directive master problem and a set of multiobjective programming subproblems. Recent methods developed for solving multiobjective problems enable us to formulate a relaxation of the master problem that is an IP whose solution yields a dual bound on the value of the original IP. This perspective provides a new, general framework for IP decomposition, in which many alternative algorithm designs are possible. Here, we develop one such algorithm, and demonstrate its viability and potential benefits with the aid of computational experiments knapsack-based instances with up to five coupling constraints and 7500 variables, comparing it with both a standard IP solver and a generic branch-and-price solver.

MSC:

90C10 Integer programming
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, S.; Tawarmalani, M.; Sahinidis, N., A finite branch and bound algorithm for two-stage stochastic integer programs, Math. Program., 100, 2, 355-377 (2004) · Zbl 1068.90084
[2] Balas, E., Disjunctive programming, Ann. Discrete Math., 5, 3-51 (1979) · Zbl 0409.90061
[3] Balas, E., Disjunctive programming: properties of the convex hull of feasible points, Discrete Appl. Math., 89, 1-3, 3-44 (1998) · Zbl 0921.90118
[4] Balas, E., Disjunctive Programming (2018), Berlin: Springer, Berlin · Zbl 1414.90001
[5] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 1-3, 295-324 (1993) · Zbl 0796.90041
[6] Balas, E.; Margot, F., Generalized intersection cuts and a new cut generating paradigm, Math. Program., 137, 1-2, 19-35 (2013) · Zbl 1262.90099
[7] Barnhart, C.; Johnson, E.; Nemhauser, G.; Savelsbergh, M.; Vance, P., Branch-and-price: column generation for solving huge integer programs, Oper. Res., 46, 3, 316-329 (1998) · Zbl 0979.90092
[8] Bergman, D., Bodur M., Cardonha C., Cire A.A.: Network models for multiobjective discrete optimization. Informs J. Comput. (2021)
[9] Boland, N.; Charkhgard, H.; Savelsbergh, M., A criterion space search algorithm for biobjective integer programming: the balanced box method, INFORMS J. Comput., 27, 4, 735-754 (2015) · Zbl 1338.90365
[10] Boland, N.; Charkhgard, H.; Savelsbergh, M., The L-shape search method for triobjective integer programming, Math. Program. Comput., 8, 2, 217-251 (2016) · Zbl 1338.90366
[11] Boyd, E.A.: The Lagrangian and other primal cutting planes for linear integer programming problems. Technical Report TR90-3, Rice University, Department of Mathematical Sciences (1990)
[12] Boyd, EA, Fenchel cutting planes for integer programs, Oper. Res., 42, 1, 53-64 (1994) · Zbl 0809.90104
[13] Chen, Q.; Grossmann, I., Modern modeling paradigms using generalized disjunctive programming, Processes, 7, 11, 839 (2019)
[14] Dächert, K.; Klamroth, K., A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems, J. Global. Opt., 61, 1-34 (2015) · Zbl 1338.90369
[15] Dantzig, G.; Wolfe, P., Decomposition principle for linear programs, Oper. Res., 8, 1, 101-111 (1960) · Zbl 0093.32806
[16] Desaulniers, G.; Desrosiers, J.; Solomon, M., Column Generation (2006), Berlin: Springer, Berlin · Zbl 1084.90002
[17] Ehrgott, M., Multicriteria Optimization (2006), Berlin: Springer, Berlin · Zbl 0956.90039
[18] Ehrgott, M., Gandibleux, X., Przybylski, A.: Exact methods for multi-objective combinatorial optimisation. In: Multiple Criteria Decision Analysis, 2nd edn., pp. 817-850. Springer (2016)
[19] Floudas, C.; Pardalos, P., Encyclopedia of Optimization (2008), Berlin: Springer, Berlin · Zbl 1156.90001
[20] Gao, C.; Lu, G.; Yao, X.; Li, J., An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem, Eur. J. Oper. Res., 260, 1, 1-11 (2017) · Zbl 1402.90146
[21] Geoffrion, A.: Lagrangian relaxation for integer programming. In: 50 Years of Integer Programming 1958-2008, pp. 243-281. Springer (2010) · Zbl 1187.90010
[22] Grossmann, IE; Trespalacios, F., Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming, AIChE J., 59, 9, 3276-3295 (2013)
[23] Jozefowiez, N.; Laporte, G.; Semet, F., A generic branch-and-cut algorithm for multiobjective optimization problems: application to the multilabel traveling salesman problem, INFORMS J. Comput., 24, 4, 554-564 (2012) · Zbl 1462.90120
[24] Kazachkov, A.M.: Non-recursive Cut Generation. Ph.D. Thesis, Carnegie-Mellon University (2018)
[25] Khan, S.; Li, K.; Manning, E.; Akbar, M., Solving the knapsack problem for adaptive multimedia systems, Stud. Inform. Univ., 2, 1, 157-178 (2002)
[26] Kong, N.; Schaefer, A.; Hunsaker, B., Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach, Math. Program., 108, 2, 275-296 (2006) · Zbl 1130.90378
[27] Molina, F., A survey of resource directive decomposition in mathematical programming, ACM Comput. Surv., 11, 2, 95-104 (1979)
[28] Morrison, DR; Jacobson, SH; Sauppe, JJ; Sewell, EC, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Discrete Optim., 19, 79-102 (2016) · Zbl 1387.90010
[29] Nemhauser, G., Decomposition of linear programs by dynamic programming, Naval Res. Logist. Quart., 11, 2, 191-195 (1964) · Zbl 0136.14105
[30] Nemhauser, GL; Wolsey, LA, Integer and Combinatorial Optimization (1988), New York: Wiley, New York · Zbl 0652.90067
[31] Özlen, M.; Burton, BA; MacRae, CAG, Multi-objective integer programming: an improved recursive algorithm, J. Optim. Theory Appl., 160, 2, 470-482 (2014) · Zbl 1300.90044
[32] Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., Automation and combination of linear-programming based stabilization techniques in column generation, INFORMS J. Comput., 30, 2, 339-360 (2018) · Zbl 1528.90164
[33] Przybylski, A.; Gandibleux, X.; Ehrgott, M., A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives, Discrete Optim., 7, 3, 149-165 (2010) · Zbl 1241.90138
[34] Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Oper. Res., 45, 6, 831-841 (1997) · Zbl 0895.90161
[35] Sawaya, NW; Grossmann, IE, A cutting plane method for solving linear generalized disjunctive programming problems, Comput. Chem. Eng., 29, 9, 1891-1913 (2005)
[36] Soylu, B., The search-and-remove algorithm for biobjective mixed-integer linear programming problems, Eur. J. Oper. Res., 268, 1, 281-299 (2018) · Zbl 1403.90617
[37] Trapp, A.; Prokopyev, O.; Schaefer, A., On a level-set characterization of the value function of an integer program and its application to stochastic programming, Oper. Res., 61, 2, 498-511 (2013) · Zbl 1267.90074
[38] Trespalacios, F.; Grossmann, IE, Review of mixed-integer nonlinear and generalized disjunctive programming methods, Chem. Ing. Tech., 86, 7, 991-1012 (2014)
[39] Trespalacios, F., Grossmann, I.E.: Chapter 24: Review of mixed-integer nonlinear optimization and generalized disjunctive programming applications in process systems engineering. In: Advances and Trends in Optimization with Engineering Applications pp. 315-329 (2017)
[40] Vanderbeck, F., On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm, Oper. Res., 48, 1, 111-128 (2000) · Zbl 1106.90360
[41] Vanderbeck, F., Branching in branch-and-price: a generic scheme, Math. Program., 130, 2, 249-294 (2011) · Zbl 1229.90100
[42] Vanderbeck, F.; Savelsbergh, M., A generic view of Dantzig-Wolfe decomposition in mixed integer programming, Oper. Res. Lett., 34, 3, 296-306 (2006) · Zbl 1109.90062
[43] Zhang, W.; Reimann, M., A simple augmented \(\varepsilon \)-constraint method for multi-objective mathematical integer programming problems, Eur. J. Oper. Res., 234, 1, 15-24 (2014) · Zbl 1305.90378
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.