Jérôme De Boeck
email: jdeboeck@ulb.ac.be

Luce Brotcorne
email: luce.brotcorne@inria.fr

Bernard Fortz
email: bernard.fortz@ulb.ac.be

Strategic Bidding in Price Coupled Regions

Keywords: Strategic bidding, Bilevel optimization, MPEC, Extended formulations, MILP reformulation

published or not. The documents may come

Introduction

Electricity markets evolved in recent years to a deregulated system where Generation Companies (GC) and retailers compete and place hourly bids in day-ahead markets. Hourly spot prices for the next day are determined by a Market Operator (MO) that selects bids in order to maximize the global welfare. In order to maximize its profit, a GC competing in day-ahead markets needs an accurate evaluation of the hourly spot price of electricity in order to establish an appropriate production plan. In Europe, several dayahead markets have been grouped through an international transmission network in the Price Coupling of Regions 1 (PCR) project. The global market equilibrium is determined by the MO who maximizes the global welfare of all markets in order to increase competitivity between the actors. The MO determines the market equilibrium and the resulting hourly spot prices for electricity as well as the quantities of electricity traded in each day-ahead market of the PCR. Coupling day-ahead markets makes it harder for GCs to evaluate the spot prices as they are influenced by local bids, bids from other markets and transmission constraints.

In this paper, we consider the Bidding Problem (BP) of a GC maximizing its profit in coupled day-ahead markets. A price-maker perspective is taken, in the sense that the production of the GC is considered high enough to impact the market prices. Our model integrates a detailed Unit Commitment (UC) formulation of the production planning problem. The Bidding Problem is a hierarchical sequential Stackelberg game, where one player, defined as the leader, can make a decision and commit a strategy taking into account the reaction of other players, defined as followers. In the problem considered in this paper, the leader is a GC that determines a production schedule and a bidding price for its production, while the follower is the MO which fixes the prices induced by the market equilibrium. In order to compute its optimal bidding strategy, the GC must take into consideration the impact of its bid on the market equilibrium. We focus here on a GC, but our models and methods could easily be adapted for the case of a bidding retailer.

We assume that the GC bids at the spot price and sells the whole quantity it offers. Furthermore, we consider that the GC has a full knowledge of other bids in the market. This information is typically estimated through statistical [START_REF] Morales | Integrating Renewables in Electricity Markets[END_REF] or machine learning [START_REF] Chen | Learning from past bids to participate strategically in day-ahead electricity markets[END_REF] methods. The UC problem consists in establishing a minimum cost production plan for a fixed demand. It involves characteristics such as quadratic production costs, start-up and shut-down costs, ramping up and down constraints, minimum on and off time and transmission network constraints (Koltsaklis et al., 2018). This problem has been widely studied in the literature (Tahanan et al., 2015), and is challenging by itself as it is a non-convex optimization problem. Adding market equilibrium conditions increases significantly the complexity of the problem as the demand is not fixed anymore but depends on the bids proposed by competitors and the resulting the market equilibrium. The study of the UC problem is out of the scope of this paper, but the methods presented here can be adapted to any UC formulation.

As described above, we assume that the GC is a price makers since it can influence the hourly spot prices. On the other hand, if a GC has a small market share, it has a negligible influence on the market price and is considered as a price-taker. In this case, spot prices are considered as given beforehand.

The literature on bidding strategies mostly focuses on the price-taker case. The resulting problems are usually modeled as a UC problem with a couple of additional constraints [START_REF] Li | Modeling methods for genco bidding strategy optimization in the liberalized electricity spot markete: A state-of-the-art review[END_REF]Steeger et al., 2014). Price-taker formulations are easier to solve than price-maker ones since the reaction of the market to the bids of the GC can be ignored. The drawback of such formulations is the risk of obtaining suboptimal solutions because of a wrong estimation of the spot prices, resulting in a loss of profit or leading to an infeasible production plan.

In contrast, price-maker formulations, as considered in this paper, make an accurate evaluation of spot prices by taking into consideration the reaction of the market to the bids of the GC. The resulting problems are single-round Stackelberg games that are typically modeled as bilevel optimization problems.

A deterministic formulation of the price-maker bidding problem was proposed by de la [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF]. The first level is a UC model and the GC bids at the spot prices. The spot prices are discretized to the set of bidding prices of competitors and the spot price at each time period is represented as a stepwise function in the offered quantity. This allows to formulate the problem as a MILP with a limited number of binary variables. Other deterministic price-maker problems consider stepwise bidding curves [START_REF] Bakirtzis | Electricity producer offering strategies in day-ahead energy market with step-wise offers[END_REF][START_REF] Dalby | Stratégies d'offre sur le marché électrique[END_REF][START_REF] Ruiz | Pool strategy of a producer with endogenous formation of locational marginal prices[END_REF] or bidding at marginal costs [START_REF] Dalby | Stratégies d'offre sur le marché électrique[END_REF][START_REF] Kardakos | Optimal bidding strategy in transmission-constrained electricity markets[END_REF]. The bilevel formulations proposed in these papers are reformulated by using Karush-Kuhn-Tucker (KKT) first order optimality conditions to obtain a single level Mathematical Program with Equilibrium Constraints (MPEC) [START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF]. In all these models, the KKT conditions are linearized through classical techniques, resulting in computationally challenging formulations. In most papers, a general UC formulations is used containing general electricity productions constraints. Some papers focus on bidding with a specific type of generators that strongly influence the UC model and the resulting bidding strategy [START_REF] Cruz | Strategic bidding for price-maker producers in predominantly hydroelectric systems[END_REF].

A single day-ahead market is considered by [START_REF] Bakirtzis | Electricity producer offering strategies in day-ahead energy market with step-wise offers[END_REF], for a single time period. The GC maximizes its profit by finding an optimal bidding curve with steps without specific restrictions on offered prices. A discretization of the prices through a binary expansion [START_REF] Pereira | Strategic bidding under uncertainty: A binary expansion approach[END_REF] is performed to eliminate products of continuous variables and linearize the formulation. The large size of the resulting formulation limits the size of the instances considered. The aim in [START_REF] Dalby | Stratégies d'offre sur le marché électrique[END_REF] is to minimize the difference between the profit and the production costs in order to recover start-up costs based on market equilibrium constraints from [START_REF] Bakirtzis | Electricity producer offering strategies in day-ahead energy market with step-wise offers[END_REF].

Formulations with various types of transmission constraints have also been proposed [START_REF] Ruiz | Pool strategy of a producer with endogenous formation of locational marginal prices[END_REF][START_REF] Kardakos | Optimal bidding strategy in transmission-constrained electricity markets[END_REF] where several day-ahead markets are coupled. Transmission constraints in these models make the model very complex. To compensate the difficulty added by the transmission network, [START_REF] Ruiz | Pool strategy of a producer with endogenous formation of locational marginal prices[END_REF] consider a UC problem composed of only ramping up and down constraints, avoiding start-up and shut-down cost, and [START_REF] Kardakos | Optimal bidding strategy in transmission-constrained electricity markets[END_REF] consider that local demands are fixed in advance and do not consider ramping constraints in their UC model.

Strong hypotheses are always made in price-maker formulations due to the inherent complexity of such an approach. Only a limited proportion of market regulations are considered in state-of-the-art studies and the UC formulation is generally simplified.

In this paper, we propose a bilevel formulation for BP. We reformulate it as an MPEC by applying KKT conditions on the market equilibrium subproblem. General properties of this problem are studied to derive new valid inequalities and heuristic methods. A novel extended formulation [START_REF] Conforti | Extended formulations in combinatorial optimization[END_REF] describing the spot prices by using special ordered sets of type 1 (SOS) [START_REF] Beale | Global optimization using special ordered sets[END_REF] allows to consider only a limited number of possible spot prices in an optimal bidding strategy. An analysis of the impact of the transmission network reduces the number of spot sprices to consider even more. The SOS used to represent the possible spot prices leads to new valid inequalities using RLT (Sherali and Adams, 1999). These new inequalities improve significantly the quality of the linear programming relaxation of the formulation. The resultinr MILP formulation can also easily be adapted for the case of bidding at marginal costs.

Two heuristic methods are proposed to solve large size instances in moderate CPU times. The properties of the primal and dual formulations of the market equilibrium problem are analysed in order to derive a general Iterative Aggregation-Disaggregation algorithm (IAD) [START_REF] Rogers | Aggregation and disaggregation techniques and methodology in optimization[END_REF] which can be applied for coupled markets as in PCR. The SOS constraints are also used to run a novel SOS-narrowing heuristic that narrows the values of the spot prices during the branch and bound procedure in order to limit the size of the branching tree, improving significantly the solving time. This SOS-narrowing heuristic is generic and can be adapted to any formulation containing SOS of type 1.

Our computational experiments confirm and highlight our main contributions:

• the reformulation proposed, combined with new valid inequalities and preprocessing techniques that reduce the number of variables, allow to solve instances with over 50 competitors and 5 generators;

• the proposed heuristics deliver very high quality solutions in a short computation time;

• thanks to the algorithmic improvements, a more detailed UC model can be handled in the master problem;

• adding the transmission network to the model and a more detailed UC model represents a strong step forward towards a more realistic and applicable model;

• the results also highlight the risk of a loss for the bidding GC when ignoring the new aspects we introduced in the model.

The remainder of the paper is organized as follows. Section 2 defines the bidding problem and proposes a bilevel formulation as well as a single level reformulation as a MPEC. An extended linearized formulation obtained by discretizing the spot prices is presented in Section 3. In Section 4, we show how the number of binary variables can be reduced by a careful study of the properties of bidding prices. Section 5 presents an adaptation of the formulation to the case of bidding at marginal costs. Heuristic methods are proposed in Section 6. The results of our computational experiments are presented and analysed in Section 7. Section 8 concludes the paper.

Step 1 :

Step 2 : Bidding ok the GC and the competitors Response of the Market Operator to the participants

Problem definition

