8
$\begingroup$

Though my title is quite general (please feel free to edit), indeed, I wonder if the following models can be solved in Gurobi or CPLEX. Model 2 is just an alternative one to Model 1. Although we discussed about an MIP reformulation applicability in here for a similar version of the problem, I would like to directly solve the problem as is. If Gurobi or CPLEX cannot handle it, can you please suggest some other solvers that can handle 10,000 variables as $|P|\approx10000$. Note that all notations other than $h_p$ (which are continuous in $\mathbb{R}^+$) represent some non-negative constant.

Model 1:

\begin{alignat}2\max &\quad \sum_{\substack{p\in P,\\s\in S_p}}e_{ps}\left(H^+-h_p\right)\tag1\\\text{s.t.}&\quad \sum_{p\in P}\left(\frac{k_p\tau_p}{h_p}-\sum_{s\in S_p}e_{ps}\right)\leq \kappa\tag2\\&\quad\sum_{\{p\in P|d_p=t,\theta_p=j\}}\frac{\tau_p}{h_p} \leq M_{tj} \qquad \forall t\in T, j\in J\tag3\\&\quad f_{ps}h_p \leq B_p \qquad \forall p\in P, s\in S_p\tag4\\&\quad h_p\in \mathbb{R}^+, H^- \leq h_p \leq H^+.\end{alignat}

Model 2:

\begin{alignat}2\max &\quad \sum_{\substack{p\in P,\\s\in S_p}}\frac{e_{ps}}{2}\left(30-\frac{30}{h_p}\right)\tag1\\\text{s.t.}&\quad \sum_{p\in P}\left(\frac{k_p\tau_ph_p}{60}-\sum_{s\in S_p}e_{ps}\right)\leq \kappa\tag2\\&\quad\sum_{\{p\in P|d_p=t,\theta_p=j\}}\frac{\tau_ph_p}{30} \leq M_{tj} \qquad \forall t\in T, j\in J\tag3\\&\quad h_p\geq \frac{e_{ps}}{B_p} \qquad \forall p\in P, s\in S_p\tag4\\&\quad h_p\in \mathbb{R}^+, H^- \leq h_p \leq H^+.\end{alignat}

$\endgroup$
0

1 Answer 1

8
$\begingroup$

It appears that the only nonlinearity in either model are terms of the form {positive number}/$h_p$.

In (4), $h_p$ can be moved to the RHS, resulting in a linear constraint.

In all other instances, this can be handled by use of Rotated Second Order Cone constraint, which is convex, and can be handled by Gurobi and CPLEX, as well as by many front-end optimization modeling systems which call them.

Specifically, for each $p$ for which there is a $1/h_p$ term, introduce $t_p$ as a new variable, and replace $1/h_p$ by $t_p$, along with adding to the model the Rotated Second Order Cone constraint $$\|1\|_2 \le \sqrt{h_pt_p}, t_p \ge 0, h_p \ge 0$$

The syntax for accomplishing this depends on the interface used.

In some syntaxes, the Rotated Second Order Cone constraint might look more like $$\|1\|^2_2 \le \ h_pt_p, t_p \ge 0, h_p \ge 0$$

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. Can you excuse my inexperience and educate me what $||1||_2$ and $||1||_2^2$ mean? Also, can you write linear expressions that I (as a dumb still living in a linear world) can understand and implement in Gurobi? $\endgroup$
    – tcokyasar
    Mar 24, 2020 at 0:51
  • 1
    $\begingroup$ That just means two-norm or two-norm squared of "1". There will be 3 entries in the Rotated Second Order Cone constraint, one of which is 1, and the others of which are $h_p,t_p$. The point is, you look up the syntax needed for Rotated Second Order Cone constraints in the modeling system or interface you are using, and specify the Rotated Second Order Cone constraint. In some systems, you can avoid this and use higher level modeling constructs, such as inv_pos($h_p$) in CVX, which calls Gurobi and formulates, under the hood, this Rotated Second Order Cone constraint transparently to the user. $\endgroup$ Mar 24, 2020 at 1:00
  • $\begingroup$ Thanks for the explanation. This means both models can be solved using Gurobi, right? Btw, would Gurobi or CPLEX provide a globally optimal or local optimal solution for such problems? I checked here [gurobi.com/documentation/9.0/examples/qcp_py.html] and the syntax seems identical to an ordinary LP. Is there anything I am missing? For this project, I am time constrained and I do not want to waste time by giving up after a lot of time put into it by coding for Gurobi. $\endgroup$
    – tcokyasar
    Mar 24, 2020 at 1:28
  • 3
    $\begingroup$ Gurobi should be able to handle either, using the reformulation I provided.In qcp.py, use # Add rotated cone: x^2 <= yz . m.addConstr(x*x <= y*z, "qc1") with x being 1, y being $h_p$, and z being $t_p$. $\endgroup$ Mar 24, 2020 at 1:43
  • 3
    $\begingroup$ Both Gurobi and CPLEX solve these (SOCP) problems to global optimality (unless they run into numerical difficulty, such as with bad scaling, or run out of memory or time. $\endgroup$ Mar 24, 2020 at 2:22

Your Answer

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

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