# A multi-objective optimization approach for generalized linear multiplicative programming

Minh Hieu Nguyen, Thanh Loan Nguyen

<figure><img src="image_1.png" /></figure>

## To cite this version:

Minh Hieu Nguyen, Thanh Loan Nguyen. A multi-objective optimization approach for generalized linear multiplicative programming. 2025. hal-04986427

HAL Id: hal-04986427

https://hal.science/hal-04986427v1

Preprint submitted on 11 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A multi-objective optimization approach for generalized linear multiplicative programming

Minh Hieu Nguyen¹,² and Thanh Loan Nguyen³

¹ Unité de Mathématiques Appliquées, ENSTA, Institut Polytechnique de Paris, 91120 Palaiseau, France

² CEDRIC-Cnam, 292 rue Saint Martin, F-75141 Paris Cedex 03, France
minh-hieu.nguyen@ensta-paris.com

³ INP Clermont Auvergne, Univ Clermont Auvergne, Mines Saint-Etienne, CNRS, UMR 6158 LIMOS, 1 Rue de la Chebarde, 63178 Aubiere Cedex, France
Corresponding author: thanh-loan.nguyen@doctorant.uca.fr

**Abstract.** Multiplicative programming is a fundamental mathematical optimization problem in which the objective function contains a product of several real-valued functions. This paper deals with a class of multiplicative programming, called generalized linear multiplicative programming (GLMP), in which the objective is to minimize the product of two positive linear functions with general positive powers under linear constraints. Since the objective is a typical non-convex function, GLMP may have multiple local minima, making it computationally challenging. To address this, we propose a multi-objective optimization-based approach. By treating each function as an objective to be minimized, we show that a solution of GLMP is necessarily a non-dominated extreme point located on the vertex of the convex hull of the Pareto front. Then, we use a recursive algorithm to determine the set of all non-dominated extreme points. Notice that the solutions of GLMP can be directly extracted from this set. Furthermore, based on the Weighted Sum Method, it requires only solving one linear program in each iteration. Finally, we provide computational results on a specific instance of GLMP with 0-1 knapsack constraints, indicating that our approach is promising.

**Keywords:** Linear multiplicative programming · Multi-objective optimization · Pareto front · Weighted Sum Method.

## 1 Introduction

Multiplicative programming is a fundamental mathematical optimization problem that involves optimizing a product of several real-valued functions subject to general constraints. In this paper, we consider a class of multiplicative programming, called generalized linear multiplicative programming (GLMP), which can be formulated as:

$$ \min_{x \in \mathcal{X}} P(x)Q(x)^{\rho}, \qquad (1) $$
where $\mathcal{X} = \{x \in \mathbb{R}^n \mid Ax \leq b\}$ is a finite set of feasible solutions, $\rho \in \mathbb{R}_+$ and $P(x), Q(x)$ are positive linear functions, $\forall x \in \mathcal{X}$.

GLMP has been widely explored in the literature due to its broad inclusion of various mathematical programming models, such as quadratic programming, linear multiplicative programming, and bilinear programming. Moreover, GLMP plays a crucial role in numerous scientific applications, including portfolio management [8], marketing and service planning [13], and microeconomics [14], among others.

From the algorithmic point of view, even a product of two linear functions (i.e., $\rho = 1$) is not necessarily convex [3], and then GLMP belongs to a class of nonconvex programming problems called global optimization problems which may have multiple local minima. Thus, finding global solutions to GLMP is NP-hard [12]. In the past several decades, many methods have been developed to tackle GLMP. These methods can be mainly classified as parametric simplex method-based algorithms (e.g., [5]), branch-and-bound methods (e.g., [6]) and various heuristic methods (e.g., [9], [11]).

As an optimal solution of GLMP is an efficient (non-dominated or Pareto-optimal) solution of a multi-objective optimization problem where each function is to be minimized, some methods have been recently proposed to solve GLMP based on multi-objective optimization techniques. For example, when $\rho = 1$, Shao et al. employed primal and dual multi-objective linear programming algorithms to compute the Pareto front which contains all non-dominated points to solve GLMP [12]. Similarly, Mahmoodian et al. developed a decision-space search algorithm that works directly in the space of decision variables. The algorithm performs similarly to the classical branch-and-bound algorithm for solving single-objective mixed integer linear programs [10].

In this paper, we further develop the multi-objective optimization approach by improving the method proposed in [12]. Specifically, we establish that a global solution of GLMP should be a non-dominated extreme point located on the vertex of the convex hull of the Pareto front. Instead of computing all non-dominated points by branch-and-bound methods, we determine directly all non-dominated extreme points by a recursive algorithm, significantly reducing computational complexity. Notice that in practice, the number of non-dominated extreme points is much less than the number of non-dominated points. Furthermore, based on the Weighted Sum Method, it requires only solving one linear program in each iteration. Finally, we present computational results on a GLMP instance with 0-1 knapsack constraints, demonstrating the effectiveness of our approach.