The Bidding Problem (BP) is a multi-period price-maker problem where a GC maximizes its profit by proposing hourly bids for selling its production on the day-ahead electricity market. The production schedule of the GC results from the optimal solution of a UC problem, and electricity spot prices are computed to form a market equilibrium. In addition, the computation of spot prices takes into account different regions coupled by a capacitated transmission network. The GC and competitors propose bids to the MO that determines the spot price for each time period and the quantities traded between the actors. A bid is composed of a unit price and a quantity and the MO can select any proportion of a bid proposed by a producer or a retailer in order to obtain the market equilibrium solution maximizing the global welfare. Bids of the competitors are considered as known. The day-ahead markets in different regions are represented by a set of nodes N connected through a capacitated transmission network coordinated by the MO. The GC and competitors can bid in several day-ahead markets as illustrated in Figure 1.

The MO imposes fixed minimum and maximum bidding prices λ t and λ t for each time period t ∈ T . It fixes the local spot λ t n price for each period t ∈ T and node n ∈ N such that local seller bids under the spot price are fully bought and bids above are not bought and conversely for local buyer bids. The bids that are bought are said to be in-the-money, those that are not are out-of-the-money in market regulations (EUPHEMIA, 2016). Power exchanges are possible through a set of capacitated transmission lines E between the day-ahead markets.

A solution of BP is represented by a set of bids {(λ t n , p t n )} t∈T,n∈N from the GC such that p t n is the bidden quantity at node n, meaning the GC aims to bid at the spot prices by taking into consideration the reaction of the market to its bid. We consider that the full bidden production of the GC is dispatched to retailers by the MO. Note that bidding all the produced electricity at a single price is not restrictive when considering the bids of the competitors as known. Indeed, [START_REF] Bakirtzis | Electricity producer offering strategies in day-ahead energy market with step-wise offers[END_REF] proposed bidding curves in order to diversify bidding prices and concluded that this is of no interest in the deterministic case. In order to ensure selling bids, the GC must only bid under the spot price of electricity which can be seen as an upper bound for bidding prices for the GC.

We denote by P n the set of feasible solutions of the UC in node n, where p n = {p t n } t∈T ∈ P n is a vector of resulting quantities offered on market n. The cost for producing p n is denoted by c(p n ). Note that the GC is free to produce more than the quantities offered on the market. In order to guarantee feasibility of BP, we assume for each period t ∈ T and node n ∈ N that the maximum production capacity of the GC, Q t n , is smaller than the total demand in n and that there exists a feasible solution when the GC does not participate in market n.

In the following, we first present a linear formulation for the market equilibrium problem of the MO with p t n as parameter to provide a model integrating a fixed bidden production by a GC that must be traded by the MO. A bilevel formulation of BP is then provided and reformulated as a bilinear MPEC by using complementarity constraints arising from the market equilibrium problem.

Unit commitment model

The UC is a challenging problem to solve in itself. In most bidding problems presented in the literature, a simplified version is used. So far, only a few UC specific components have been considered in price-maker bidding problems constrained by a transmission network. Only start-up and shut-down costs are considered by [START_REF] Kardakos | Optimal bidding strategy in transmission-constrained electricity markets[END_REF] while [START_REF] Ruiz | Pool strategy of a producer with endogenous formation of locational marginal prices[END_REF] integrates only ramping up and down constraints.

A more detailed UC formulation is composed of several specific components such as:

• non-linear production costs,

• startup and shut down costs, introducing binary decision variables and a non continuous objective function,

• ramping up and down capacities, limiting the variation of production from on time period to another for each generator, linking the time periods of the problem,

• minimum up and down times, forcing generators to be turned on or off for a minimum time period, linking again the time periods.

Even production costs cannot be modelled through linear expressions and are often approximated through linearization techniques.

In the present paper, we propose general market equilibrium constraints for a GC bidding in day-ahead markets that can be adapted to any UC formulation. In the computational experiments, a detailed stateof-the-art deterministic UC formulation presented by [START_REF] Ostrowski | Tight mixed integer linear programming formulations for the unit commitment problem[END_REF] is used. This formulation is presented in Appendix D.

Market equilibrium problem

The actors in coupled day-ahead markets are divided into a set of buyers B and a set of sellers S, partitioned into sets B n and S n , n ∈ N of buyers and sellers by node. Each actor bids in its local day-ahead market. Each buyer b ∈ B defines a bid (π t b , Q t b ) composed of a price π t b and a strictly positive quantity Q t b . In the market equilibrium solution computed by the MO, a proportion x t b of bid b ∈ B is traded at period t. The same notation applies for sellers s ∈ S. The transmission network is represented by a graph (N, E), where a maximum capacity C max nm > 0 is associated with each edge nm ∈ E. The set of neighbors of a node n ∈ N is denoted Θ n . Set A is the set of arcs obtained by replacing each edge in E by two arcs in opposite directions. The flow f t nm , nm ∈ A, t ∈ T corresponds to the flow from node n to node m at period t. The objective in the market equilibrium problem is to maximize the global welfare.

In a day-ahead market without transmission constraints, and where only step bids composed of a unit price and a quantity are considered, the market equilibrium for a given period is determined by the intersection of the aggregated production and demand curves as illustrated in Figure 2. The global welfare corresponds to the surface between the demand and the production curves and the spot price is the price at the intersection of the two curves. We consider that if the intersection of both curves results in multiple points, the spot price and quantity traded are settled at their maximum value [START_REF] Hogan | Multiple market-clearing prices, electricity market design and price manipulation[END_REF].

The marked equilibrium problem considered in this paper is a simplified version of the model proposed by [START_REF] Madani | Computationally efficient mip formulation and algorithms for european day-ahead electricity market auctions[END_REF] for European deregulated electricity markets considering only step bids. As the GC intents to bid at the spot price and to sell the entirety of the quantity offered on the market, we consider that the full production is dispatched to retailers by the MO. The market equilibrium problem is Figure 2: Bids and spot-price for a given time period decomposable by time period. Given the quantities p t n offered by the GC in period t, the market equilibrium problem (M E t ) is formulated as follows:

(M E t ) max n∈N ( b∈Bn π t b Q t b x t b - s∈Sn π t s Q t s x t s ) (1a) s.t. b∈Bn Q t b x t b - s∈Sn Q t s x t s + m∈Θn (f t nm -f t mn ) = p t n n ∈ N (λ t n ) (1b) 0 ≤ x t b ≤ 1 n ∈ N, b ∈ B n (y t b ) (1c) 0 ≤ x t s ≤ 1 n ∈ N, s ∈ S n (y t s ) (1d) 0 ≤ f t nm ≤ C max nm nm ∈ A (r t nm ) (1e)
where dual variables are indicated next to constraints. The objective function (1a) corresponds to the global welfare. Constraints (1b) are the balance constraints at each node, imposing the production offered by the GC is bought. Constraints (1c)-(1e) are bounds on variables. A noticeable difference with a market without transmission constraints is that the MO may be limited in its choice of bids because of transmission constraints. Note that under the proposed assumptions, M E t admits a feasible solution for each time period for any production of the GC.

An optimal solution of M E t produces a solution of the market equilibrium problem. The spot price in a period t and market n is given by the optimal value of dual variable λ t n [START_REF] Baker | A linear programming ramework for cost allocation and external acquisition when reciprocal services exist[END_REF][START_REF] Balachandran | Joint cost allocation for multiple lots[END_REF].

The dual of M E t for period t is given by:

(M ED t ) min n∈N (p t n λ t n + b∈Bn y t b + s∈Sn y t s + m∈Θn C max nm r t nm ) (2a) s.t. Q t b λ t n + y t b ≥ π t b Q t b n ∈ N, b ∈ B n (x t b ) (2b) -Q t s λ t n + y t s ≥ -π t s Q t s n ∈ N, s ∈ S n (x t s ) (2c) λ t n -λ t m + r t nm ≥ 0 nm ∈ A(f t nm ) (2d) y t b , y t s , r t nm ≥ 0 (2e)
Variables y t b and y t s represent the welfare obtained from a bid. Some observations can be made from the primal and dual of the market equilibrium problem about the values of variables in a market equilibrium. Let us consider a market equilibrium and two adjacent nodes n and m. If r t nm > 0, then f t nm = C max nm by complementarity constraints as r t nm is the dual variable of (1e). Variable r t nm only appears in (2d) in the constraints of the dual and must be minimized in the objective function (2a), thus r t nm = λ t m -λ t n if λ t m -λ t n ≥ 0. Variables r t nm represent the spot price difference between nodes m and n if this difference is positive and 0 otherwise. Constraint (2d) can be strengthened as follow as at most one term out of r t nm and r t mn is strictly positive:

λ t n -λ t m + r t nm -r t mn = 0 (3)
Two nodes n and m can have different spot prices if and only if |f t nm -f t mn | = C max nm . Furthermore, if r t nm > 0, line nm ∈ A is said to be saturated. In this case, λ t n < λ t m , meaning that when considering two nodes linked by a transmission line, the exporting one has the lowest spot price.

When considering transmission constraints, the market equilibrium is harder to determine than finding the intersection of two curves, as in Figure 2. For instance, if the production bids are very cheap in a bidding area n, the MO might not be able to buy all of them because of the limited capacity of transmission lines. This can potentially lead to different spot prices in different bidding areas. Figure 3 illustrates the impact of the transmission network on a given time period t for the following bidding data:

• N = {1, 2}; E = {(1, 2)} • C max 1,2 = 3 GW h • The GC is bidding in node 1
• B 1 = {(80, 0.5), (75, 0.5), (60, 1), (37, 0.5), (25, 0.5)}

• S 1 = {(10, 1), (20, 1), (30, 1.5), (35, 0.5), (40, 0.5)}

• B 2 = {(90, 1), (70, 1.5), (63, 0.5), (58, 0.5), (50, 1), (43, 0.6), (41, 0.4)}

