I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that involves bilinear terms, and I'm looking for guidance on whether there's a more efficient way to represent it.

Context and Conditions:

  1. Item Purchase: Each year, exactly one item is purchased.
    • Represented by variable $y_i$, the percentage of the item purchased in year $i$, where $0 \leq y_i \leq 1$.
  2. Item Sale: Each year, the available items can be sold. The amount sold is a fixed percentage of all held items.
    • Represented by variable $z_{i,t}$, the percentage of an item sold in year $t$ that was purchased in year $i$, where $0 \leq z_{i,t} \leq 1$.

Current Expression:

The total amount sold at time $t$ is given by:

$\sum_{i} S_{i,t} \cdot \left( y_{i} - \sum_{k=i}^{t-1} z_{i,k} \right) \cdot z_{i,t}$

  • $S_{i,t}$ is the sale price of an item in year $t$ that was purchased in year $i$.
  • The term $\left( y_{i} - \sum_{k=i}^{t-1} z_{i,k} \right)$ represents the amount of the item still available for sale at time $t$, calculated by taking the initial percentage of the item purchased $y_{i}$ and subtracting the cumulative percentage of the item sold in the previous years (from year $i$ to year $t-1$).

Additional Constraints:

  1. To ensure the amount sold does not exceed the amount purchased: $\sum_{i=1}^{t} z_{i,t} \leq y_{i}, \quad \forall i$
  2. For a uniform sale percentage across all items: $z_{i,t} = \alpha_{t}, \quad \forall i$ where the item is available for sale at time $t$ and $\alpha_{t}$ is an auxiliary variable.

Binary Variables:

The model includes binary variables to enforce logical conditions, such as allowing either a sale or a purchase in a given year. However, the focus here is on the expression mentioned above. The problem falls under Mixed-Integer Quadratic Programming (MIQP), which might be challenging to solve.


Is there a more streamlined way to represent this expression? For ease of understanding, I have expanded this expression below for the first three years, assuming a matrix $S$ representing sale prices:

Sale Price Matrix:

\begin{bmatrix} S_{1,1} & S_{1,2} & S_{1,3} \\ 0 & S_{2,2} & S_{2,3} \\ 0 & 0 & S_{3,3} \end{bmatrix}

Expanded Expression for Years ( t = 1, 2, 3 ):

  • Year $t = 1$: $\text{Total Sales Value at } t = 1: S_{1,1} \cdot y_{1} \cdot z_{1,1}$

  • Year $t = 2$: $\text{Total Sales Value at } t = 2: S_{1,2} \cdot \left( y_{1} - z_{1,1} \right) \cdot z_{1,2} + S_{2,2} \cdot y_{2} \cdot z_{2,2}$

  • Year $t = 3$: $\text{Total Sales Value at } t = 3: S_{1,3} \cdot \left( y_{1} - z_{1,1} - z_{1,2} \right) \cdot z_{1,3} + S_{2,3} \cdot \left( y_{2} - z_{2,2} \right) \cdot z_{2,3} + S_{3,3} \cdot y_{3} \cdot z_{3,3}$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.