The paper is organized as follows. In Section 2, we present a mathematical formulation and some preliminaries on multi-objective optimization. In Section 3, we design a recursive algorithm to determine the global solution of GLMP. Computational results on an instance of GLMP with 0-1 knapsack constraints will be presented and discussed in Section 4. Section 5 concludes the paper and outlines directions for future research.
## 2 Generalized linear multiplicative programming and multi-objective optimization

We recall that an optimal solution problem (1) is an efficient solution (i.e., non-dominated solution or Pareto-optimal solution) of the following bi-objective optimization problem: [12]

$$ \min_{x \in \mathcal{X}} (P(x), Q(x)), \qquad (2) $$

Consequently, we can obtain an optimal solution of GLMP (ρ-LMP solution) by minimizing $P(x)Q(x)^ρ$ over the set of efficient solutions (i.e., Pareto front) to problem (2). Let $(P, Q) = (P(x), Q(x))$ denote the objective values corresponding to a decision vector $x \in \mathcal{X}$. Let $\mathcal{S}$ represent the set of pairs $(P, Q)$ corresponding to all feasible decision vector solutions. This paper will characterize the feasible solutions (including the efficient solutions) to problem (2) by using pairs $(P, Q)$ instead of the decision vector solutions $x$. Thus, two feasible solutions having the same values of $(P, Q)$ will be considered equivalent i.e., $(P', Q') \equiv (P'', Q'') \iff P' = P''$ and $Q' = Q''$. Furthermore, an efficient solution $(P, Q)$ is also a point $(P, Q)$ on the Pareto front.

In the following, we restate several classes of efficient solutions [15].

1. Supported efficient solution are optimal solutions of a weighted sum single-objective problem

$$ W(\alpha) = \min_{(P,Q) \in \mathcal{S}} P + \alpha Q, \text{ where } \alpha \in \mathbb{R}_{+}, $$

2. Non-supported efficient solutions are efficient solutions that are not optimal solutions of $W(\alpha)$ for any $\alpha \in \mathbb{R}_{+}$.

Furthermore, we can distinguish two classes of supported efficient solutions.

a. Supported solutions are located on the vertex of the convex hull of the Pareto front called extremal supported efficient solutions.

b. Supported solutions are located on the relative inferior faces of the convex hull of the Pareto front called non-extremal supported efficient solutions.

Fig. 1 illustrates an example of bi-objective optimization problem (2) with different classes of efficient solutions on the Pareto front.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Illustration of extremal/non-extremal supported efficient solutions, non-supported efficient solutions on the Pareto front.</figcaption></figure>
### 3 Algorithm for solving GLMP

In this section, we first show that a $\rho$-LMP solution is a supported efficient solution. Furthermore, it is necessarily an extremal supported efficient solution.

**Theorem 1.** Let $(P_*, Q_*)$ be a $\rho$-LMP solution. Then it is a supported efficient solution. Moreover, it is necessarily an extremal supported efficient solution.

*Proof.* Since $(P_*, Q_*)$ is a $\rho$-LMP solution, we have $PQ^\rho \ge P_*Q_*^\rho, \forall (P, Q) \in S$. Using Young's inequality for products (See Appendix 1), we have

$$ \frac{1}{\rho+1} \frac{P}{P_*} + \frac{\rho}{\rho+1} \frac{Q}{Q_*} \ge (\frac{P}{P_*})^{\frac{1}{\rho+1}} (\frac{Q}{Q_*})^{\frac{\rho}{\rho+1}} = \sqrt[\rho+1]{\frac{PQ^\rho}{P_*Q_*^\rho}} \ge 1, \forall (P, Q) \in S, \quad (3) $$

Multiplying both sides of (3) by $(\rho+1)P_* > 0$ gives

$$ P + \alpha_* Q \ge P_* + \alpha_* Q_*, \forall (P, Q) \in S, $$

where $\alpha_* = \rho P_*/Q_* > 0$. Thus, $(P_*, Q_*)$ is an optimal solution of $W(\alpha_*)$ which implies it is a supported efficient solution.

Now let $(P_i, Q_i)$, $(P_j, Q_j)$ be two extremal supported efficient solutions and $(P_k, Q_k)$ be a supported efficient solution such that they are collinear and $P_i < P_k < P_j$, $Q_i > Q_k > Q_j$. We will show that $P_k Q_k^\rho > \min\{P_i Q_i^\rho, P_j Q_j^\rho\}$.

Since they are collinear, there exist $\lambda_1, \lambda_2 \in \mathbb{R}_+$ and $\lambda_1 + \lambda_2 = 1$ such that $P_k = \lambda_1 P_i + \lambda_2 P_j$ and $Q_k = \lambda_1 Q_i + \lambda_2 Q_j$.

Since $\ln(t)$ is a concave function for $t \in \mathbb{R}_+$, using Jensen's inequality gives