• S 2 = {(25, 1), (33, 1), (38, 0.5), (47, 1), (52, 1.5)} Bids in node 1 and node 2 are represented respectively in blue and red. Demand and production bids are represented respectively with a full line and dashed line. The upper graph represents the aggregated demand and production curves by node and the resulting market equilibriums when the transmission network is ignored. The spot price in node 1 is 30 e/MW and a spot price in node 2 is 52 e/MW. The upper-left graph represents the aggregated curves considering both nodes linked by the transmission network. The resulting spot price is 43 e/MW in both nodes. A demand of 2GW and a production of 4.5 GW bought in node 1. The exceeding production of 2.5 GW is sent to node 2 to complete the local demand, respecting the capacity of the transmission network. The upper-right graph represents the aggregated curves considering both nodes and an additional production bid (20,0.3) placed in node 1 and represented in green. The exceeding production bought in node 1 is of 2.8 GW and can be sent through the transmission network to node 2, resulting in a market equilibrium with a global spot price of 41 e/MW. The extra bid is fully bought and the demand bid (41,0.5) in node 1 is now only partially bought. The middle-left graph consider an additional production bid of (20,0.8), reaching the maximum transmission capacity of the transmission line, breaking the obligation of having equal spot prices in nodes 1 and 2. As node 1 is exporting, the spot price in node 1 is smaller or equal than in node 2. The resulting local spot prices illustrated in the middle-right figure are of 40 e/MW in node 1 and of 41 e/MW in node 2. In both nodes, all production bids under the local spot price are fully bought as all demand bids are above the spot price. Bids at the spot price are partially bought up to the dot on the corresponding curve. The bottom-left graph represents the aggregated curves with an extra bid (20,1.3) placed in node 1. The exceeding production in node 1 is now of 3.3 GW, which strictly exceeds the capacity of the transmission network. The capacity limiting the objective value of the market equilibrium problem of the MO, variable r t 1,2 > 0 and the spot price cannot be equal in both nodes. The bottom-right Aggregated bidding curves per node, local spot prices : 30 e/MWh and 52 e/MWh

1 2 C max 1,2
Aggregated bidding curves of both nodes, Additional bid of (20,0.3),

f t 1,2 = 2.5 < C max 1,2 , f t 1,2 = 2.8 < C max 1,2 , Global spot price : 43 e/MWh
Global spot price : 41 e/MWh Additional bid of (20,0.8),

Local marginal spot prices resulting

f t 1,2 = 3 = C max 1,2 ,
from the additional bid (20,0.8), possible local spots prices: Additional bid of (20,1.3),

f t 1,2 = 3, λ t 1 = 40e/MWh, λ t 2 = 41e/MWh:
Local marginal spot prices resulting

f t 1,2 =3.3 > C max 1,2 , from the additional bid (20,1.3), forced local spot prices f t 1,2 = 3, λ t 1 = 37e/MWh, λ t 2 = 41e/MWh:
q t 1 q t 2 q t 3 q t 4 q t 5 q t 6 λ t λt 1 λt 2 λt 3 λt 4 λt 5 λt 6
Total bidden quantity (GW) Spot price (e/MWh) Figure 4: Spot price without transmission network graph represents the market equilibrium obtained with the additional bid. As without the additional bid, the spot price in node 2 stays at 41 e/MW, but falls to 37 e/MW in node 1. Note that once the transmission line from 1 to 2 is at its maximum capacity, the spot price in node 2 cannot decrease when increasing the production bidden in node 1. This can play at the advantage of the GC if some production is bidden in node 2 and can be sold at a higher price than if all bids are aggregated in a single bidding area.

In a market equilibrium solution, we define a group as a set of connected nodes having the same spot price at a given time period. During each time period t, the nodes N are partitioned into a set of groups G t in which r t nm = 0 for all n, m ∈ G, G ∈ G t . Given the production of competitors, the spot prices can be bounded considering the offer of the GC on the market.

Lemma 1. Consider a set of quantities p t n for the market equilibrium problem in period t, the resulting market equilibrium solution at period t with groups G t and the spot prices λ t n . Increasing a quantity p t n cannot increase the spot price in any group.

Proof. Consider a bid s ∈ S n in a group G ∈ G t such that increasing Q t s of a quantity q in period t increases the spot price in node n in group G ∈ G t . If π t s > λ t n , then the extra quantity q is not bought and the spot prices remain unchanged. Otherwise, π t s = λ t n and the spot price λ t G can increase only if after modifying the bidden quantities, quantity q is fully bought in addition to a positive quantity q not previously sold in G. Buying q is performed if and only if it increases the global welfare. If so, the quantity q bought in G could have been bought without increasing Q t s contradicting the initial market equilibrium hypothesis.

It follows from Lemma 1 and the assumption that the spot price is maximal, that λ t n can be expressed as an upper step-wise decreasing function in p t m for all m ∈ N as illustrated in Figure 4. Values q t i are quantities at which the spot price decreases. de la [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF] proved that these values are fixed parameters when considering a single day-ahead market but vary depending on all quantities p t n , n ∈ N when considering coupled markets.

Market equilibrium constraints

To model BP, we propose a bilevel formulation where the GC acts as the leader. It maximizes the profit arising from selling the production, determined by the solution of the UC problem, at spot prices. The MO is the follower determining the market equilibrium solution:

(BP -BL) max p t n n∈N t∈T λ t n p t n -c(p n ) (4a) s.t. p n ∈ P n n ∈ N (4b) ∀t ∈ T min λ t ,y t b ,y t s ,r t nm n∈N (p t n λ t n + b∈Bn y t b + s∈Sn y t s + m∈Θn C max nm r t nm ) (4c) s.t. Q t b λ t n + y t b ≥ π t b Q t b n ∈ N, b ∈ B n (4d) -Q t s λ t n + y t s ≥ -π t s Q t s n ∈ N, s ∈ S n (4e) λ t n -λ t m + r t nm -r t mn = 0 nm ∈ A (4f) y t b , y t s , r t nm ≥ 0 (4g)
The leader in the first level controls the quantities p t n produced and offered on the market, as solution of problem (4b). The follower in the second level controls the remaining variables, among which, the spot prices λ t n , and is formulated by M ED t for each time period. Under the hypotheses considered in the previous section regarding the bids of competitors, the optimal value of the second level is well defined for any production levels p t n as the problem is a feasible linear program. Assuming that c(p n ) is an increasing lower semi-continuous function in p n , the optimal value of BP is well defined. Classical unit commitment models respect this assumption since i) production costs are generally quadratic, ii) discontinuities appear with start-up costs and iii) the spot prices are upper semi-continuous functions. The objective function of ( 4) is thus an upper semi-continuous function in p t n for all n ∈ N admitting a global maximum.

Several optimal solutions can exist in the second level if several bids are made at the spot price and the MO can choose any subset of these bids to satisfy the demand. Furthermore, being the dual variables of the balance constraints, the spot prices can be degenerated, i.e. several different values are possible in an optimal solution. Therefore, the second level of the proposed bilevel formulation is not a point-to-point map for values of variables p t n and an optimistic assumption is made. This assumption considers that the follower always chooses the best solution for the leader among the set of optimal solutions of the second level. This yields the following properties for BP-BL:

• the GC has priority over the competitors when bidding at the same price, which can practically be ensured by decreasing the optimal bidding prices by a small amount,

• the MO maximizes spot prices in the chosen market equilibrium solution, which satisfies the assumption made on the market equilibrium problem.

Since it is linear and continuous, the follower problem can be reformulated as a set of equilibrium constraints by using complementarity constraints of the market equilibrium primal and dual formulations:

x t b Q t b λ t n + y t b -π t b Q t b = 0 t ∈ T, n ∈ N, b ∈ B n (5a) x t s -Q t s λ t n + y t s + π t s Q t s = 0 t ∈ T, n ∈ N, s ∈ S n (5b) y t b 1 -x t b = 0 t ∈ T, n ∈ N, b ∈ B n (5c) y t s 1 -x t s = 0 t ∈ T, n ∈ N, s ∈ S n (5d) (C max nm -f t nm )r t nm = 0 t ∈ T, nm ∈ A (5e)
The bilinear terms x t b y t b and x t s y t s can be replaced by y t b and y t s by (5c) and (5d). We can then rewrite constraints (5a) and (5b) as:

y t b = -Q t b λ t n x t b + π t b Q t b x t b t ∈ T, n ∈ N, b ∈ B n (6a) y t s = Q t s λ t n x t s -π t s Q t s x t s t ∈ T, n ∈ N, s ∈ S n (6b)
Let us replace r t nm in (5e) by λ t m -λ t n :

C max nm r t nm = f t nm (λ t m -λ t n ) t ∈ T, nm ∈ A (7)
Lemma 2. Constraints ( 7) are valid for BP-BL.

Proof. Constraints (5e) can be rewritten as:

C max nm r t nm = f t nm r t nm
As previously mentioned r t nm represents the spot price difference between nodes m and n, λ t m -λ t n , if this difference is positive and 0 otherwise. Thus,

• if r t nm = 0, then both sides equal 0,

• if r t nm > 0, then r t nm = λ t m -λ t n .
Constraints ( 6) and ( 7) are called reduced complementarity constraints. Let P 1 be the solution space of constraints of M E t (1) and M ED t (2) combined with the complementarity constraints (5), which defines the optimal solution space of M E t , and P 2 be the solution space of the same constraints M E t (1) and M ED t (2) combined with the reduced complementarity constraints ( 6) and ( 7).

Lemma 3. The solution spaces defined by P 1 and P 2 are equivalent.

Proof.

• P 1 ⊆ P 2 : consider a solution (x, y, λ, π, r, f ) ∈ P 1 . This solution satisfies (7) as described in Lemma 2. The solution also satisfies (6) as these constraints are derived from (5) which are satisfied by (x, y, λ, π, r, f ).

• P 2 ⊆ P 1 : consider a solution (x, y, λ, π, r, f ) ∈ P 2 . By substituting y t b in (2b) using (6a), we obtain:

(-λ t n + π t b )Q t b x t b ≥ (-λ t n + π t b )Q t b (8) If * π t b > λ t n , constraints (1c) and (8) lead to x t b = 1, * π t b = λ t n , constraint (6a) implies that y t b = 0, * π t b < λ t n , constraint (
6a) implies that x t b = 0 and y t b = 0 as these variables are positive.

Thus for any t ∈ T, b ∈ B, either y t b = 0 or x t b = 1, and constraints (5c) are satisfied by (x, y, λ, π, r, f ). Similarly, constraints (5d) are implied by (1d), ( 8) and (6b). As constraints (5c) and (5d) are valid for P 2 , y t b , y t s can be replaced by x t b y t b and x t s y t s in constraints (6a) and (6b) respectively, leading to constraints (5a) and (5b). Constraint (5e) is also satisfied by (x, y, λ, π, r, f ):

