One-parametric analysis of column-oriented linear programs

Larsson, Torbjörn; Quttineh, Nils-Hassan Article One-parametric analysis of column-oriented linear programs Operations Research Perspectives Provided in Cooperation with: Elsevier Suggested Citation: Larsson, Torbjörn; Quttineh, Nils-Hassan (2023) : One-parametric analysis of column-oriented linear programs, Operations Research Perspectives, ISSN 2214-7160, Elsevier, Amsterdam, Vol. 10, pp. 1-6, https://doi.org/10.1016/j.orp.2023.100278 This Version is available at: https://hdl.handle.net/10419/325764 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Operations Research Perspectives 10 (2023) 100278 Available online 6 May 2023 2214-7160/© 2023 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). Contents lists available at ScienceDirect Operations Research Perspectives journal homepage: www.elsevier.com/locate/orp One-parametric analysis of column-oriented linear programs Torbjörn Larsson, Nils-Hassan Quttineh∗ Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden ARTICLE INFO MSC: 90C05 90C31 90C10 90C29 Keywords: Linear programming Parametric optimization Column generation Dantzig–Wolfe decomposition Bi-objective discrete optimization ABSTRACT A linear optimization problem which is amenable to column generation and contains a single parameter in the objective function is considered. We extend and adapt the standard linear programming column generation scheme to effectively and efficiently solve this problem for all values of the parameter. As a potential application we consider bi-objective discrete optimization and describe how the one-parametric column generation scheme can be used to form an outer approximation of the Pareto frontier for such a problem. 1. Derivation The field of sensitivity and parametric analyses in linear programming is well established since several decades. Such analyses are however typically performed for explicitly given linear programs. In contrast, we make a parametric analysis with respect to a single parameter in the objective function of a linear program that is not explicitly known and can be solved only by means of a column generation procedure. We give a precise algorithm for such an analysis; to the best of our knowledge, there is no previous method for doing this. The parametric analysis is inspired by results within the field of fractional optimization. In the following the reader is assumed to be well acquainted with linear programming and the column generation principle, and is otherwise referred to, for example, [1,2]. Let 𝜆∈R+,𝑐𝑗(𝜆) = 𝑐𝑗+𝜆𝛥𝑐𝑗, with 𝑐𝑗∈Rand 𝛥𝑐𝑗∈R,𝑗= 1,…, 𝑁. Let further 𝐴𝑗∈R𝑚,𝑗= 1,…, 𝑁, and 𝑏∈R𝑚, and consider the one-parametric linear optimization problem 𝑧∗(𝜆) = min 𝑁 ∑ 𝑗=1 𝑐𝑗(𝜆)𝑥𝑗(1a) s.t. 𝑁 ∑ 𝑗=1 𝐴𝑗𝑥𝑗=𝑏, (1b) 𝑥𝑗≥0, 𝑗 = 1,…, 𝑁, (1c) which is assumed to have a non-empty and bounded set of feasible solutions. If the feasible set has 𝑃extreme points, denoted by 𝑥𝑝, ∗Corresponding author. E-mail address: [email protected] (N.-H. Quttineh). 𝑝= 1,…, 𝑃 , we obtain that 𝑧∗(𝜆) = min 𝑝=1,…,𝑃 {𝑁 ∑ 𝑗=1 𝑐𝑗𝑥𝑝 𝑗+𝜆 𝑁 ∑ 𝑗=1 𝛥𝑐𝑗𝑥𝑝 𝑗}, which reveals that the function 𝑧∗∶R+↦Ris the pointwise minimum of a finite number of linear functions. Hence it is finite, piecewise linear and concave on its domain; clearly, each piece corresponds to a certain extreme point being optimal and the number of breakpoints is finite. Assume further that 𝑁is huge, but that the set of columns, 𝐴= {𝐴1,…, 𝐴𝑁}, and their corresponding cost coefficients, 𝑐(𝑎)and 𝛥𝑐(𝑎), 𝑎∈𝐴, with 𝑐(𝐴𝑗) = 𝑐𝑗and 𝛥𝑐(𝐴𝑗) = 𝛥𝑐𝑗,𝑗= 1,…, 𝑁, can be characterized in a compact way. Further, for any value of 𝜆∈R+and any constant vector 𝑦∈R𝑚it shall be possible to solve the column generation problem min 𝑎∈𝐴{𝑐(𝑎) + 𝜆𝛥𝑐(𝑎) − 𝑦T𝑎}(2) without making an explicit enumeration of the columns, but by instead solving some application-specific optimization problem by a tailored algorithm. This means that the one-parametric linear optimization problem is, for a fixed value of 𝜆, amenable to a column generation approach. The set 𝐴is then typically described by linear constraints and integrality restrictions, while 𝑐(𝑎)and 𝛥𝑐(𝑎),𝑎∈𝐴, are costs associated with the integer points satisfying the linear constraints. Remark 1. A one-parametric optimization model of the form (1) may for example arise from a linear bi-objective column-oriented model https://doi.org/10.1016/j.orp.2023.100278 Received 12 November 2022; Received in revised form 30 April 2023; Accepted 3 May 2023 Operations Research Perspectives 10 (2023) 100278 2 T. Larsson and N.-H. Quttineh which is approached by a weighted-sum scalarization. Let 𝑐1, 𝑐2∈R𝑁 be two cost vectors, let 𝑥∈R𝑁be the variable vector, and consider the objective to simultaneously minimize 𝑐T 1𝑥and 𝑐T 2𝑥. With 𝑤∈ [0,1], the scalarized single objective then becomes 𝑤𝑐T 1𝑥+ (1 − 𝑤)𝑐T 2𝑥= 𝑐T 2𝑥+𝑤(𝑐1−𝑐2)T𝑥, which is of the type (1a). Due to convexity, the solution of the scalarized linear optimization problem for all 𝑤∈ [0,1] will provide the entire Pareto frontier of the bi-objective problem. A precise algorithm for finding the function 𝑧∗is missing in the literature. A naive way would be to sample values of 𝜆and use straightforward column generation for each of them (and exploiting reoptimization facilities). This way would however not guarantee that all breakpoints are found (if the sampling is too coarse) and it can also be unnecessarily computationally demanding (if the sampling is finer than needed). Our goal is to enable an effective and efficient calculation of the breakpoints of 𝑧∗, even though the number of columns in the one-parametric linear optimization problem is huge, by deriving an extension of a standard column generation scheme. Let 𝜆∈R+and assume that column generation is used to find a basic feasible solution (BFS) that is verified to be optimal, that is, dual feasible, and let 𝐵(𝜆)be its basis matrix. Let 𝑐𝐵(𝜆)and 𝛥𝑐𝐵(𝜆)be the vectors of coefficients 𝑐𝑗and 𝛥𝑐𝑗, respectively, for the optimal basic variables, and let 𝑐𝐵(𝜆) = 𝑐𝐵(𝜆)+𝜆𝛥𝑐𝐵(𝜆). The dual feasible solution then is 𝑦(𝜆)T=𝑐𝐵(𝜆)T𝐵(𝜆)−1 and the reduced costs are 𝑐𝑗(𝜆) = 𝑐𝑗(𝜆) − 𝑦(𝜆)T𝐴𝑗≥0,𝑗= 1,…, 𝑁. We now consider a fixed value  𝜆∈R++ and the problem of finding the largest value of 𝜆such that a BFS that is verified to be optimal at  𝜆 remains verified optimal, that is, dual feasible since primal feasibility is clearly not affected by 𝜆. For this purpose we let 𝛿=𝜆− 𝜆∈R+. The following result, which is easily verified, is instrumental for the analysis. Proposition 2. Given a dual feasible BFS at  𝜆∈R++. In this basis it then holds that 𝑐𝑗( 𝜆+𝛿) = 𝑐𝑗( 𝜆) + 𝛿𝛥 𝑐𝑗( 𝜆),𝑗= 1,…, 𝑁, where 𝛥 𝑐𝑗( 𝜆) = 𝛥𝑐𝑗−𝛥𝑦( 𝜆)T𝐴𝑗with 𝛥𝑦( 𝜆)T=𝛥𝑐T 𝐵( 𝜆)𝐵( 𝜆)−1. Notice that, by construction, 𝑐𝑗( 𝜆+𝛿)=0holds for all basic variables and for all 𝛿∈R+. The largest value of 𝛿that maintains dual feasibility is  𝛿= max{𝛿∈R+∣𝑐𝑗( 𝜆) + 𝛿𝛥 𝑐𝑗( 𝜆)≥0, 𝑗 = 1,…, 𝑁}.(3) If 𝑁were of moderate size, and problem (1) were known explicitly, then  𝛿could be calculated in the straightforward way  𝛿= min 𝑗=1,…,𝑁 {−𝑐𝑗( 𝜆) 𝛥 𝑐𝑗( 𝜆)||||| 𝛥 𝑐𝑗( 𝜆)<0}. But because 𝑁is huge,  𝛿can clearly not be calculated like this. We instead find  𝛿by studying the function ℎ∶R+↦Rwith ℎ(𝛿) = min 𝑗=1,…,𝑁 {𝑐𝑗( 𝜆) + 𝛿𝛥 𝑐𝑗( 𝜆)}.(4) This function is clearly finite, piecewise linear and concave on its domain, and has a finite number of breakpoints. Since 𝑐𝑗( 𝜆)+𝛿𝛥 𝑐𝑗( 𝜆)=0 holds for all basic variables and all 𝛿∈R+, it holds that ℎ(0) = 0 and that ℎ(𝛿)≤0for all 𝛿∈R+. Let ℎ′ min denote the most negative slope of this function. Obviously, ℎ′ min = min 𝑗=1,…,𝑁 𝛥 𝑐𝑗( 𝜆).(5) If ℎ′ min ≮0, then 𝑐𝑗( 𝜆) + 𝛿𝛥 𝑐𝑗( 𝜆)≥0holds for all 𝑗= 1,…, 𝑁 and all 𝛿∈R+. Hence, ℎ′ min ≮0means that  𝛿= +∞, that dual feasibility holds for all 𝛿∈R+, and that the optimal BFS at  𝜆remains optimal for all 𝜆 >  𝜆. If ℎ′ min <0, then  𝛿is finite and from the definition of the function ℎfollows that  𝛿= max{𝛿∈R+∣ℎ(𝛿) = 0}. As is well known, if the optimal BFS is non-degenerate, then the condition 𝑐𝑗( 𝜆+𝛿)≥0, Fig. 1. Illustration of the function ℎand Newton’s method. 𝑗= 1,…, 𝑁, is both necessary and sufficient for maintained optimality, but in case the solution is degenerate, it is only sufficient. In the case of non-degeneracy, the value  𝜆+ 𝛿yields the smallest breakpoint of 𝑧∗that is larger than  𝜆, but in the case of degeneracy this value may just yield a degenerate change of basis, which leaves the primal feasible solution unchanged. In the latter case,  𝜆+ 𝛿is not a breakpoint of 𝑧∗, but just indicates a transition to a new primal and dual feasible basis for one and the same extreme point. In order to find the finite  𝛿, we suggest using Newton’s method on the piecewise linear equation ℎ(𝛿)=0. Let 𝛿𝑘∈R++ be an iterate and 𝑗(𝛿𝑘) ∈ arg min 𝑗=1,…,𝑁 {𝑐𝑗( 𝜆) + 𝛿𝑘𝛥 𝑐𝑗( 𝜆)}, giving ℎ(𝛿𝑘) = 𝑐𝑗(𝛿𝑘)( 𝜆) + 𝛿𝑘𝛥 𝑐𝑗(𝛿𝑘)( 𝜆). Suppose that ℎ(𝛿𝑘)<0. Since 𝛿𝑘is on a linear piece of ℎwith slope 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆), a Newton update gives the next iterate 𝛿𝑘+1 =𝛿𝑘−ℎ(𝛿𝑘) 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)=𝛿𝑘−𝑐𝑗(𝛿𝑘)( 𝜆) + 𝛿𝑘𝛥 𝑐𝑗(𝛿𝑘)( 𝜆) 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)= − 𝑐𝑗(𝛿𝑘)( 𝜆) 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆).(6) The function ℎand the progress of Newton’s method for finding its zero are illustrated in Fig. 1. Proposition 3. Given any initial iterate 𝛿0∈R++ with ℎ(𝛿0)<0, Newton’s method on the piecewise linear equation ℎ(𝛿) = 0 generates an iteration sequence 𝛿𝑘∈R+,𝑘= 0,1,2,…, that is monotonically decreasing and finitely converges to the value  𝛿, as defined in (3). Proof. Throughout the proof it is assumed that ℎ(𝛿𝑘)<0. By using 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆) ∈ 𝜕ℎ(𝛿𝑘)in the subgradient-defining inequality for ℎat 𝛿𝑘we obtain that ℎ(𝛿)≤ℎ(𝛿𝑘) + 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)(𝛿−𝛿𝑘)holds for all 𝛿∈R+. The choice 𝛿= 0 gives that 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)≤ℎ(𝛿𝑘)∕𝛿𝑘<0. From the update (6) then follows that 𝛿𝑘+1 < 𝛿𝑘. Since 𝑐𝑗(𝛿𝑘)( 𝜆)≥0, it also follows from (6) that 𝛿𝑘+1 ≥0. To prove finite convergence we show that the method will in each iteration exclude at least one linear piece of ℎfrom further consideration in the search for its zero. We first consider the case that 𝛿𝑘is not a breakpoint of ℎand again use that 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆) ∈ 𝜕ℎ(𝛿𝑘). Assume that 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆) ∈ 𝜕ℎ(𝛿𝑘+1). Using the subgradient-defining inequality for ℎat 𝛿𝑘and 𝛿𝑘+1, for the choices 𝛿=𝛿𝑘+1 and 𝛿=𝛿𝑘, respectively, gives that ℎ(𝛿𝑘+1) = ℎ(𝛿𝑘) + 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)(𝛿𝑘+1 −𝛿𝑘). By inserting the expression for 𝛿𝑘+1 according to (6), it follows that ℎ(𝛿𝑘+1)=0, so that the method terminates. Hence, if ℎ(𝛿𝑘+1)<0, then 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆) ∉ 𝜕ℎ(𝛿𝑘+1), implying that 𝛿𝑘+1 is not on the piece of ℎwhere 𝛿𝑘is located. Further, since the iterates are monotonically decreasing, no subsequent iterate can be located on that piece of ℎ. In the case that 𝛿𝑘is a breakpoint of ℎ, we may instead conclude that no subsequent iterate can be located on the piece of ℎwhich has its lower endpoint at 𝛿𝑘, by again using that the iterates are monotonically decreasing. From the update (6) follows that ℎ(𝛿𝑘) = 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)(𝛿𝑘−𝛿𝑘+1), and therefore ℎ(𝛿)≤ℎ(𝛿𝑘) + 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)(𝛿−𝛿𝑘) = 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)(𝛿−𝛿𝑘+1)holds Operations Research Perspectives 10 (2023) 100278 3 T. Larsson and N.-H. Quttineh for all 𝛿∈R+. Suppose that ℎ(𝛿) = 0 holds for some 𝛿∈R+. Since 𝛥 𝑐𝑗(𝛿𝑘)( 𝜆)<0, it must then hold that 𝛿≤𝛿𝑘+1. Hence, if ℎ(𝛿𝑘+1) = 0 holds, then 𝛿≤𝛿𝑘+1 holds for all other zeros of ℎ, and therefore 𝛿𝑘+1 = 𝛿.□ The construction of the function ℎand the use of Newton’s method to find its zero  𝛿are inspired by results within fractional optimization, see e.g. [3,4]. From the assumption that the linear program is amenable to column generation, it follows that the calculation of the value of the function ℎin (4) can be replaced by the column generation problem 𝑎(𝛿) ∈ arg min 𝑎∈𝐴{𝑐(𝑎)+( 𝜆+𝛿)𝛥𝑐(𝑎) − (𝑦( 𝜆) + 𝛿𝛥𝑦( 𝜆))T𝑎},(7) for the application under consideration, and the calculation ℎ(𝛿) = 𝑐(𝑎(𝛿)) + (  𝜆+𝛿)𝛥𝑐(𝑎(𝛿)) − (𝑦( 𝜆) + 𝛿𝛥𝑦( 𝜆))T𝑎(𝛿).(8) Similarly, the calculation (5) amounts to solving the column generation problem min𝑎∈𝐴{𝛥𝑐(𝑎) − 𝛥𝑦( 𝜆)T𝑎}. We are now in the position to state a procedure for solving the one-parametric linear optimization problem by column generation. The breakpoints between optimal bases are denoted by 𝜆0, 𝜆1, 𝜆2,…, where we define 𝜆0= 0 (although it is not likely to be a proper breakpoint). In order to make the transition from one dual feasible basis to the next, a very small step 𝜀 > 0is taken beyond each breakpoint 𝜆𝑝,𝑝= 0,1,2,…. In case it is determined that  𝛿is finite, Newton’s method is initialized at a 𝛿0such that ℎ(𝛿0)<0holds. (Such a 𝛿0can for example be found by starting with a tentative value and then, if needed, doubling the value until the condition holds.) The complete parametric procedure is summarized in Algorithm 1. The algorithm will clearly find all the breakpoints of the function 𝑧∗. Notice that some of the breakpoints 𝜆𝑝 may not be actual breakpoints of 𝑧∗, but may instead correspond to a change of dual feasible basis at a degenerate extreme point. Algorithm 1 One-Parametric Column Generation input: a one-parametric column-oriented linear program output: breakpoints 𝜆0, 𝜆1, 𝜆2,…, and an optimal basis for each interval let 𝑝= 0 and 𝜆0= 0 loop let  𝜆=𝜆𝑝+𝜀 apply column generation to solve the linear program for 𝜆= 𝜆 record the optimal basis found apply column generation to find ℎ′ min = min𝑎∈𝐴{𝛥𝑐(𝑎) − 𝛥𝑦( 𝜆)T𝑎} if ℎ′ min <0then let 𝑘= 0 and use the column generation problem (7) and the expression (8) to find a 𝛿0such that ℎ(𝛿0)<0 while ℎ(𝛿𝑘)<0do let 𝛿𝑘+1 = − 𝑐(𝑎(𝛿𝑘)) +  𝜆𝛥𝑐(𝑎(𝛿𝑘)) − 𝑦( 𝜆)T𝑎(𝛿𝑘) 𝛥𝑐(𝑎(𝛿𝑘)) − 𝛥𝑦( 𝜆)T𝑎(𝛿𝑘) solve the column generation problem (7) for 𝛿=𝛿𝑘+1 use the expression (8) for 𝛿=𝛿𝑘+1 to calculate ℎ(𝛿𝑘+1) let 𝑘=𝑘+ 1 end while let 𝜆𝑝+1 = 𝜆+𝛿𝑘 let 𝑝=𝑝+ 1 else terminate end if end loop In column generation approaches, all columns that are generated are commonly accumulated in the restricted master problem. When the parametric solution procedure terminates, this problem will then clearly contain all columns needed to find verified optimal solutions for all 𝜆∈R+. Remark 4. In case the parameter values of interest are bounded from above, like in the application discussed in Remark 1, the algorithm can be simplified. Suppose that the range of interest is 𝜆∈ [0, 𝐿], where 𝐿∈R++. Then the calculations of ℎ′ min and 𝛿0can be replaced by the calculation of ℎ(𝐿− 𝜆). If ℎ(𝐿− 𝜆)≮0holds, then the algorithm terminates, and otherwise we let 𝛿0=𝐿− 𝜆. Remark 5. If the original one-parametric linear optimization problem includes columns from several categories, such that several column generation problems are obtained, then the analysis of the function ℎ separates over these column categories, and the value  𝛿is determined as the smallest of the values obtained from the separate categories. Since Dantzig–Wolfe decomposition is simply an application of the general column generation principle, our approach is directly applicable to one-parametric linear optimization problems with complicating side constraints, and in particular to one-parametric block-angular linear programs. The work found in the literature that is closest to ours is by Moradi et al. [5]; it presents a column generation, Dantzig–Wolfe type method for finding the Pareto frontier for the bi-objective multi-commodity minimum cost network flow problem. This problem is a special case of a block-angular linear program and it should be straightforward to extend the method in [5] to any such linear program. This method uses the bi-objective simplex method, fractional linear programming and the Charnes–Cooper transformation of a fractional linear program into a standard linear programming problem; hence, it relies fully on linear programming techniques. In a straightforward application of the Dantzig–Wolfe decomposition principle to a single-objective multi-commodity minimum cost network flow problem, the column generation problems are singlecommodity minimum cost flow problem, but in the method in [5] the column generation problems are instead one-parametric side constrained single-commodity minimum cost flow problems; hence, the favorable column generation structure from the application of Dantzig– Wolfe decomposition is not inherited to the method in [5]. In contrast to the method in [5], our parametric procedure can be applied in situations where the column generation is a discrete (or mixed-integer) optimization problem. Further, our procedure preserves structure, in the sense that it employs only the column generation problem for the application at hand. An application of our procedure to the bi-objective multi-commodity minimum cost flow problem studied in [5], after making a scalarization of the two objectives, would therefore be much simpler than the method in [5]. 2. Application to bi-objective discrete optimization We here investigate how a one-parametric column-oriented linear optimization problem and the procedure stated above can be used to effectively and efficiently calculate a strong bounding frontier (that is, an outer approximation) of the Pareto frontier of a bi-objective discrete optimization problem with complicating side constraints. The bounding frontier is based on a scalarization and convexification of the problem, and typically it is tighter than the bounding frontier obtained from a linear programming relaxation of the bi-objective problem. Let the vectors 𝑐1, 𝑐2∈R𝑛, the vector 𝑏∈R𝑚, and the matrix 𝐴∈R𝑚×𝑛. Further, let the set 𝑋 ⊂ R𝑛 +be non-empty and finite, and consider the bi-objective discrete optimization problem min (𝑧1, 𝑧2)=(𝑐T 1𝑥, 𝑐T 2𝑥) s.t. 𝐴𝑥 =𝑏, 𝑥∈𝑋, which is assumed to have a feasible solution. It is presumed that it is possible to efficiently minimize a linear objective over the set 𝑋, such that it is the bi-objective nature of the problem and the explicit linear Operations Research Perspectives 10 (2023) 100278 4 T. Larsson and N.-H. Quttineh Fig. 2. To the left, the objective outcomes of the points in the set 𝑋(small dots) and of the feasible solutions (large dots), the Pareto optimal outcomes (circles), the bounding frontier obtained from the linear programming relaxation (dash–dotted), the bounding frontier obtained from the one-parametric column generation (solid), and the breakpoints of the two frontiers (asterisks). To the right, a magnification of the Pareto optimal outcomes and the two frontiers. side constraints that make the problem challenging. Let 𝑍be the set of feasible objective outcomes, that is, 𝑍={(𝑐T 1𝑥, 𝑐T 2𝑥)|||𝐴𝑥 =𝑏and 𝑥∈𝑋}. Let 𝑃 ⊂ R𝑛be the set of Pareto optimal solutions and let 𝑍∗⊂R2be the set of Pareto optimal outcomes, that is, 𝑍∗={(𝑐T 1𝑥, 𝑐T 2𝑥)|||𝑥∈𝑃}. Clearly, the sets 𝑍,𝑃, and 𝑍∗are finite. Consider the function 𝑧∗∶ [0,1] ↦Rdefined by the scalarized problem 𝑧∗(𝑤) = min 𝑤𝑧1+ (1 − 𝑤)𝑧2= min [𝑤𝑐1+ (1 − 𝑤)𝑐2]T𝑥 s.t. (𝑧1, 𝑧2) ∈ 𝑍s.t. 𝐴𝑥 =𝑏, 𝑥∈𝑋. Since 𝑍is finite, 𝑧∗is clearly finite, piecewise linear and concave on its domain, with each piece corresponding to some 𝑥∈𝑋. From the expression for 𝑧∗follows that 𝑤𝑧1+ (1 − 𝑤)𝑧2≥𝑧∗(𝑤)holds for all (𝑧1, 𝑧2) ∈ 𝑍. Since 𝑍∗⊆ 𝑍, we may conclude that 𝑍∗⊂{(𝑧1, 𝑧2)|||𝑤𝑧1+ (1 − 𝑤)𝑧2≥𝑧∗(𝑤)}, 𝑤 ∈ [0,1]. Hence, 𝑍∗⊂⋂ 𝑤∈[0,1] {(𝑧1, 𝑧2)|||𝑤𝑧1+ (1 − 𝑤)𝑧2≥𝑧∗(𝑤)}.(9) We next consider the function 𝑧∗ c∶ [0,1] ↦Rdefined by the convexified scalarized problem 𝑧∗ c(𝑤) = min [𝑤𝑐1+ (1 − 𝑤)𝑐2]T𝑥 s.t. 𝐴𝑥 =𝑏, 𝑥∈conv(𝑋). Since this is a linear program with a bounded feasible set, the function 𝑧∗ cis finite, piecewise linear and concave on its domain, with each piece corresponding to an extreme point of the feasible set. Define 𝑍c=⋂ 𝑤∈[0,1] {(𝑧1, 𝑧2)|||𝑤𝑧1+ (1 − 𝑤)𝑧2≥𝑧∗ c(𝑤)}. The set can alternatively be expressed as 𝑍c={(𝑐T 1𝑥, 𝑐T 2𝑥)|||𝐴𝑥 =𝑏and 𝑥∈conv(𝑋)}+R2 +, where the first term is a convex, polyhedral, and bounded set, which leads to the following result. Proposition 6. The set 𝑍cis convex and polyhedral. Using that 𝑧∗ c(𝑤)≤𝑧∗(𝑤)holds for all 𝑤∈ [0,1] and the inclusion (9), it follows that 𝑍c⊃ 𝑍∗. Let 𝑍∗ cbe the set of Pareto optimal outcomes within the set 𝑍c. Clearly, 𝑍∗ c=bd(𝑍c). We have now arrived at the main result. Proposition 7. Each member of the set 𝑍∗ cis non-dominated by each member of the set 𝑍∗. We conclude that set 𝑍∗ cconstitute a bounding frontier for the Pareto frontier of the given bi-objective discrete optimization problem. Further, this frontier is the boundary of a polyhedral convex set. Remark 8. The bounding property of the set 𝑍∗ cis a close relative to the bounding property of a Lagrangian dual problem for a single-objective discrete optimization problem with complicating side constraints, which are Lagrangian relaxed. Assuming that the set 𝑋consists of 𝑁points, denoted by 𝑥𝑗,𝑗= 1,…, 𝑁, and letting 𝜇𝑗,𝑗= 1,…, 𝑁, be convexity weights for these points, the convexified scalarized problem can be expressed as 𝑧∗ c(𝑤) = min 𝑁 ∑ 𝑗=1 [𝑤𝑐1+ (1 − 𝑤)𝑐2]T𝑥𝑗𝜇𝑗 s.t. 𝑁 ∑ 𝑗=1 𝐴𝑥𝑗𝜇𝑗=𝑏, 𝑁 ∑ 𝑗=1 𝜇𝑗= 1, 𝜇𝑗≥0, 𝑗 = 1,…, 𝑁. This is a one-parametric column-oriented linear optimization problem that can be approached by Algorithm 1. Considering a fixed value of 𝑤∈ [0,1] and denoting a dual solution with (𝑦T, 𝑣)T∈R𝑚+1, the column generation problem (2) here becomes min 𝑥∈𝑋{[𝑤𝑐1+ (1 − 𝑤)𝑐2−𝐴T𝑦]T𝑥−𝑣},(10) that is, the minimization of a linear objective over the set 𝑋. (Recall that we assume that this minimization can be readily done.) If the set 𝑋is described by integrality restrictions on variables and linear constraints, say 𝑋={𝑥∈Z𝑛 +|||𝐷𝑥 ≥𝑒}, then the Pareto frontier can alternatively be bounded by the linear programming frontier 𝑍∗ LP = bd(𝑍LP)where 𝑍LP =⋂ 𝑤∈[0,1] {(𝑧1, 𝑧2)|||𝑤𝑧1+ (1 − 𝑤)𝑧2≥𝑧∗ LP(𝑤)} with 𝑧∗ LP(𝑤) = min [𝑤𝑐1+ (1 − 𝑤)𝑐2]T𝑥 s.t. 𝐴𝑥 =𝑏, 𝐷𝑥 ≥𝑒, 𝑥≥0. Operations Research Perspectives 10 (2023) 100278 5 T. Larsson and N.-H. Quttineh Fig. 3. Pareto optimal outcomes and the two frontiers for eight examples. Operations Research Perspectives 10 (2023) 100278 6 T. Larsson and N.-H. Quttineh Since conv({𝑥∈Z𝑛 +|||𝐷𝑥 ≥𝑒}) ⊆{𝑥∈R𝑛 +|||𝐷𝑥 ≥𝑒}, it holds that 𝑍c⊆ 𝑍LP. If the set {𝑥∈R𝑛 +|||𝐷𝑥 ≥𝑒}has the integrality property (see e.g. [2]), then the column generation problem (10) can be solved as a linear program, 𝑍c=𝑍LP holds, and hence the bounding frontier 𝑍∗ c coincides with that obtained from the linear programming relaxation of the scalarized bi-objective problem. Otherwise the column generation (10) is a genuine integer program and the bounding frontier 𝑍∗ cwill in general be tighter than that from the linear programming relaxation. Example 9. To illustrate the bounding of the Pareto frontier, we use a small numerical zero–one example. min (𝑧1= 7𝑥1+ 9𝑥2+ 4𝑥3+ 8𝑥4+𝑥5+ 9𝑥6+ 7𝑥7+ 6𝑥8+ 2𝑥9+ 2𝑥10, 𝑧2=𝑥1+𝑥2+ 9𝑥3+ 2𝑥4+ 8𝑥5+𝑥6+ 3𝑥7+ 5𝑥8+ 7𝑥9+ 3𝑥10) s.t.5𝑥1+ 7𝑥2+ 7𝑥3+ 5𝑥4+ 9𝑥5+ 4𝑥6+ 4𝑥7+ 2𝑥8+ 3𝑥9+ 2𝑥10 ≥26, 𝑥1+ 9𝑥2+ 7𝑥3+ 5𝑥4+ 2𝑥5+ 7𝑥6+ 5𝑥7+ 8𝑥8+ 7𝑥9+𝑥10 ≥28,(11a) 𝑥∈ {0,1}10 (11b) The set 𝑋is here defined by (11a) and (11b). It contains 457 points, and 337 out of these are feasible. These give 232 distinct objective outcomes, out of which 14 are Pareto optimal. Fig. 2 shows to the left the objective outcomes of the points in the set 𝑋and of the feasible solutions, the Pareto optimal outcomes, and the bounding frontiers obtained from the linear programming relaxation and from the oneparametric column generation. To the right is a magnification of only the Pareto optimal outcomes and the two frontiers. Column generation is here made by solving a knapsack problem, which does not have the integrality property, and therefore the column generation provides a tighter bounding frontier. This frontier has eight breakpoints, each corresponding to a knapsack solution. Fig. 3 shows results for eight more problems of the same structure as in Example 9. The problem data are randomly generated and the results illustrate that the strengths of the bounding frontiers of course vary between problem instances. As can be seen, the one-parametric column generation frontier is sometimes noticeable stronger than the linear programming relaxation frontier, while it is sometimes only slightly stronger. Further, the frontiers can be close to the Pareto optimal outcomes or farther away. An obvious potential application of the above described bounding of the Pareto frontier is in situations when it is prohibitively computationally expensive to calculate the Pareto frontier, but it is possible to use meta-heuristics (for example population-based) for finding a set of feasible solutions and resulting objective outcomes that are mutually non-dominated. The bounding frontier can then be used to assess the quality of the set of mutually non-dominated solutions. 3. Summary We have showed how to effectively and efficiently perform a oneparametric analysis of column-oriented linear programs. This topic has, quite surprisingly, not been studied previously. The proposed scheme relies on the standard column generation problem for the linear program at hand, and Newton’s method for finding the largest zero of a univariate function. The latter technique is inspired by results from fractional optimization. To exemplify how a one-parametric column-oriented linear program may arise, we consider a scalarized strong reformulation of a bi-objective discrete optimization problem. The outcome of this reformulation and the one-parametric analysis is a strong bounding of the Pareto frontier. An interesting topic for future research is to apply this approach to some class of computationally challenging bi-objective discrete optimization problems, for example for assessing the quality of a set of mutually non-dominated solutions found by a population-based meta-heuristic. CRediT authorship contribution statement Torbjörn Larsson: Conceptualization, Formal analysis, Visualization, Writing – original draft, Writing – review & editing. Nils-Hassan Quttineh: Conceptualization, Formal analysis, Visualization, Writing – review & editing. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Data availability Data for the numerical example is given in the paper. References [1] Murty KG. Linear programming. New York, NY: John Wiley & Sons; 1983. [2] Wolsey LA. Integer programming. New York, NY: John Wiley & Sons; 1998. [3] Radzik T. Fractional combinatorial optimization. In: Du D-Z, Pardalos PM, editors. Handbook of combinatorial optimization, vol. 1. Kluwer Academic Publishers; 1998, p. 429–78. [4] Borrero JS, Gillen C, Prokopyev OA. Fractional 0-1 programming: applications and algorithms. J Global Optim 2017;69(1):255–82. [5] Moradi S, Raith A, Ehrgott M. A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem. European J Oper Res 2015;244(2):369–78.