$$ \begin{aligned} & \ln(\lambda_1 P_i + \lambda_2 P_j) + \rho \ln(\lambda_1 Q_i + \lambda_2 Q_j) \\ & \ge \lambda_1 \ln(P_i) + \lambda_2 \ln(P_j) + \rho(\lambda_1 \ln(Q_i) + \lambda_2 \ln(Q_j)), \\ & = \lambda_1(\ln(P_i) + \rho \ln(Q_i)) + \lambda_2(\ln(P_j) + \rho \ln(Q_j)), \\ & = \lambda_1 \ln(P_i Q_i^\rho) + \lambda_2 \ln(P_j Q_j^\rho), \end{aligned} $$

Thus,

$$ \begin{aligned} & (\lambda_1 P_i + \lambda_2 P_j)(\lambda_1 Q_i + \lambda_2 Q_j)^\rho \ge (P_i Q_i^\rho)^{\lambda_1} (P_j Q_j^\rho)^{\lambda_2}, \\ & \ge \min\{P_i Q_i^\rho, P_j Q_j^\rho\}^{\lambda_1+\lambda_2}, \\ & = \min\{P_i Q_i^\rho, P_j Q_j^\rho\}, \end{aligned} $$

Notice that the "=" sign in the above inequalities do not hold since $(P_i, Q_i) \ne (P_j, Q_j)$. Consequently, we have $P_k Q_k^\rho > \min\{P_i Q_i^\rho, P_j Q_j^\rho\}$. In other words, a $\rho$-LMP solution is necessarily an extremal supported efficient solution. $\square$

Then we show the monotonic relationship between $\alpha \in \mathbb{R}_+$ and the optimal solution values of $W(\alpha)$.

**Lemma 1.** Given $0 \le \alpha' < \alpha''$ and let $(P', Q')$, $(P'', Q'') \in S$ be the solutions of $W(\alpha')$ and $W(\alpha'')$, respectively. Then $P' \le P''$ and $Q' \ge Q''$.
Proof. The optimality of $(P', Q')$ and $(P'', Q'')$ gives

$$P' + \alpha'Q' \leq P'' + \alpha'Q'', \text{ and} \quad (4a)$$

$$P'' + \alpha''Q'' \leq P' + \alpha''Q' \quad (4b)$$

Adding (4a) and (4b) gives $(\alpha' - \alpha'')(Q' - Q'') \leq 0$. Since $\alpha' < \alpha''$, $Q' \geq Q''$. In addition, the inequality (4a) implies $P' - P'' \leq \alpha'(Q'' - Q') \leq 0$. $\square$

As a consequence of Lemma 1, we state the following corollary.

**Corollary 1.** If $\alpha' < \alpha''$ and $(P', Q')$ is the solution of both $W(\alpha')$ and $W(\alpha'')$ then $(P', Q')$ is the unique optimal solution of $W(\alpha)$ for all $\alpha' < \alpha < \alpha''$.

**Definition 1 (Consecutive extremal supported efficient solutions).** Let $(P_i, Q_i)$ and $(P_j, Q_j)$ be two extremal supported efficient solutions such that $P_i < P_j$ and $Q_i > Q_j$. They are considered consecutive supported efficient solutions if there is no other extremal supported efficient solution located between $(P_i, Q_i)$ and $(P_j, Q_j)$ on the convex hull of the Pareto front. In other words, there is no other extremal supported efficient solution $(P, Q)$ such that $P_i < P < P_j$ and $Q_i > Q > Q_j$.

The following lemma gives us a condition for verifying whether two extremal supported efficient solutions are consecutive.

**Theorem 2.** Let $(P_i, Q_i)$ and $(P_j, Q_j)$ be two extremal supported efficient solutions such that $P_i < P_j$ and $Q_i > Q_j$. Then $(P_i, Q_i)$ and $(P_j, Q_j)$ are two consecutive extremal supported efficient solutions on the convex hull of the Pareto front if and only if $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$ where $\alpha_k = (P_j - P_i)/(Q_i - Q_j)$.

*Proof.* Suppose that $(P_i, Q_i)$ and $(P_j, Q_j)$ are optimal solutions of $W(\alpha_i)$ and $W(\alpha_j)$, respectively, where $0 < \alpha_i < \alpha_j$. Let $\alpha_k = (P_j - P_i)/(Q_i - Q_j)$. We first show that $\alpha_i \leq \alpha_k \leq \alpha_j$.

The optimality of $(P_i, Q_i)$ and $(P_j, Q_j)$ gives

$$\begin{aligned} P_i + \alpha_i Q_i &\leq P_j + \alpha_i Q_j, \\ P_j + \alpha_j Q_j &\leq P_j + \alpha_j Q_j, \end{aligned}$$

Thus, we obtain $\alpha_i \leq \frac{P_j - P_i}{Q_i - Q_j} \leq \alpha_j$, which implies $\alpha_i \leq \alpha_k \leq \alpha_j$.