if r t nm = 0, then this constraint is trivially satisfied, if r t nm > 0, then r t nm = λ t m -λ t n . Constraints (5e) are equivalent to constraints (7) by substitution.

The reduced complementarity constraints ( 6)-( 7) of Lemma 3 combined with those of the primal and dual of the market equilibrium problem can replace the second level problem of BP-BL. Variables y t b , y t s can be substituted by using (6a) and (6b). This results in the following MPEC:

(BP -M P EC) max n∈N t∈T λ t n p t n -c(p n ) (9a) s.t. p n ∈ P n n ∈ N (9b) b∈Bn Q t b x t b - s∈Sn Q t s x t s + m∈Θn (f t nm -f t mn ) = p t n t ∈ T, n ∈ N (9c) (λ t n -π t b )(1 -x t b ) ≥ 0 t ∈ T, n ∈ N, b ∈ B n (9d) (-λ t n + π t s )(1 -x t s ) ≥ 0 t ∈ T, n ∈ N, s ∈ S n (9e) (-λ t n + π t b )x t b ≥ 0 t ∈ T, n ∈ N, b ∈ B n (9f) (λ t n -π t s )x t s ≥ 0 t ∈ T, n ∈ N, s ∈ S n (9g) λ t n -λ t m + r t nm -r t mn = 0 t ∈ T, nm ∈ A (9h) C max nm r t nm = f t nm (λ t m -λ t n ) t ∈ T, nm ∈ A (9i) 0 ≤ x t b ≤ 1 t ∈ T, n ∈ N, b ∈ B n (9j) 0 ≤ x t s ≤ 1 t ∈ T, n ∈ N, s ∈ S n (9k) 0 ≤ f t nm ≤ C max nm t ∈ T, nm ∈ A (9l) r t nm ≥ 0 t ∈ T, nm ∈ A (9m)
Constraints (9c)-(9m) define market equilibrium constraints for all t ∈ T . Constraints (9c) are the balancing contraints, constraints (9d)-(9g) ensure bids in-the-money are bought and bids out-of-the-money are rejected. Constraints (9h)-(9i) link the flows with the differences of spot prices between the bidding areas.

MILP reformulation

BP-MPEC contains a continuous bilinear objective and several bilinear constraints where all bilinear terms contain a spot price variable. The linearization of the bilinear terms is challenging since all products involve continuous variables. Let Λ t be the ordered set of all bidding prices of competitors at period t over all bidding areas including the minimum and maximum bidding prices λ t and λ t allowed by the MO. Prices in Λ t are denoted by λt i , i ∈ I t where I t is the set of price indices of Λ t .

Lemma 4. There exists an optimal solution of BP such that λ t n ∈ Λ t for all n ∈ N, t ∈ T .

Proof. Consider an optimal solution with a spot price λ t n that is not in Λ t . Increasing λ t n to λt i = min{λ ∈ Λ t |λ > λ t n } preserves the validity of constraints (9d)-(9g) and potentially increases the objective value. For all m ∈ Θ n :

