3
$\begingroup$

Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= I_{t-1}+x_t-D_t$ where $x_t$ is the quantity that is refilled. Now, the quantity that we can send to customers is determined based on the inventory level and demand, $z_t \le I_{t-1}+x_{t}$ or $z_t \le D_t(p_t)$. Now, consider a part of objective function $\sum_{t\in T}p_t.z_t$.

Gurobi can solve it regardless if it is convex or concave. Now, suppose we discretize the price with $L$ levels and price is re-written as $p_t=\sum_{l \in L}p_ly_{lt}$ where $\sum_{l \in L}y_{lt}=1 \quad \forall t \in T$.

Regardsless the gap between these two formulation, I am wondering which formulation is well-suited for solvers like Gurobi, because in the second formulation, the number of decision variables increases and there will be some binary variables. This will be more severe if it depends on scenarios, i.e., $p_{ts}$.

One more question, if I use the second formulation, should I linearized the objective function or Gurobi can do it by it-self? That is: $$ \max \sum_{t \in T}\sum_{l \in L}p_l W_{lt} \\ W_{lt} \le M.y_{lt} \\ W_{lt} \le z_t \\ \sum_{l \in L}y_{lt}=1 $$

$\endgroup$
4
  • $\begingroup$ This is similar to a common problem in integrated energy (storage) scheduling and bidding literature, where quantitiy-price tuples must be determined simultaneously, see Mazzi, Kazempour, Pinson (2018). The focus is on the scenario-based stochastic formulation. $\endgroup$
    – ktnr
    Commented Apr 1, 2021 at 8:39
  • $\begingroup$ It seems that $p_t$ and $z_t$ are both continuous variables? Gurobi cannot handle the product of continuous variables by default. $\endgroup$
    – ktnr
    Commented Apr 1, 2021 at 8:46
  • $\begingroup$ Thank you so much. In version 9, Gurobi can solve non-convex quadratic programming and it provides the optimal solution. $\endgroup$
    – Amin
    Commented Apr 1, 2021 at 18:33
  • $\begingroup$ Bookmarked this question! I wrote a book on quadratization with and without adding auxiliary variables, and there's some related questions here: or.stackexchange.com/q/799/727, or.stackexchange.com/q/1380/727, or.stackexchange.com/a/2621/727. $\endgroup$ Commented Apr 1, 2021 at 20:44

1 Answer 1

6
$\begingroup$

You can ask Gurobi to do this for you https://www.gurobi.com/documentation/9.1/refman/preqlinearize.html

Whether a linearization leads to better or worse performance is almost impossible to know beforehand. You will simply have to test.

Cplex for instance uses an ML-trained classifier to make this decision, indicating that it is hard to come up with any simple rule manually http://www.optimization-online.org/DB_HTML/2020/03/7662.html

$\endgroup$
1
  • $\begingroup$ Thank you so much $\endgroup$
    – Amin
    Commented Apr 4, 2021 at 7:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.