⇒ Assume that $(P_i, Q_i)$ and $(P_j, Q_j)$ are two consecutive extremal supported efficient solutions. We consider the three following cases.

1. If $\alpha_k = \alpha_i$ then obviously $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$.

2. If $\alpha_k = \alpha_j$, we have $\alpha_j = (P_j - P_i)/(Q_i - Q_j)$ which implies

$$P_i + \alpha_j Q_i = P_j + \alpha_j Q_j,$$

Hence, $(P_i, Q_i)$ is also an optimal solution of $W(\alpha_k)$.
3. If $\alpha_i < \alpha_k < \alpha_j$, let $(P_k, Q_k)$ be a supported efficient solution which is an optimal solution of $W(\alpha_k)$.

If $(P_k, Q_k) \equiv (P_i, Q_i)$ then obviously $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$.

If $(P_k, Q_k) \equiv (P_j, Q_j)$ then $\alpha_k = (P_k - P_i)/(Q_i - Q_k)$ which implies

$$P_i + \alpha_k Q_i = P_k + \alpha_k Q_k,$$

Hence, $(P_i, Q_i)$ is also an optimal solution of $W(\alpha_k)$.

If $(P_k, Q_k) \neq (P_i, Q_i)$ and $(P_k, Q_k) \neq (P_j, Q_j)$ then $P_i < P_k < P_j$ and $Q_i > Q_k > Q_j$. Since $(P_i, Q_i)$ and $(P_j, Q_j)$ are two consecutive extremal supported efficient solutions, $(P_k, Q_k)$ is necessarily collinear with $(P_i, Q_i)$ and $(P_j, Q_j)$. Thus, we have

$$\frac{P_k - P_i}{Q_i - Q_k} = \frac{P_j - P_i}{Q_i - Q_j} = \alpha_k,$$

Hence, $P_i + \alpha_k Q_i = P_k + \alpha_k Q_k$ which implies $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$.

Assume that $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$. Notice that a supported solution located between $(P_i, Q_i)$ and $(P_j, Q_j)$ is necessarily an optimal solution of $W(\alpha)$ where $\alpha_i < \alpha < \alpha_j$ due to Lemma 1. We consider the three following cases.

1. If $\alpha_k = \alpha_i$, we have $P_i + \alpha_i Q_i = P_j + \alpha_i Q_j$ which implies $(P_j, Q_j)$ is also an optimal solution of $W(\alpha_i)$.

Since $(P_j, Q_j)$ is the optimal solution of both $W(\alpha_i)$ and $W(\alpha_j)$, it is the unique optimal solution of $W(\alpha)$ for any $\alpha_i < \alpha < \alpha_j$. Thus, $(P_i, Q_i)$ and $(P_j, Q_j)$ are two consecutive extremal supported efficient solutions.

2. If $\alpha_k = \alpha_j$, we have $P_i + \alpha_j Q_i = P_j + \alpha_j Q_j$ which implies $(P_i, Q_i)$ is also an optimal solution of $W(\alpha_j)$. Similar to the case above, $(P_i, Q_i)$ is the unique optimal solution of $W(\alpha)$ for any $\alpha_i < \alpha < \alpha_j$. Hence, $(P_i, Q_i)$ and $(P_j, Q_j)$ are two consecutive extremal supported efficient solutions.

3. If $\alpha_i < \alpha_k < \alpha_j$, we have $P_i + \alpha_k Q_i = P_j + \alpha_k Q_j$ due to $\alpha_k = (P_j - P_i)/(Q_i - Q_j)$. Furthermore, as $(P_i, Q_i)$ is an optimal solution of $W(\alpha_k)$ which implies $(P_j, Q_j)$ is also an optimal solution of $W(\alpha_k)$.

Since $(P_i, Q_i)$ is an optimal solution of both $W(\alpha_i)$ and $W(\alpha_k)$, it is the unique optimal solution of $W(\alpha)$ where $\alpha_i < \alpha < \alpha_k$. Similarly, $(P_j, Q_j)$ is the unique optimal solution of $W(\alpha)$ where $\alpha_k < \alpha < \alpha_j$. Furthermore, for any optimal solution $(P_k, Q_k)$ of $W(\alpha_k)$ which is different to $(P_i, Q_i)$, we have $P_i + \alpha_k = P_k + \alpha_k Q_k$ which implies

$$\alpha_k = \frac{P_k - P_i}{Q_i - Q_k} \implies \frac{P_j - P_i}{Q_i - Q_j} = \frac{P_k - P_i}{Q_i - Q_k},$$