• if r t nm = 0, λ t m is increased to λt i in order to preserve the validity of constraints (9h) and (9i). • if r t nm > 0, r t nm is decreased by the same amount as λ t n is increased in order to satisfy constraints (9h) and (9i). Variable r t nm may become negative in this procedure if λ t m ∈]λ t n , λt i [. In this case, λ t m is not in Λ t either and can also be increased to λt i .

Once the increase of λ t n is propagated to r t nm and λ t m for each adjacent node m, the procedure can be iterated until all spot prices are in Λ t .

It follows from Lemma 4 that relevant spot prices values λ t n in an optimal solution can be discretized to values in Λ t by using Special Ordered Sets (SOS) of type 1 [START_REF] Beale | Global optimization using special ordered sets[END_REF]. Consider binary variables z t in , i ∈ I t ,

z t in = 1 if λ t n = λt i 0 otherwise.
The following constraints restrict variables λ t n in BP-MPEC to values in Λ t :

i∈I t z t in = 1 t ∈ T, n ∈ N (10a) λ t n = i∈I t λt i z t in t ∈ T, n ∈ N (10b)
Sets {z t in } i∈I t for all t ∈ T and n ∈ N are SOS of type 1, meaning exactly one variable in each set must be different from 0. Constraints (10a)-( 10b), lead to an extended formulation of BP-MPEC where the continuous spot price variables are substituted by binary variables. All products of continuous variables in BP-MPEC can be rewritten as the product of a binary and a continuous variable which can easily be linearized. The following variables and inequalities are used for linearization for all t ∈ T, n ∈ N, i ∈ I t :

P t in = z t in p t n 0 ≤ P t in ≤ Q t n z t in P t in ≤ p t n P t in ≥ p t n -Q t n (1 -z t in ) (11a) X t ib = z t in x t b 0 ≤ X t ib ≤ z t in X t ib ≤ x t b X t ib ≥ x t b + z t in -1 b ∈ B n (11b) X t is = z t in x t s 0 ≤ X t is ≤ z t in X t is ≤ x t s X t is ≥ x t s + z t in -1 s ∈ S n (11c)
F t inm = z t in f t nm 0 ≤ F t inm ≤ C max nm z t in F t inm ≤ f t nm F t inm ≥ f t nm -C max nm (1 -z t in ) m ∈ Θ n (11d) F t inm = z t in f t mn 0 ≤ F t inm ≤ C max nm z t im F t inm ≤ f t nm F t inm ≥ f t nm -C max nm (1 -z t im ) m ∈ Θ n (11e)
Linearization constraints as (11) usually introduce a large LP gap due to the introduction of additional variables that are weakly linked to the initial model. Valid inequalities linking these new variables and the initial variables can tighten the formulation. By multiplying constraint (10a) by variables p t n , x t b , x t s and f t nm respectively we obtain the following constraints:

i∈I t P t in = p t n t ∈ T, n ∈ N (12a) i∈I t X t ib = x t b t ∈ T, n ∈ N, b ∈ B (12b) i∈I t X t is = x t s t ∈ T, n ∈ N, s ∈ S (12c) i∈I t F t inm = f t nm t ∈ T, nm ∈ A (12d) i∈I t F t inm = f t nm t ∈ T, nm ∈ A (12e)
These constraints illustrate that the new variables are a disaggregation by price of the initial ones. The balance constraint (9c) can also be disaggregated by price by multiplying them by the corresponding variables

z t in : b∈Bn Q t b X t ib - s∈Sn Q t s X t is + m∈Θm (F t inm -F t imn ) = P t in t ∈ T, n ∈ N, i ∈ I t (13)
Multiplying constraints by binary variables as done for constraints ( 12) and ( 13) is similar to the RLT procedure proposed by Sherali and Adams (1994) to tighten the linear programming relaxation of models with binary variables. The formulation derived from BP-MPEC by adding constraints ( 10), ( 11), ( 12) and ( 13) is denoted BP-MILP. The complete formulation is presented in Appendix A.

Price elimination

The discretization of λ t n through sets I t is heavy as it introduces |T |(|B| + |S|) binary variables to the formulation in addition to the continuous variables resulting from linearization. The prices to consider at each node can be restricted to a smaller set than Λ t . We define in this section sets I t n containing the indices of prices in Λ t to consider as possible spot prices in an optimal solution.

Lemma 1 allows to bound the spot prices at each node. The highest, respectively lowest, possible spot prices in an optimal solution are those obtained when solving the market equilibrium problem with the GC bidding no capacity, respectively its full capacity, at each node and period. These bounds on the spot prices are obtained by solving two times M ED t for each time period, first fixing p t n = 0, then fixing p The resulting average number of prices per node is of 7.5. Note that in this example, there does not exist any common spot price for all nodes meaning there are at least two groups in an optimal solution.

When using sets I t n , the proportion bought for some bids in B and S in a feasible solution can be trivially fixed. For all bids b ∈ B n :

• if π t b > λt ı t n , then x t b = 1, • if π t b < λt i t n , then x t b = 0,
and conversely for bids in S.

I t 1 i t 1 5 i t 3 10 i t 2 i t 1 15 i t 4 i t 3 20 i t 2 25 i t 4 30 I t 1 I t 2 I t 3 I t 4
Figure 5: Price discretization by node for a given period

Bidding at marginal costs

The literature on price-maker bidding considers two approaches: bidding at unconstrained prices (de la [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF][START_REF] Bakirtzis | Electricity producer offering strategies in day-ahead energy market with step-wise offers[END_REF][START_REF] Ruiz | Pool strategy of a producer with endogenous formation of locational marginal prices[END_REF] or bidding at marginal production costs [START_REF] Dalby | Stratégies d'offre sur le marché électrique[END_REF][START_REF] Kardakos | Optimal bidding strategy in transmission-constrained electricity markets[END_REF]. The MPEC formulation proposed for BP can easily be adapted to bid at marginal production cost in a problem BP M . We consider that each generator makes a single bid (π j , p t jn ) at a fixed marginal production cost π j for each generator j ∈ J n at each time period. Set J n is composed of the generators at node n.

In BP, it is assumed that the GC can sell its full bidden production. The same does not hold for BP M as some generators might have a marginal cost above the spot price and can therefore not sell any production. Constraints (9g) rejecting such bids in BP-MPEC can be added for the bids of the GC, leading to the following formulation derived from BP-MPEC:

(BP M -M P EC) max n∈N j∈Jn t∈T λ t n p t jn -c(p jn ) (14a) s.t. p jn ∈ P j n n ∈ N, j ∈ J n (14b) b∈Bn Q t b x t b - s∈Sn Q t s x t s t ∈ T, n ∈ N (14c) + m∈Θn (f t nm -f t mn ) = j∈Jn p t jn (λ t n -π t b )(1 -x t b ) ≥ 0 t ∈ T, n ∈ N, b ∈ B n (14d) (-λ t n + π t s )(1 -x t s ) ≥ 0 t ∈ T, n ∈ N, s ∈ S n (14e) (-λ t n + π t b )x t b ≥ 0 t ∈ T, n ∈ N, b ∈ B n (14f) (λ t n -π t s )x t s ≥ 0 t ∈ T, n ∈ N, s ∈ S n (14g) (λ t n -π jn )p t jn ≥ 0 t ∈ T, n ∈ N, j ∈ J n (14h) λ t n -λ t m + r t nm ≥ 0 t ∈ T, nm ∈ A (14i) C max nm r t nm = λ t m f t nm -λ t n f t nm t ∈ T, nm ∈ A (14j) 0 ≤ x t b ≤ 1 t ∈ T, n ∈ N, b ∈ B n (14k) 0 ≤ x t s ≤ 1 t ∈ T, n ∈ N, s ∈ S n (14l) 0 ≤ f t nm ≤ C max nm t ∈ T, nm ∈ A (14m) r t nm ≥ 0 (14n)
where P j n is the feasible solution space for generator j in node n and constraint (14h) rejects bids from generators with a marginal cost above the spot price. The same reformulation technique used for BP-MPEC can be applied by introducing variables P t ijn = p t jn z t in . The spot prices are discretized in the same way adding marginal production costs to sets Λ t . The linearized formulation BP M -MILP is presented in Appendix B.

Heuristic methods

In this section we describe two heuristic solution methods based on the properties of the spot prices.

Iterative price-taker algorithm

A simple price-taker formulation with estimated spot prices λt n is considered as follow:

(BP -P T ) max where p t n,0 is an initial bidden quantity and p t * n is the best bidden quantity found. In the following, BP-start provides an initial solution for BP by setting p t n,0 to 0. This algorithm can be adapted to obtain a feasible solution of BP M by setting p t nj = 0 for all generators having a marginal cost above the spot price λt n before step 6.

Iterative Aggregation Disaggregation algorithm

In a solution of BP, the spot price in a group at a given time period is based on bids within this group, the imported/exported quantities of this group and the production of the GC and is independent of the structure of the network within this group. As already illustrated in Figure 3, a spot price is much simpler to compute when the transmission constraints are not blocking the selection of bids of the MO. We already presented some conditions under which two nodes cannot be in the same group in Section 4 through the spot prices in sets I t n . Based on these observations, an efficient clustering of nodes can reduce the difficulty of solving BP. Bids in different nodes of the same group can be aggregated before determining a market equilibrium for the groups considered as illustrated in Figure 6 where nodes 2 to 4 are considered in a single group. Aggregating the bids in a group of nodes can reduce significantly the size of the problem by considering fewer spot prices, removing the transmission constraints within groups and reducing the number of lines between groups to consider. In Figure 6, aggregating the nodes 2,3 and 4 results in a two nodes network with only two spot prices to establish (rather than four) and a single transmission line with a capacity equal to the sum of the capacities C max 1,2 and C max 1,3 . The drawback of performing an aggregation of nodes is the loss of information that can lead to non-optimal or infeasible solutions. A way to improve or repair the solution of an aggregated formulation is to retrieve and use some aggregated information by a disaggregation procedure. This scheme corresponds to classical aggregation and disaggregation techniques used to solve large scale problems described by [START_REF] Rogers | Aggregation and disaggregation techniques and methodology in optimization[END_REF].

Consider a set of groups over time periods G = t∈T G t . When aggregating the nodes at period t ∈ T , the transmission network is modified into a graph (G t , E t ). Edges between two groups G 1 and G 2 in the original transmission network are aggregated as a single edge G 1 G 2 with a capacity equal to the sum of the capacities of the aggregated edges. Set A t is the set of arcs corresponding to edges in the graph (G t , E t ). Consider the following aggregated formulation of BP with groups G where λ t G is the spot price in group

G ∈ G t : (BP -G) max G∈G t n∈G λ t G t∈T p t n -c(p n ) (16a) s.t. p n ∈ P n n ∈ N (16b) b∈B G Q t b x t b - s∈S G Q t s x t s t ∈ T, G ∈ G t (16c) + GG ∈A t (f t GG -f t G G ) = n∈G p t n (λ t G -π t b )(1 -x t b ) ≥ 0 t ∈ T, G ∈ G t , n ∈ G, b ∈ B n (16d) (-λ t G + π t s )(1 -x t s ) ≥ 0 t ∈ T, G ∈ G t , n ∈ G, s ∈ S n (16e) (-λ t G + π t b )x t b ≥ 0 t ∈ T, G ∈ G t , n ∈ G, b ∈ B n (16f) (λ t G -π t s )x t s ≥ 0 t ∈ T, G ∈ G t , n ∈ G, s ∈ S n (16g) λ t G1 -λ t G2 + r t G1G2 ≥ 0 t ∈ T, G 1 G 2 ∈ A t (16h) C max G1G2 r t G1G2 = λ t G2 f t G1G2 -λ t G1 f t G1G2 t ∈ T, G 1 G 2 ∈ A t (16i) 0 ≤ x t b ≤ 1 t ∈ T, n ∈ N, b ∈ B n (16j) 0 ≤ x t s ≤ 1 t ∈ T, n ∈ N, s ∈ S n (16k) 0 ≤ f t G1G2 ≤ C max G1G2 G 1 G 2 ∈ A t (16l) r t G1G2 ≥ 0 G 1 G 2 ∈ A t (16m)
This formulation corresponds to aggregating the balance constraints of BP-MPEC in constraint (16c), ignoring flow constraints within each group. This model can be reformulated into a MILP similar to BP-MPEC.

A feasible solution of BP-G is feasible for BP if and only if there exist flows within each group satisfying the demand at each node. This is done by checking for all groups G ∈ G t , t ∈ T the feasibility of the initial demand and transmission constraints :

(F LOW t G ) n∈G b∈Bn Q t b x t * b - n∈G s∈Sn Q t s x t * s + m∈Θn,m∈G (f t nm -f t mn ) + G2∈Θ G 1 (f t * G1G2 -f t * G2G1 ) = p t * n t ∈ T, n ∈ G (17a) 0 ≤ f t nm ≤ C max nm t ∈ T, nm ∈ A, n, m ∈ G (17b)
where x t * b , x t * s , f t * G1G2 , p t * n are the values in the feasible solution of BP-G. In an optimal solution of BP-G, if there exists a group G ∈ G t such that F LOW t G is not feasible, then G is partioned to restore violated transmission constraints in BP-G. The partitioning is performed by running an augmenting path algorithm and partitioning nodes in G along cuts where all lines are at their maximum capacity.

The Iterated Aggregation-Disaggregation algorithm (IAD) solves iteratively formulation BP-G until a feasible solution of BP is found, starting with G t = N for all t ∈ T and disaggregating groups G t each time F LOW t G is not feasible. Algorithm IAD iterates at most until all groups are partitioned into single nodes in which case BP-G is equivalent to BP-MPEC. The initial groups G of IAD can be improved considering observations made in Section 4. In a group G ∈ G t , feasible prices are prices that are feasible for all nodes in the group, that is

I t G = ∩ n∈G I t n .
If there exists a group G ∈ G t such that I t G = ∅, then the optimal solution of BP-G cannot be feasible for BP when discretizing prices. Such a group G is partitioned by removing a node n such that I t G\n = ∅. If no such node exists, nodes are removed from G at random until there exists a feasible price for the remaining nodes of G. In the example of Figure 5, there exists no feasible price for a group containing all four nodes. The resulting partitioning can be {1, 2, 3} and {4} or {1} and {2, 3, 4}.

In order to retrieve a feasible repaired solution of BP at each iteration of IAD where the solution is not feasible for BP, the productions p n found at the current iteration are used as initial production in BP-start to obtain a feasible solution of BP. The flowchart of algorithm IAD is presented in Figure 7.

Step Cut groups (1) corresponds to the partitioning of groups if there exists a group G such that I t G = ∅, step Cut groups (2) corresponds to the partitioning of a group in an optimal solution of BP-G where the flow is not feasible.

When solving IAD, if there exists a time period t ∈ T such that G t = {N }, then flow constraints disappear from BP-G in this period. The production of the GC at period t is then only constrained by ( 16c)-( 16g) regarding the market equilibrium constraints. This leads to a single node formulation as presented by de la [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF] where the spot price λ t {N } can then be expressed as a piece-wise linear function depending on the total production of the GC at period t, as already illustrated in Figure 4. Let r t i be the residual demand at price i ∈ I t {N } , that is, the production the GC can sell with priority over competitors at price λt i : [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF] showed on a single node that if the production of the GC lies in an interval ]r t i+1 ; r t i ] then the spot price λ t n is equal to λt i+1 . After price discretization, constraints (16c)-(16i) of BP-G for periods t ∈ T such that G t = {N } can be replaced by the following constraints:

r t i = b∈B:π t b ≥ λt i Q t b - s∈S:π t s < λt i Q t s de la
i∈I t z t i{N } = 1 (18a) i∈I t P t i{N } = n∈N p t n (18b) P t i{N } ≤ r t i z t i{N } i ∈ I t {N } (18c) P t i{N } ≥ r t i+1 z t i{N } i ∈ I t {N } (18d) 0 ≤ P t i{N } ≤ Q t n z t i{N } i ∈ I t {N } (18e) P t i{N } ≥ n∈N p t n - n∈N Q t n (1 -z t i{N } ) i ∈ I t {N } (18f) z t i{N } ∈ {0, 1} i ∈ I t {N } (18g)
Formulation BP-{N } where all nodes are aggregated during all time periods is presented in Appendix C.

Set G t = {N }, t ∈ T Update I based on G |I t G | > 0 t, G ∈ T × G t ? Solve BP -G Solve F LOW t

SOS-narrowing

For each time period and node, a special ordered set composed of binary variables {z t in } i∈I t n is used to represent the possible spot prices. Fractional values of these variables obtained during the branching process may give some indication on prices that are unlikely to be optimal spot prices. Consider the following values at a node of the branching tree for variables {z t in } i∈I t n with I t n = {1, . . . , 10} : i 1 2 3 4 5 6 7 8 9 10 z t i 0 0.02 0.06 0.61 0.20 0.08 0.03 0 0 0 These values can roughly be seen as a discrete probability distribution. Prices up to price π t 3 and after π t 6 can be considered as unlikely to be an optimal bidding price. These prices can be eliminated in the remaining subtree of the branch and bound tree in order to narrow the value of the potential prices considered. Consider an elimination coefficient α ∈ [0, 0.5] and the following indices:

