Suppose we have a market that follows the following rules. For each time window, the suppliers are able to submit bids and the buyer sets a demanded quantity. The bids comprise a given quantity and price. After all parties put the information to market operator, the price in which market demand and supply quantities are met is called the clearing price. All bids are purchased for this clearing price. This mechanism repeats for next time window. The task is to simulate the market operator role.
Moreover, suppose we have three (but generally more) markets that sell the same goods, each of them has a different set of bids. For each time window, the buyer sets one demanded amount and would like to know the minimum clearing prices and a set of activated bids on all markets.
My original idea was to model a one market situation as a knapsack problem in which I try to buy a given amount $W$ of a resource and minimize the purchase price $c^Tx$. The resulting problem that usually takes a form of the following optimzation problem.
$\min \sum c^Tx, s.t.$
$w^Tx \geq W$
Where $c \in \mathbb{R}^n$ is the vector of bid prices, $w \in \mathbb{R}^n$ is the amount of resource offered, $W \in R^+$ is the demanded amount. $x \in {[0,1]}^n$ is the vector of bid activations and is a variable (1 corresponds to a full activation). The result of this problem is the vector of bid activations $x^*$.
However when using the knapsack problem on the following situation, the solution does not lead to the optimal solution. See the figure below.
The figure illustrates a situation on two markets. Blue market comprises two bids offering amounts $q_1$ and $q_2$ for prices $p_1$ and $p_2$. Yellow market comprises one bid offering amount $q_3$ for price $p_3$. The demanded amount $q_D$ is shown as a red line. According to the knapsack problem the optimal solution would be to acquire bids from blue market resulting in an activation of bid 1 and partial activation of bid two. The clearing price is $p2$ and the total price is $p_2W$. The expected solution would be to take bid one from blue market. The clearing price is $p_1$ for amount $q_1$ and partially accept bid ($q_d - q_1$) from yellow market for price $p_3$. The resulting total cost $p_3(q_d-q_1) + p_1q_1$ is lower than $p_2q_d$.
So I need to solve a different problem in which the prices of bids are not fixed. I try to find a minimum price $p$ that will solve the above optimization problem. The price $p \in \mathcal{C}, \mathcal{C} = \{c_i|\forall i \in \mathcal{I}\}$. The optimal price will apply to all activated bids (even to the cheaper ones).
Hence the optimization problem is now extended with a variable price that can take values only from a set of values corresponding to the prices of the bids. The chosen price is then applied to all bids in the knapsack. This probably leads to a non-convex optimization problem.
Anyone know a way how to define and solve this type of problems?
A possible solution that came to my mind is the following
$\min{p} \ \ s.t.$
$w^Tx \geq W $
$\forall i \in \mathcal{I}, c_ix_i \leq p x_i$
Where $p \in \mathbb{R}^+$ is the variable and $\mathcal{I} = \{1,\dots,n\}$ and again $c \in \mathbb{R}^n, w \in \mathbb{R}^n, W \in R^+$ are given and $x \in {[0,1]}^n$ is the variable
The solution still seems clear. For any one market, sort its bids from lowest price to highest price, then start summing the supply quantities starting with the lowest price bid. Continue summing until your demanded quantity is met or exceeded. The bid that did so sets the clearing price. If your demand was exceeded, adjust the activations $x_i$ for the winning bidders down until $w^Tx = W$ (activations for losing bidders are $0$). How this is done doesn't matter as far the problem is concerned, as the price you pay remains $pW$ no matter how you make the adjustments, where $p$ is the clearing price. But I think lowering only the highest winning bidder's activation while leaving all lower bidders at $x_i = 1$ makes the most sense.
If you are splitting the order over several markets to get the lowest overall price, the solution is almost the same. Order all bids from all markets by price, and sum quantities starting with the lowest prices and moving up until your demand $W$ is met. These are the winning bidders. The clearing price for each market is the price of the highest winning bid from that market. In the market which had the highest winning bidder, you can adjust the activations for that market as you please to reduce the total purchase to exactly $W$, but in the other markets, all winning bids must be at full activation to get the lowest overall price (any lowering of activation in these markets would have to be matched by raising activation in the higher priced market).