Thus, $(P_i, Q_i)$, $(P_k, Q_k)$ and $(P_j, Q_j)$ are collinear which implies $(P_k, Q_k)$ is not an extremal supported efficient solution. Consequently, $(P_i, Q_i)$ and $(P_j, Q_j)$ are consecutive extremal supported efficient solutions. □
We now present Procedure FIND\_GLMP(), an iterative algorithm for identifying the solution of the GLMP and all extremal supported efficient solutions of its corresponding bi-objective optimization problem. The algorithm begins by computing two extremal supported efficient solutions, $(P_0, Q_0)$ and $(P_1, Q_1)$, which are obtained by minimizing $P(x)$ and $Q(x)$, respectively (or by lexically minimizing in case of multiple optimal solutions). The algorithm initializes a solution set $E$ for the GLMP, starting with the list of extremal supported efficient solution $I \leftarrow \{(P_0, Q_0), (P_1, Q_1)\}$. Additionally, a search list $L = \{[(P_0, Q_0), (P_1, Q_1)]\}$ is initialized to store the areas to be explored.

**Procedure 1 Finding $\rho$-LMP solutions**

**Input:** A general GLMP.

**Output:** $\rho$-LMP solutions.

1. **procedure FIND\_GLMP()**

2. minimize $P(x), Q(x)$ to obtain $(P_0, Q_0), (P_1, Q_1)$, respectively.

3. $I \leftarrow \{(P_0, Q_0), (P_1, Q_1)\}$, $L \leftarrow \{[(P_0, Q_0), (P_1, Q_1)]\}$

4. **while** $L \neq \emptyset$ **do**

5. select and remove $[(P_i, Q_i), (P_j, Q_j)]$ from $L$

6. $\alpha \leftarrow \frac{P_j - P_i}{Q_i - Q_j}$

7. **if** $(P_i, Q_i)$ is an optimal solution of $W(\alpha)$ **then**

8. $I \leftarrow I \cup \{(P_i, Q_i), (P_j, Q_j)\}$

9. continue to the next pair in $L$

10. **else**

11. solve $W(\alpha)$ to obtain a solution $(P_m, Q_m)$

12. $L \leftarrow L \cup \{[(P_i, Q_i), (P_m, Q_m)], [(P_m, Q_m), (P_j, Q_j)]\}$

13. **end if**

14. **end while**

15. $E \leftarrow \text{argmin}_{(P,Q) \in I} PQ^\rho$

16. **return** $E$

17. **end procedure**

The algorithm iterates through the search lists in $L$, refining the set of solutions as follows. For each pair of solutions $(P_i, Q_i)$ and $(P_j, Q_j)$ in $L$, it calculates a weight

$$ \alpha = \frac{P_j - P_i}{Q_i - Q_j} $$

and considers the problem $W(\alpha)$. According to Theorem 2, we first verify whether $(P_i, Q_i)$ is an optimal solution of $W(\alpha)$. If it is, then $(P_i, Q_i)$ and $(P_j, Q_j)$ are consecutive extremal supported efficient solutions, meaning no further refinement is needed. In this case, we add them to the solution list $I$ and proceed to the next pair in $L$. Otherwise, we solve $W(\alpha)$ to obtain a new solution $(P_m, Q_m)$, ensuring that $(P_m, Q_m) \neq (P_i, Q_i)$ and $(P_m, Q_m) \neq (P_j, Q_j)$. The algorithm then updates $L$ by replacing the interval $[(P_i, Q_i), (P_j, Q_j)]$ with two new search
intervals:

$$[(P_i, Q_i), (P_m, Q_m)] \text{ and } [(P_m, Q_m), (P_j, Q_j)].$$

This process continues iteratively until $L$ becomes empty, ensuring that all extremal supported efficient solutions have been identified in $I$. Finally, $E$ is defined as the set of optimal solutions that minimize $PQ^\rho$ among all extremal supported efficient solutions $(P, Q)$. As stated in Theorem 1, $E$ represents the solution set of the GLMP with respect to the value of $\rho$.

# 4 Experimental study on the GLMP with 0-1 knapsack constraints

## 4.1 Definition and modeling

The 0-1 knapsack problem is a fundamental combinatorial optimization problem in which a decision-maker selects a subset of $n$ items, each defined by a profit value, a weight, and a binary decision variable, while ensuring that the total weight does not exceed a given capacity. In this study, we examine the GLMP with 0-1 knapsack constraints, where the objective is to minimize a multiplicative function while adhering to a knapsack-type feasibility constraint. This problem extends the classical knapsack problem, which has wide-ranging applications in resource allocation, logistics, and financial decision-making [2].

Kuno's work [7] makes a significant contribution to solving multiplicative programming problems with 0-1 knapsack constraints by developing a branch-and-bound algorithm. However, this approach is specifically designed for a restricted class of problems and does not generalize to broader instances of multiplicative programming with knapsack constraints. On the other hand, our work introduces a more generalized framework that extends beyond the specific problem class tackled by Kuno, allowing it to efficiently handle a wide range of multiplicative optimization problems without relying on specialized structural assumptions or restrictive conditions.