i t m = min{i ∈ I t : i ∈I t ,i ≤i z t i ≥ α} ; i t M = max{i ∈ I t : i ∈I t ,i ≥i z t i ≥ α} As i ∈I t z t i = 1, z t im ≤ z t i M
, at each node of the branching tree, the prices with indices out of {i t m , . . . , i t M } are eliminated by setting the corresponding variables to 0 through local cuts. These cuts reduce the number of binary variables and thus the size of the solution space during the branching procedure but may also eliminate optimal solutions from the model.

In order to avoid eliminating optimal solution too early in the branching tree and to limit the size of the branch and bound tree, the value of α is increased from an initial value up to 0.5 following a sigmoid curve as the number of nodes explored increases. This increases the number of prices eliminated in the subtrees as the number of nodes explored increases. Consider α 1 as an initial value for α, n as the maximum number of nodes that can be explored and α k as the elimination coefficient used at node k. Then,

α k = 1 1 + e -Θk n +Θ ; Θ = ln 1 -α 1 α 1
We have α k ≤ 0.5 for all k ∈ [1, n] and α n+1 > 0.5. Figure 8 illustrates the value of α k throughout the iterations of the heuristic.

In the following the SOS narrowing heuristic with values α and n is referred to as SOS-n(α, n).

Numerical results

We present in this section computational results to assess the quality of models and solution methods proposed in this paper. We first provide a description of the characteristics of the instances. Some preliminary computational experiments are then performed on small instances with exact methods. Finally larger instances are only solved through the heuristic methods to illustrate their scalability. An analysis of the impact of PCR on the profit of the GC is performed. The impact of restricting bidding prices to marginal production costs and the resulting impact on the spot prices is also analysed. All the results reported are averages over five instances.

Tests are performed on a 8-core i7-4790K 4.00 GHz with 32 Gb of RAM memory and the computation time is limited to 1800 seconds. All reported times include instances that are not solved to optimality in 1800 seconds. All methods are implemented using Julia 1.0 with packages JuMP 0.18.5 and CPLEX 0.4.1 interfaced with ILOG CPLEX 12.7. The default parameters of CPLEX are used. The SOS parameter of CPLEX available for special ordered sets is deactivated as no improvement in the solving time has been observed during the tests performed with this feature.

Data

The instances used are built from several sources 234 and consider 24 time periods. Each bid of a competitor represents a generator similar to those of the GC in terms of capacity. The bidding prices considered reflect bids observed on the EPEX market. Figure 9 The generators considered in the UC are thermal units in a bus to bus system. This model integrates linearized quadratic production costs, start-up and shut-down costs related to the online/offline time, ramping up and down constraints and minimum online and offline time. The UC formulation contains three binary variables per generator and time period. The data for generators is provided by [START_REF] Carrión | A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem[END_REF] and have been used in multiple studies. Ten generators types are given. The instances considered replicate these generators to obtained the desired number of generators. In case (|J| -5) mod 5 = 0, the five generators at odd indices are added.

The transmission network is composed of 4 nodes representing The Netherlands, Belgium, France and Germany. Daily average spot prices on the EPEX and BELPEX are similar for Belgium, France and Germany. The total bidden quantity of competitors are randomly partitioned in each country in following proportions: The transmission network depicted in Figure 10 shows transmission lines between each pair of bordering countries. It has been observed in EPEX that hourly spot prices are often equal between France and Germany. The values for capacities of the transmission lines have been chosen in order that two or three local spot prices are defined over the four markets at each time period in a market equilibrium to be compatible with the EPEX data. Sets S and J are the set of competitor bids and the set of generators of the GC. Column Count. are the countries where the GC is bidding and Iter. is the number of iterations of BP-start. Feasible solutions with a small gap to optimality can be found with BP-start in a short time. Adding a starting solution to BP-MILP improves significantly the solving time and the end gap for unsolved instances.

Exact formulations for BP

Figure 11 shows the evolution with respect to time of the relative gap to the best solution found for all methods for an unsolved instance. Bounds are in the upper half of the figure.

The upper bound on BP falls down to a value close to optimality in a short time before stagnating. Finding integer solution seems to be difficult. Without using a starting solution, the first integer solution with a gap under 20% is found after 931 seconds, the final gap being 12.81% with only three other integer solutions found. With a starting solution, a total of six feasible solutions are found, the best one having a relative gap of 1.09%.

Curve Bound -UC relax. is obtained by solving BP-MILP and relaxing the integrality constraint of the UC variables, which provides an upper bound for BP in the smallest time. This partial relaxation of the integer variables of BP-MILP is denoted BP-MILP R in the following. The relative gap of SOS-n(0.01,2000) is also illustrated, the heuristic method finds the best feasible solution in a very short time.

In all the following results we initialize all solution methods with a starting solution obtained with BP-start . Instance BP-MILP -without ( 12) and ( 13 Table 2: Strengthening BP-MILP Some insight on the impact of constraints ( 12) and ( 13) used to strengthen BP-MILP after linearizing the extended formulation of BP-MPEC is reported in Table 2. All gaps reported are relative to the best solution found with the full BP-MILP formulation. From the LP gaps we can observe that the strengthening constraints are significantly tightening the solution space. Without these constraints, no feasible solution of decent quality can be found.

Numerical results of formulation BP-MILP for larger instances are reported in Table 3. When the GC is bidding in two countries, the number of generators is equally split in both countries. All gaps are relative to the best solution found with BP-MILP. Column Nodes is the number of nodes explored in the branch and bound tree. Only very few instances are solved to optimality and some do not start the branching procedure. The gap reported for BP-MILP R is the relative gap between the best bound and the best solution found with BP-MILP. Formulation BP-MILP R provides on average a better upper bound on BP than BP-MILP, generally in a shorter time. During the branching procedure, the gaps tend to get low quite quickly but decrease very slowly afterwards as illustrated in Figure 11. We can observe that the size of the UC formulation strongly influences the difficulty of the instances. The penetration of the GC on the market defined by |J| |S| is also correlated to the difficulty of solving an instance. The higher the penetration, the more the GC influences the spot prices resulting in more potential spot prices to consider in sets I t n and more binary variables in formulation BP-MILP.

Figure 12 illustrates the local spot prices over time on an instance where the GC is bidding in two nodes. This spot prices represented with a full line result from the best solution found with BP-MILP. The dotted line represents the spot prices obtained without the bids of the GC, in which case the spot prices are equal in all nodes in 10 time periods over 24 and spot prices are always identical between France and Germany. With the bids of the GC, 8 time periods admit a global spot price and France and Germany have the same spot price in 17 periods. Recalling the exporting/importing situation of a node can be deduced from local spot prices, one can observe it fluctuates over time, mainly between The Netherlands and Belgium on one side and France and Germany on the other side.

Figure 13 gives the number of price indices in sets I t n to illustrate the impact of the price elimination technique presented in Section 4. Without any price elimination, there would be 400 binary variables for bid prices at each time period. The largest number of prices after eliminations is 26 and lies in Belgium as the generators of the GC have the highest local penetration in this country. The number of prices in France is also generally more important than in Germany as the GC also bids in France. In several time period, the number of local prices to consider is equal to one, fixing the local spot prices on these periods.

Heuristic methods

Table 4 presents numerical results for IAD. Gaps are relative to the best bound found with BP-MILP or BP-MILP R . Column C. gap reports the proportion of the gap closed by the best solution z * found by IAD in comparison to the best solution z found by MILP, relative to the best upper bound found z:

C. gap = 1 - z -z * z -z M ILP
Column Iter. is the number of iterations of IAD before finding a feasible solution or reaching the time limit and column Nb. gr. is the average number of groups per time period in the solution returned by IAD. Except for a couple of instances, IAD improves significantly the value of the best solution found as well as the solving time. The number of iterations is quite reduced before finding a feasible solution by solving BP-G, the groups being rapidly partitioned. The average gaps and times per iteration over the 60 instances of Table 4 are reported in Figure 14. The numbers shown in brackets next to the iteration indices are the number of instances that did not terminate before the given iteration. The repaired solutions computed improve over the iterations, illustrating the importance of initial starting productions in BP-start. Figure 15 presents the average number of groups per time period per iteration. The number of groups considered in the first iteration is often different from 1 as the network can be partitioned from the beginning to have at least one price in each set I t G . The most important partitioning is then made at the end of the first iteration. At the end of further iterations, only one or two groups are generally partitioned.

Numerical results for the SOS-n(0.01,2000) heuristic are given in Table 5. This heuristic is tested on BP-MILP and on IAD. Gaps are relative to the best bound found with BP-MILP or BP-MILP R . The closed gaps are the proportion of the gap closed by the best solution found with SOS-n compared to the best solution found with the corresponding solving method without SOS-n, relative to the best upper bound found. The initial value for α = 0.01 and the limitation to 2000 nodes are the parameters reporting the best results. Increasing the number of nodes improves slightly the solution and increases slightly the solving time and conversely for the value of α.

When used on BP-MILP, SOS-n improves significantly the solving time as well as the best solution found. The largest instances that do not exit the root node of the branch and bound tree in BP-MILP have over a On IAD, SOS-n improves the solving time but the solution is sometimes of lower quality than without SOS-n.

Still, IAD -SOS-n finds on average better solutions than BP-MILP -SOS-n. Figure 16 summarizes the performance of the different solving methods presented per instances. Gaps are relative to the best bound found with BP-MILP or BP-MILP R . Negative gaps are associated with feasible solutions. Overall, formulation BP-MILP R provides the best upper bound and the best feasible solution is found by IAD -SOS-n. As already observed, the difficulty of the instances is strongly correlated with the penetration of the GC and the size of the UC formulation. For a given number of generators and nodes, the gap tends to decrease when the number of bids increases.

Market impact

This section provides some insight on the impact on the profit of the GC when considering a transmission network or restraining bidding prices to marginal prices of generators.

Table 6 compares the formulation proposed by de la [START_REF] De La Torre | Price maker self-scheduling in a pool-based electricity market: A mixed-integer lp approach[END_REF] for BP considering a single day-ahead market with the equivalent formulation BP-{N }.

The columns under de la Torre et al. provide the LP gaps and the solving times to optimality. The columns under BP-{N } also reports LP gaps and the total solving time that are both slightly improved. The constraints of the transmission network being removed, BP-{N } is a relaxation of BP-MILP. Column Gap to BP reports the gap of the optimal value of BP-{N } relative to the best upper bound found for BP. These gaps are reported as negative as the optimal value of BP is overestimated when ignoring the transmission constraints. C. gap 1 reports the first corrected gap, that is the profit for the GC considering it sells its full quantity at the spot prices obtained considering the transmission network, relative to the best upper bound found. Considering this optimistic correction where the GC sells everything without worrying about bidding prices, the solution provided by BP-{N } is of significantly lower quality than the best solution obtained with the former methods, the best gap obtained considering the network being reported in column B. gap. A more realistic correction is to consider the GC places bids according to the spot prices and quantities computed in BP-{N }. The risk in this case is to place a bid over the accurate local spot price and not sell any production at some time periods as can be the case in price-taker formulations. The gap of the realistic correction, considering bids over the spot price are not sold, relative to the best upper bound found is reported in column C. gap2. The gaps obtained are very large, illustrating the importance of integrating an accurate computation mechanism of the spot prices to avoid bidding at a too high price and not selling.

Figure 17 illustrates the spot prices and quantities sold by the GC with no network before and after the realistic correction and compares it to the best solution found for BP. The curves reported for the spot prices correspond to the local spot price of the node where the GC is bidding. On the left figure, we can observe that the spot prices found without considering the transmission constraints can be pretty far from the corrected local spot prices. Furthermore, in the four periods where the spot price is over-estimated, the corresponding quantity sold is equal to zero if the GC bids at the computed spot price.

We now consider the effect of constraining bidding prices to the marginal cost of the associated generator as in BP M . Numerical results for formulation BP M are reported in Table 7. The gap to BP is the relative gap between the value of the best solution found by BP M and the best solution found by BP-MILP. As bidding prices are fixed in BP M , its optimal value is at most the optimal value of BP. The end gaps are slightly bigger than when solving BP-MILP, this is explained by the additional difficulty in BP M to track if generators can sell their production depending on their marginal cost and the spot prices. The gaps to BP is on average of 5% and the end gaps of the formulation are slightly bigger than for BP-MILP. Figure 18 illustrates the local spot prices of each bidding market as well as the sold quantity per time period. In the results of this instance, the same generators are turned on until period 13 in BP and in BP M . The bidden production of the GC is limited by the spot prices in periods 2 and 14 when bidding at marginal costs. The production of the GC is smaller is these periods in BP M than in BP to limit the production at loss. When the spot prices are not limiting the bidden production, one can expect that the optimal bidden quantities are identical in BP and BP M as start-up and shut-down costs are identical until period 13 included. because of ramping up constraints, the total production in BP M catches up the total production of BP only in period 9 and 10 before decreasing again to avoid a too important production at loss in period 14. At period 14 in BP M , the GC can either decide to reduce the production of the generators over the spot price and keep it turned on, producing at loss but avoiding future start-up cost, or shut-down the generators to avoid producing at loss but adding eventual start-up costs in the future. In this instance, the involved generator is turned off at period 14 in BP M and is not turned back on during the remaining times periods, start-up cost being too important. In order to compensate a lower production during the last periods in BP M , the generators that are turned on in period 14 in BP M produce more than in BP at a higher unit cost. The restriction of limiting bidding prices to marginal production costs can significantly modify the UC production plan. Finally, we illustrate how the profit of the GC is split into income and production for solutions of BP and BP M in Figure 19. The instance used is the same as for Figure 18. The dotted line represents the income, the dashed line the production cost and the full line the profit of the GC. In period 4, the income decreases significantly regarding the income in BP M while the production cost decreases only slightly. This is a consequence of the GC not bidding any production with some generators with a marginal cost under the spot price but still producing power with them to reach a desired quantity in future time periods. In period 15, the production cost of BP M surpasses the one in BP, consequence of the GC deciding to shut down a generator in period 14 and producing more with the other generator in future periods. One can also observe that in both formulations, the GC has a negative profit in certain time periods. This is explained by the ramping up constraints that limit the increase and decrease of the total production. In order to be able to sell a lot of production during periods with a high spot price, the GC must start the production several periods in advance even if this results in a production at loss for certain periods.

Conclusion

This paper presents a Mathematical Program with Equilibrium Constraints formulation and a tight Mixed Integer Linear reformulation of the bidding problem. Our model consider a Unit Commitment problem much more detailed than the current literature on such bidding problems. Instances with a limited number of generators and a larger number of bids are solved to less than 1% from optimality.

Computational experiments highlight the complexity introduced by regulations such as Priced Coupled Regions. Nevertheless, the problem could be addressed by exploiting properties of local spot prices in an Iterative Aggregation-Disaggregation heuristic, aggregating the bidding areas with a potentially equal spot price throughout the time periods to reduce significantly the number of binary variables. The gap to optimality is significantly reduced in comparison of the best solutions found with the Mixed Integer Linear formulation. This heuristic is particularly interesting if many areas are likely to have equal spot prices, and can be adapted to other bidding problems with a transmission constrained network.

The SOS-n heuristic, reducing the number of binary variables to consider in Special Ordered Sets during a branch and bound procedure, is particularly efficient in improving the gap to optimality in a limited computational time. This generic heuristic can be adapted to any formulation containing a special ordered set of type 1 represented by binary variables.

Numerical results have also shown the importance of considering a price-maker formulation with a realistic spot price computation. A bad evaluation of the spot price might result in bids with a high price that are not sold after determining the market equilibrium, leading to important losses.

As a vast majority of the literature on price-maker approaches, we make strong assumptions to keep the models tractable. The market mechanism used is limited to a single type of bid, the context is deterministic and only capacity constraints are consider for the transmission network. [START_REF] Clements | Strategic bidding and rebidding in electricity markets[END_REF] have illustrated that physical constraints of a transmission network can have a significant impact on the spot price. Some papers consider a more complete setup for the transmission constraints with a simplified UC formulation as a counterpart. The combination of the market equilibrium constraints proposed in this paper could potentially be combined with an more detailed transmission model to be closer to reality. Uncertainty should also be considered in the bids of competitors. For this purpose, Γ-robust optimization [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] could be a possible approach. Finally, the bidding mechanism proposed in most price-maker bidding problems are a very simplified version of the one used in Europe, where the market equilibrium problem is solved with the EUPHEMIA algorithm (EUPHEMIA, 2016). [START_REF] Koltsaklis | Incorporating unit commitment aspects to the european electricity markets t algorithm: An optimization model for the joint clearing of energy and reserve markets[END_REF] have illustrated the limitation of this algorithm as it does not consider all physical constraints of power generation. The bidding mechanism being central for accurate price-maker formulations, a more accurate market mechanism should be considered to fit with real life constraints. Formulation is given for a single node. Data:

• J: set of production units (generators)

• P j , P j : lower and upper bound on production level of unit j over one time period

• A j : fixed cost for a generator is turned on

• N L j : number of segments for production cost of unit j

• F lj : unit cost on segment l of unit j

• T lj : upper bound on accumulated production up to segment l of unit j

• U T j , DT j : minimum up and down times for unit j

• K j , C j : Ramping up/down costs • RU j , RD j : ramping up/down rates • SU j , SD j : start/stop rates • p 0 j : initial production of unit j • L j : number of periods unit j must be initially offline due to its minimum down time constraint p j (t) -p j (t -1) ≤ RU j v j (t -1) + SU j y j (t) j ∈ J, t = 2, . . . , |T | p j (1) -p 0 j ≤ RU j v j (0) + SU j y j (1) j ∈ J p j (t -1) -p j (t) ≤ RD j v j (t) + SD j z j (t) j ∈ J, t = 2, . . . , |T | p 0 j -p j (1) ≤ RD j v j (1) + SD j z j (1) j ∈ J Minimum up / down times: v j (t) = 0 j ∈ J c p j (t), c u j (t), c d j (t), Θ l (j, t) ≥ 0 j ∈ J, t ∈ T v j (t), y j (t), z j (t) ∈ {0, 1} j ∈ J, t ∈ T

Figure 1 :

 1 Figure 1: Bidding procedure

Figure 3 :

 3 Figure 3: Market equilibrium examples

Figure 8 :

 8 Figure 7: IAD flowchart

Figure 9 :

 9 Figure 9: Average demand (GWh) and spot-price (e/MWh) of instances with 200 bids

  Figure 10: Transmission network

Figure 11 :

 11 Figure 11: Gap evolution of BP-MILP for an instance with |S| = 200, |J| = 10

Figure 12 :

 12 Figure 12: Spot prices at each time period and node for |S| = 400, |J| = 20, country = BE-FR

Figure 13 :

 13 Figure 13: Number of indices in sets I t n for |S| = 400, |J| = 20, country = BE-FR

Figure 16 :

 16 Figure 16: Solving methods gap comparaison

Figure 18 :Figure 19 :

 1819 Figure 18: Marginal bidding results for |S| = 300, |J| = 20, country = BE

  At each node n and time period t, let i t n , respectively ı t n , be the index in Λ t of the minimum, respectively maximum, possible spot price. The indices of the spot prices to consider in sets I t n can be restricted to {i t n , . . . , ı t n }. Indices in sets I t n can also be restricted based on potential groups in a market equilibrium. Spot prices can be equal or different between nodes depending whether they are in the same group or not. Consider an index i ∈ {i tFigure5provides an illustration of the potential spot prices by nodes for a time period considering 30 bidding prices in a network of 4 nodes. All bids are represented by a color associated to a node on the first line. The indices i t n and ı t n are indicated for each node. The price indices considered in I t n are local price indices in {i t n , . . . , ı t n } in addition to the prices indices bidden in another nodes m that are in {i t n , . . . , ı t n }∩{i t m , . . . , ı t m }.

	I t n =	( Ĩt m ∩ {i t n , . . . , ı t n })
	m∈N

t n = Q t n . n , . . . , ı t n } such that λt i ∈ Λ t corresponds to a price bidden in a node m = n. Then the spot price at node n can be equal to λt i if and only if it is equal to λt i at node m and n and m are in the same group. This allows to eliminate from I t n indices i ∈ [i t n , ı t n ] such that λt i is bidden at a node m = n and i ∈ [i t m , ı t m ]. Let Ĩt n be the set of all indices of prices in Λ t bidden at node n at period t included in {i t n , . . . , ı t n }. Then I t n is defined as follow:

  In the leader subproblem, variables of the follower are fixed and variables of the leader are optimized and conversely for the follower subproblem. For BP, the leader subproblem is BP-PT fixing spot prices {λ t n } t∈T,n∈N as in a price-taker formulation and the follower subproblem is M ED t fixing bidden quantities {p t n } t∈T,n∈N and computing spot prices. A feasible solution of BP is found with algorithm BPstart as follow:

	1
	2	3
	4
	Figure 6: Partial aggregation of nodes
	s.t. p n ∈ P n	(15b)
	A feasible solution of a bilevel problem can be computed by iteratively solving a leader and a follower
	subproblem. 1. Set p t * n = p t n = p t n,0 , t ∈ T, n ∈ N ,
	2. Initialize λt
	λt n p t n -c(p n )	(15a)
	n∈N t∈T

n by solving M ED t for each time period, 3. z * = n∈N t∈T λt n p t n0 -c(p n0 ), 4. Update p t n by solving BP-PT, 5. Update λt n by solving M ED t for each time period, 6. Set z = n∈N t∈T λt n p t n -c(p n ) 7. If z > z * , set z * = z, p t * n = p t n , go to step 4 8. Return z * and p t * n

Table 1 :

 1 Table1presents numerical results obtained with algorithm BP-start on small instances as well as the impact of adding the obtained starting solution to BP-MILP. Gaps are relative to the best bound found with BP-MILP with a starting solution. Start solution impact on BP-MILP

		Instance			Start heuristic		No start	BP-MILP	With start
	|S| |J| Count. Time (s) Gap (%) Iter. Time (s) Gap (%) Time (s) Gap (%)
	100	5	BE	0.63	0.85	1.45	191.11	0		118.55	0
	100 10	BE	0.97	3.35	2.11	1097.45	1.19	864.91	0
	200	5	BE	0.85	0.97	1.58	298.11	0		99.16	0
	200 10	BE	1.23	3.02	2.23	1800	10.85	1653.31	0.74

Table 3 :

 3 Numerical results for BP-MILP

		35
	Spot price (e/MW)	20 25 30			NL
		15			BE
					FR
					DE
		0	6	12	18	24
				Time period

Table 4

 4

	: Numerical results for IAD

Table 5 :

 5 Numerical results forSOS-n(0.01,2000)

Table 6 :

 6 Comparaison with single node model thousand nodes with SOS-n, illustrating some binary variables are eliminated starting from the root node.

Table 7 :

 7 Bidding at marginal costs

		30
	Spot price (e/MWh)	25
						BP
		15				BP M
		0	6	12	18	24
				Time

  H. D. Sherali and W. P. Adams. A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Applied Mathematics, 52:83-106, 1994. H. D. Sherali and W. P. Adams. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer, 1999. G. Steeger, L. A. Barroso, and S. Rebennack. Optimal bidding strategies for hydro-electric producers: A literature survey. IEEE Transactions on Power Systems, 29:1758-1766, 2014. M. Tahanan, W. van Ackooij, A. Frangioni, and F. Lacalandra. Large-scale unit commitment under uncertainty: a literature survey. 4OR, 13(2):115-171, 2015. doi: 10.1007/s10288-014-0279-y. J n , i ∈ I t n . BP M -MILP is obtained from BP-MILP, replacing constraints (19a) by p nj ∈ P j n n ∈ N, j ∈ J n , and by adding the following constraints: T, n ∈ N, j ∈ J n , i ∈ I t n P t ijn ≥ p t jn -Q t (1 -z t in )t ∈ T, n ∈ N, j ∈ J n , i ∈ I t

			X t is = x t s	t ∈ T, n ∈ N, s ∈ S
			i∈I t n
			F	t inm = f t nm	n	t ∈ T, nm ∈ A
			i∈I t n
	n i∈I t C BP-{N } formulation F t inm = f t nm	t ∈ T, nm ∈ A
	0 ≤ P t in ≤ Q t n z t in P t in ≤ p t n λt i P t i -c(p) P t in ≥ p t n -Q t n (1 -z t in ) t∈T i∈I t s.t. p ∈ P max	t ∈ T, n ∈ N, i ∈ I t n t ∈ T, n ∈ N, i ∈ I t n t ∈ T, n ∈ N, i ∈ I t n
	A BP-MILP formulation 0 ≤ X t ib ≤ z t in X t ib ≥ x t b + z t in -1 i∈I t z t i = 1 t ∈ T	t ∈ T, n ∈ N, b ∈ B n , i ∈ I t n n t ∈ T, n ∈ N, b ∈ B n , i ∈ I t
	max		  is ≥ x t X t s + z t in -1 λt in i∈I t i P t 0 ≤ X t is ≤ z t in P t i = p t	 -c(p n )  t ∈ T	t ∈ T, n ∈ N, s ∈ S n i ∈ I t n t ∈ T, n ∈ N, s ∈ S n , i ∈ I t n
	n∈N s.t. p n ∈ P n t∈T i∈I t n b∈Bn Q t b X t ib -0 ≤ F t inm ≤ C max s∈Sn nm z t Q t s X t is in P t i ≤ r t i z t t ∈ T, i ∈ I t i F t inm ≥ f t nm -C max nm (1 -z t in ) P t i ≥ r t i+1 z t i t ∈ T, i ∈ I t 0 ≤ F t inm ≤ C max nm z t 0 ≤ P t i ≤ Q t z t	n ∈ N t ∈ T, nm ∈ A, i ∈ I t n t ∈ T, nm ∈ A, i ∈ I t n	(19a)
			+	(F
			m∈Θm
				λt i X t ib + π t b x t b ≥ 0	t ∈ T, n ∈ N, b ∈ B n
			i∈I t n
			λt i X t is -π t s x t s ≥ 0	t ∈ T, n ∈ N, s ∈ S n
			i∈I t n
			λt i z t in -	λt i z t im + r t nm -r t mn = 0	t ∈ T, nm ∈ A
			i∈I t n		i∈I t m
			x t b = 0	t ∈ T, n ∈ N, b ∈ B n : π t b < λt i t n
			x t b = 1	t ∈ T, n ∈ N, b ∈ B n : π t b > λt ı t n
			x t s = 0	t ∈ T, n ∈ N, b ∈ S n : π t s > λt ı t n
	p t n =	x t s = 1 p t jn	t ∈ T, n ∈ N, b ∈ S n : π t s < λt i t n t ∈ T, n ∈ N
	C max nm r t nm = j∈Jn in = P t P t ijn	i∈I t n	λt i F t inm -t ∈ T, n ∈ N, i ∈ I t i∈I t n λt i F t inm n	t ∈ T, nm ∈ A
		i∈I t n j∈Jn λt i P t ijn -π t z t in = 1 jn p t jn ≥ 0	t ∈ T, n ∈ N, j ∈ J n	t ∈ T, n ∈ N
	i∈I t n	i∈I t n P t ijn = p t P t in = p t n jn	t ∈ T, n ∈ N, j ∈ J n	t ∈ T, n ∈ N
	i∈I t n ijn ≤ Q X t ib = x t 0 ≤ P t i∈I t n

t inm -F t imn ) = P t in t ∈ T, n ∈ N, i ∈ I t i∈I t n λt i (z t in -X t ib ) -π t b (1 -x t b ) ≥ 0 t ∈ T, n ∈ N, b ∈ B n -i∈I t n λt i (z t in -X T is ) + π t s (1 -x t s ) ≥ 0 t ∈ T, n ∈ N, s ∈ S n b t ∈ T, n ∈ N, b ∈ B im t ∈ T, nm ∈ A, i ∈ I t n F t inm ≥ f t nm -C max nm (1 -z t im ) t ∈ T, nm ∈ A, i ∈ I t n 0 ≤ x t b ≤ 1 t ∈ T, n ∈ N, b ∈ B n 0 ≤ x t s ≤ 1 t ∈ T, n ∈ N, s ∈ S n 0 ≤ f t nm ≤ C max nm t ∈ T, nm ∈ A 0 ≤ r t nm t ∈ T, nm ∈ A z t in ∈ {0, 1} t ∈ T, n ∈ N, i ∈ I t n B BP M -MILP formulation Q t jn : maximum production capacity of generator j at node n in period t, P t ijn : t ∈ T, n ∈ N, j ∈ t jn z t in t ∈ T, n ∈ N, j ∈ J n , i ∈ I t n P t ijn ≤ p t jn t ∈ i t ∈ T, i ∈ I t P t i ≤ p t t ∈ T, i ∈ I t P t i ≥ p t -Q t (1 -z t i ) t ∈ T, i ∈ I t z t i ∈ {0, 1} t ∈ T, i ∈ I t

D UC formulation from

[START_REF] Ostrowski | Tight mixed integer linear programming formulations for the unit commitment problem[END_REF]

  Tj +1 y j (t ) ≤ v j (t) j ∈ J, t ∈ G j + 1, . . . , |T | j (t ) ≤ 1 j ∈ J, t ∈ L j + 1, . . . , |T |

	t
	v j (t) +
	t =t-DTj +1
	Gj
	v j (t) = G j	j ∈ J
	t=1
	Lj
	t=1

t t =t-U z

https://www.epexspot.com/fr/

https://www.entsoe.eu/data/

https://www.belpex.be

Acknowledgments

This research benefited from the support of the FMJH Program PGMO and from the support of EDF, Thales, Orange.

• G j : number of periods unit j must be initially online due to its minimum up time constraint Variables:

• p t ≥ 0: energy bidding in period t in the node.

• p j (t) ≥ 0: energy produced in period t by unit j • c(p): total production cost for {p j (t)} {j∈J,t∈T }

• Θ l (j, t) ≥ 0: energy produced by j in period t on segment l

: production cost of unit j at period t • c u j (t): ramping up cost of unit j at period t • c d j (t): ramping down cost of unit j at period t Link with market equilibrium variables:

Production capacities:

P j v j (t) ≤ p j (t) ≤ p j (t) j ∈ J, t ∈ T 0 ≤ p j (t) ≤ P j v j (t) j ∈ J, t ∈ T Ramping up and down :