Formally, given a set of $n$ items, each item $i$ is associated with two objective values, $p_i$ and $q_i$ (e.g., representing different profit measures or utility functions, a weight $w_i$, and a binary decision variable $x_i$, where $x_i = 1$ if the item is selected and $x_i = 0$ otherwise. Let $\mathcal{X}$ denote the set of all feasible selections. The knapsack has a total capacity $C$, denoting the minimum threshold that limits the total weight of selected items. The GLMP with 0-1 knapsack constraints is then formulated as:

$$ \begin{array}{ll} \min & P(x)Q(x)^\rho \\ \text{subject to} & P(x) = \sum_{i=1}^{n} p_i x_i, \quad Q(x) = \sum_{i=1}^{n} q_i x_i, \\ & \sum_{i=1}^{n} w_i x_i \geq C, \\ & x_i \in \{0, 1\}, \quad i = 1, \dots, n. \end{array} $$
This formulation introduces multiplicative interactions between selected items, making the problem significantly more complex than its additive counterpart. As discussed in Section 3, solving the GLMP 0-1 knapsack problem requires solving $W(\alpha) = \min_{x \in \mathcal{X}} P(x) + \alpha Q(x) \iff \min_{x \in \mathcal{X}} \sum_{i=1}^{n} (p_i + \alpha q_i)x_i$. This transformation effectively reduces the original problem to a single-objective 0-1 knapsack problem with a modified profit $p = p_i + \alpha q_i$. In the following sections, we present experimental instances and analyze the results obtained using our proposed method for solving the GLMP 0-1 knapsack problem.

## 4.2 Numerical results

We generated problem instances with the number of items $n$ ranging from 20 to 500, increasing by 20 each time. For each instance, item weights $w_i$ were randomly selected from the range [1, 15]. The two profit values, $p_i$ and $q_i$, were independently drawn from the intervals [20, 40] and [10, 50], respectively. For a single-objective 0-1 knapsack problem, the ratio

$$r = \frac{C}{\sum_{i=1}^{n} w_i}$$

indicates how constrained the knapsack capacity is relative to the total item weights. When $r \approx 0.5$, the problem reaches a critical point where many feasible combinations exist, but the minimal capacity enforces strict selection constraints, intensifying competition among them and making the optimization particularly challenging. In this study, we focus on $r = 0.5$, as it is known to be the hardest setting for both single-objective and multi-objective knapsack problems [1]. Notice that dynamic programming and branch-and-bound algorithms work well for small 0-1 knapsack problems but become inefficient as the problem size grows. Dynamic programming requires too much memory and computation, while branch-and-bound struggles with a rapidly expanding search space. To address these issues, we employ the CPLEX solver to solve the single-objective 0-1 knapsack problem $W(\alpha)$. CPLEX is specifically designed to efficiently handle large-scale instances, delivering optimal solutions within a reasonable computational time.

Table 1 presents the numerical results for computing the $\rho$-LMP solution $(P, Q)$ of the GLMP 0-1 knapsack problem for three values of $\rho$: 0.5, 1, and 2. The column $n_{items}$ denotes the number of items considered and the "ESES" column indicates the number of extremal supported efficient solutions. "Time" and "Iterations" refer to the computational time in seconds and the number of iterations required by Algorithm 1 to obtain all extremal supported efficient solutions for each instance, respectively. Additionally, Fig. 2 presents the $\rho$-LMP solution for the GLMP 0-1 knapsack constraints, along with all extremal supported efficient solutions of the corresponding bi-objective optimization problem. The results are shown for instances with 300 and 400 items, considering three cases of $\rho$, where $\rho \in \{0.5, 1, 2\}$. All computational experiments were performed on a system featuring an Intel Core i5-10500 CPU (3.10 GHz), 15 GB RAM with 6 cores and 12 threads.
<table><caption>Table 1: Numerical results for GLMP 0-1 knapsack problem</caption><thead><tr><th rowspan="2">n<sub>items</sub></th><th rowspan="2">Time</th><th rowspan="2">ESES</th><th rowspan="2">Iterations</th><th colspan="2">ρ = 0.5</th><th colspan="2">ρ = 1</th><th colspan="2">ρ = 2</th></tr><tr><th>P</th><th>Q</th><th>P</th><th>Q</th><th>P</th><th>Q</th></tr></thead><tbody><tr><td>20</td><td>0.2965</td><td>7</td><td>11</td><td>175</td><td>195</td><td>202</td><td>149</td><td>268</td><td>117</td></tr><tr><td>40</td><td>0.3115</td><td>8</td><td>13</td><td>392</td><td>345</td><td>448</td><td>280</td><td>503</td><td>256</td></tr><tr><td>60</td><td>0.5993</td><td>15</td><td>27</td><td>600</td><td>345</td><td>677</td><td>288</td><td>677</td><td>288</td></tr><tr><td>80</td><td>0.5495</td><td>10</td><td>17</td><td>520</td><td>689</td><td>731</td><td>388</td><td>751</td><td>382</td></tr><tr><td>100</td><td>0.7708</td><td>18</td><td>33</td><td>900</td><td>669</td><td>1039</td><td>550</td><td>1140</td><td>517</td></tr><tr><td>120</td><td>0.8115</td><td>19</td><td>35</td><td>956</td><td>818</td><td>1051</td><td>702</td><td>1116</td><td>672</td></tr><tr><td>140</td><td>0.8470</td><td>19</td><td>35</td><td>1328</td><td>832</td><td>1369</td><td>798</td><td>1447</td><td>772</td></tr><tr><td>160</td><td>2.2811</td><td>48</td><td>93</td><td>1504</td><td>1049</td><td>1791</td><td>824</td><td>1893</td><td>791</td></tr><tr><td>180</td><td>1.2663</td><td>27</td><td>51</td><td>1632</td><td>1293</td><td>1773</td><td>1150</td><td>1943</td><td>1069</td></tr><tr><td>200</td><td>1.1329</td><td>23</td><td>43</td><td>1768</td><td>1185</td><td>1869</td><td>1099</td><td>2009</td><td>1046</td></tr><tr><td>220</td><td>2.0099</td><td>44</td><td>85</td><td>1949</td><td>1372</td><td>2146</td><td>1188</td><td>2342</td><td>1112</td></tr><tr><td>240</td><td>0.9087</td><td>18</td><td>33</td><td>1694</td><td>2084</td><td>2407</td><td>1138</td><td>2486</td><td>1112</td></tr><tr><td>260</td><td>1.1313</td><td>26</td><td>49</td><td>2371</td><td>1502</td><td>2550</td><td>1375</td><td>2707</td><td>1318</td></tr><tr><td>280</td><td>0.9467</td><td>25</td><td>47</td><td>2551</td><td>1681</td><td>2678</td><td>1569</td><td>2811</td><td>1513</td></tr><tr><td>300</td><td>1.8231</td><td>38</td><td>73</td><td>2495</td><td>1920</td><td>2780</td><td>1645</td><td>3050</td><td>1542</td></tr><tr><td>320</td><td>3.5265</td><td>75</td><td>147</td><td>2842</td><td>2215</td><td>3143</td><td>1924</td><td>3366</td><td>1824</td></tr><tr><td>340</td><td>1.1231</td><td>29</td><td>55</td><td>3319</td><td>1927</td><td>3552</td><td>1743</td><td>3756</td><td>1673</td></tr><tr><td>360</td><td>2.7074</td><td>53</td><td>103</td><td>3308</td><td>2261</td><td>3514</td><td>2070</td><td>3758</td><td>1967</td></tr><tr><td>380</td><td>3.0421</td><td>53</td><td>103</td><td>3424</td><td>2454</td><td>3593</td><td>2295</td><td>3943</td><td>2134</td></tr><tr><td>400</td><td>2.0309</td><td>45</td><td>87</td><td>3649</td><td>2548</td><td>3804</td><td>2408</td><td>3930</td><td>2351</td></tr><tr><td>420</td><td>1.7259</td><td>37</td><td>71</td><td>4002</td><td>2329</td><td>4203</td><td>2166</td><td>4465</td><td>2076</td></tr><tr><td>440</td><td>1.8541</td><td>41</td><td>79</td><td>4086</td><td>2777</td><td>4443</td><td>2503</td><td>4709</td><td>2388</td></tr><tr><td>460</td><td>2.1846</td><td>43</td><td>83</td><td>3330</td><td>3811</td><td>4378</td><td>2361</td><td>4745</td><td>2227</td></tr><tr><td>480</td><td>3.3043</td><td>57</td><td>111</td><td>4530</td><td>2849</td><td>4909</td><td>2543</td><td>5170</td><td>2446</td></tr><tr><td>500</td><td>4.7188</td><td>95</td><td>187</td><td>4952</td><td>3133</td><td>5360</td><td>2805</td><td>5816</td><td>2638</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>(a) The case of 300 items</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) The case of 400 items</figcaption></figure>

<caption>Fig. 2: ρ-LMP solutions with ρ ∈ {0.5, 1, 2}</caption>
As shown in Table 1, our algorithm demonstrates high computational ef-
ficiency, consistently solving large-scale instances in a very short runtime. Al-
though the GLMP 0-1 knapsack problem can theoretically have multiple solu-
tions, all tested cases with three values of ρ returned a unique optimal solution.
According to 2, the algorithm terminates once all pairs of consecutive extremal
supported efficient solutions have been identified, making the number of itera-
tions approximately twice the number of extremal supported efficient solutions.
As a result, the computational time is more dependent on the number of extremal
supported efficient solutions than on the total number of items. This explains
why instances with fewer items can sometimes take longer to solve. In Table 1,
the 320-item instance with 75 extremal supported efficient solutions takes 3.5265
seconds, while the 400-item instance, with only 45 solutions, requires just 2.0309
seconds. While larger instances generally tend to have more extremal supported
efficient solutions, this is not always the case. Since the algorithm’s runtime is
closely tied to the number of these solutions, problem complexity is influenced
not only by the input size but also by the structure of the Pareto front.

Furthermore, the results show how different values of ρ influence the cor-
responding ρ-LMP solutions. For a fixed number of items, the values of P in
optimal solutions follows the order P<sub>ρ=0.5</sub> < P<sub>ρ=1</sub> < P<sub>ρ=2</sub>, while those of Q
follow the opposite trend: Q<sub>ρ=2</sub> < Q<sub>ρ=1</sub> < Q<sub>ρ=0.5</sub>. This suggests that in the
obtained optimal solutions, a larger value of ρ corresponds to a higher value of
P and a lower value of Q.

# 5 Conclusion

In this paper, we developed a multi-objective optimization approach to solve
*generalized linear multiplicative programming (GLMP)* where the objective is
a product of two positive linear functions with general positive powers under
linear constraints. By considering a bi-objective optimization problem, we first
demonstrated that a solution of GLMP is necessarily an extremal supported ef-
ficient solution on the Pareto front. Then, we presented a recursive algorithm to
determine all the extremal supported efficient solutions. Based on the Weighted
Sum Method, it requires only solving one linear program in each iteration. Fi-
nally, computational experiments on some instances of GLMP with 0-1 knapsack
constraints have shown the effectiveness of our approach.

Future work should enhance the proposed algorithm to solve GLMP more
efficiently by avoiding the need to identify all extremal supported efficient solu-
tions. Additionally, we aim to explore extensions of our results to multiplicative
programming involving the product of more than two positive linear functions.

# Acknowledgments

We thank Dr. Manh Linh Nguyen, Mathematics Institute of Jussieu-Paris Rive
Gauche, CNRS, Sorbonne University and Paris Cité University for his sugges-
tions to improve the presentation of the paper.
## References

1. Visée, M., Teghem, J., Pirlot, M., Ulungu, E.L.: Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. In: Journal of Global Optimization, 12, pp. 139–155, 1998.

2. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, 2004.

3. Avriel, M., Diewert W.E., Schaible S., Zhang I.: Generalized concavity. Plenum Press, New York, 2010.

4. Bennett, K.F., Mangasarian, O.L.: Bilinear separation of two sets in n-space. In: Comput Optim Appl, 2, pp. 207–227, 1994.

5. Kuno, T., Konno, H.: Linear multiplicative programming. In: Mathematic Programming, 56, pp. 51–64, 1992.

6. Kuno, T.: A finite branch-and-bound algorithm for linear multiplicative programming. In: Comput Optim Appl, 20, pp. 119–135, 2001.

7. Kuno, T.: Solving a class of multiplicative programs with 0-1 knapsack constraints. In: *Journal of Optimization Theory and Applications*. Vol. 103, No. 1. New York: Plenum Publishing Corporation, pp. 121–135, 1999.

8. Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. In: Journal of the Operations Research Society of Japan, Vol. 32, No. 2, 1989.

9. Liu, X.J., Umegaki, T., Yamamoto, Y.: Heuristic methods for linear multiplicative programming. In: Journal of Global Optimization, 4(15), pp. 433–447, 1999.

10. Mahmoodian, M., Charkhgard, H., Zhang, Y.: Multi-objective optimization based algorithms for solving mixed integer linear minimum multiplicative programs. In: Computers & Operations Research, Vol. 128, 2021.

11. Benson HP, Boger GM.: Multiplicative programming problems: analysis and efficient point search heuristic. In: Journal of Optimization Theory and Application, 94(2):487–510, 1997.

12. Shao, L., Ehrgott, M.: Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes. In: A Journal of Mathematical Programming and Operations Research, Vol. 65(2), 2016.

13. Samadi, F., Mirzazadeh, A., Pedram, M.M.: Fuzzy pricing, marketing and service planning in a fuzzy inventory model: a geometric programming approach. In: Appl Math Model 37:6683–6694, 2013.

14. Henderson, J.M., Quandt, R.E.: Microeconomic theory. In: McGraw-Hill, New York, 1961.

15. Alves, M.J., Costa, J.P.: Graphical exploration of the weight space in three-objective mixed integer linear programs. In: European Journal of Operational Research, Vol. 248, pp. 72–83, 2016.

# APPENDIX

## Appendix 1

[Young's inequality for products] Suppose $x, y > 0, \alpha, \beta > 0$ and $\alpha + \beta = 1$ then $\alpha x + \beta y \geq x^{\alpha} y^{\beta}$.

*Proof.* Since the natural logarithmic function is concave, using Jensen's inequality, we have

$$ \log(\alpha x + \beta y) \geq \alpha \log(x) + \beta \log(y) = \log(x^{\alpha} y^{\beta}), $$

Thus, $\alpha x + \beta y \geq x^{\alpha} y^{\beta}$ and the equality holds if and only if $x = y$. □

<figure><img src="image_6.png" /></figure>