5
$\begingroup$

I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data. I would like to understand:

  1. Can this model be formulated as convex, such as piecewise linear or quadratic, or SOCP? I will be interested to know both for the case when the variables $x_i$ are binary and also if they are non-binary.
  2. Can we use a global solver, such as Octeract or Baron to solve this problem of large size (n=10,000 and T=1200)? I have seen a number of posts on this website that some global solvers can reformulate the model that can be solved efficiently, but it would be good to know whether it will work for this case.

$\max\ q_1+q_2 $

$\text{Subject to}$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \sum_{t=0}^{T} \frac{F_{t}}{(1+q_{1})^{t}} \qquad \qquad \qquad(1)$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \sum_{t=0}^{T}\sum_{i=1}^{n} \frac{b_{i}^{t} x_{i}}{\left ( 1+q_{2} \right )^{t}} \qquad \qquad(2)$

$\qquad \sum_{i=1}^{n} p_{i} x_{i} = \beta \sum_{t=0}^{T} \frac{F_{t}}{(1+q_{1}+q_{2})^{t}} \qquad \qquad(3)$

where

$x_i\in \{0,1\} \qquad \text{are optimization variables}$

$q_1 \geq\ 0, \qquad q_2 \geq\ 0 \qquad \text{are variables}$

$i\ =\ {1,2,3,...n}$

$t\ =\ {0,1,2,...T}$

$\beta \quad \text{is a constant}$

$F\ =\ {c_1,c_2,c_3,...c_T} \quad \text{(coefficients)}$

$p_i\ =\ {p_1,p_2,p_3,...p_n} \quad \text{(coefficients)}$

$b_i\ =\ {b_i^0,b_i^1,b_i^2,...b_i^T} \quad \text{(coefficients)}$

I have illustrated this using numerical data in the attached image (in case if the maths above is written incorrectly) enter image description here

$\endgroup$
3
  • $\begingroup$ (1) Duplicating expressions is almost always bad. (2) Always first try to solve as an RMINLP (relaxed MINLP i.e. an NLP). If that does not work, you are in trouble. (3) Try to add good bounds. (4) It may be better to multiply by (1+q1)**(-t) to prevent large numbers. $\endgroup$ Jan 29 at 5:43
  • $\begingroup$ @Erwin Kalvelagen I have explained in my question that I would like to solve two cases: (i) $ x_i$ are binary; (ii) $ x_i$ are non-binary (or binary condition is relaxed). The reason I have set out these two cases is because product of two variables involving one binary can be more easily transformed to a MILP. $\endgroup$
    – Marry
    Jan 29 at 6:28
  • $\begingroup$ Also, you omitted a value for $\beta$ in your example. Notice that if $\beta = 1$, $q_2$ must be 0 to let the RHS of (1) and (3) be equal, which reduces the problem dimension a bit. If $\beta < 1$, the RHS of (3) is strictly less than the RHS of (1) for any nonnegative $q_2$, making the problem infeasible. $\endgroup$
    – prubin
    Jan 29 at 21:58
3
$\begingroup$

As far as I can see there is no exact convex reformulation for this, unless someone else can think of a nice trick. Constraint 1 can actually be convexified for certain ranges of $q_i$ as these functions are partially convex, e.g. $1/(1+x)^3$ is:

enter image description here

The fractions in constraint 3 are also convex past certain hyperplanes. However, you would have to restrict your feasible region quite significantly to impose that, which means missing out on solutions.

Constraint 2 unfortunately can not be convexified because of the multiplication by $x_i$.

As you mentioned, a deterministic global optimisation solver such as Octeract Engine, Baron, ANTIGONE, or Couenne, will solve this problem automatically. The solver will not make the problem convex, but will instead generate a convex relaxation that can be solved rigorously (because it's convex). This value provides a rigorous lower bound on your problem (assuming minimisation), and the solver will the iteratively generate and solves such relaxations using branch-and-bound until it proves global optimality.

If you want to try this out, Couenne and our own Octeract Engine are free to use for any purpose.

As a final note, keep in mind that equality constraints with convex functional forms do not generally make the problem convex. Intuitively, assuming we're minimising subject to e.g., $x^2=1$, this constraint is equivalent to:

$x^2 \le 1$, and

$ x^2\ge1 \implies-x^2 \le-1 $.

The first constraint defines a convex feasible region, but the second constraint defines a concave one. The intersection of the two gives us the equality feasible region.

Some solvers can handle this out-of-the-box (e.g., Octeract Engine), but certain solvers (especially if they are convex-only) only support convex inequality constraints, so make sure to check what your solver is designed to handle.

As a final-final note on semantics, since you are maximising, a convex optimisation problem is either (i) the maximisation of a concave objective, or (ii) the minimisation of a convex objective, over a convex set. Convex problems are can be minimized to global optimality in a single local solve, and concave problems can be maximized to global optimality in a single local solve. Since your objective is linear this doesn't affect your problem, but keep it in mind as you experiment with reformulations.

$\endgroup$
2
  • $\begingroup$ Thank you @Nikos Kazazakis for the detailed answer. Can the deterministic global solvers that you have mentioned solve this problem with 10,000 binary variables ($x_i$ in the question) or if $x_i$ are 10,000 continuous variables? My understanding is that usually global solvers can solve a non-convex problem with fewer variables. So probably Couenne would not work, but Octeract may solve it. I can think of a trick to convexify constraint (2) in my question but it is an approximation and a global solver may be a better choice $\endgroup$
    – Marry
    Jan 29 at 18:41
  • $\begingroup$ Size isn't really an issue for a high performance solver, it's more about detecting and exploiting structure. Octeract engine has solved a 10million variable problem in 5 minutes, whilst certain 5-variable problems can still take hours to converge, so it really depends :) $\endgroup$ Jan 30 at 0:13
3
$\begingroup$

I might be missing something here (and by "might be" I mean "probably am"), but at least for the case of $x_i \in [0,1]$ you might be able to get solutions via "brute force". I'm assuming that all the parameters ($F,p,b,\beta$) are positive.

Suppose we slap a somewhat arbitrary upper bound $M$ on $q_1$, and then do a bisection search (or any other one-dimensional line search) on $q_1$. Since (1)-(3) all have the same LHS, the RHS of (1) equals the RHS of (3), and for fixed $q_1$ the RHS of (3) looks like a strictly decreasing function of $q_2$. So given a value of $q_1$, either we can use the fact that the RHS of (3) equals the known RHS of (1) to solve for $q_2$, or else we find there is no solution (so the value of $q_1$ is infeasible).

Assuming we find a value for $q_2$, we solve for $x$ satisfying (1) and (2). Given $q_1$ and $q_2$, these are now linear equations in $x$, and if the system is underdetermined (likely) that's fine. We don't care which feasible solution we find; we just need to confirm that there is a solution that respects the bounds on $x$. One way to do this would be solve a linear program. If the LP is infeasible, again that means our choice of $q_1$ is infeasible. If it's feasible, we have a new feasible solution with a known objective value, and now we go back to the line search of $q_1$ and use the new objective value to decide where to look next.

$\endgroup$
4
  • $\begingroup$ Thank you @prubin. Your assumptions regarding sign of the parameters are correct. The part I am stuck with is constraint (3) even if try a more simplified version of the problem. E.g. assume that $q_1$ is fixed as zero, so objective is just to maximize $q_2$ and we get rid of constraint (1). The simplified problem is given by: $\max\ q_2 $ $\qquad \sum_{i=1}^{n} p_{i} x_{i} = \sum_{t=0}^{T}\sum_{i=1}^{n} \frac{b_{i}^{t} x_{i}}{\left ( 1+q_{2} \right )^{t}} \qquad \qquad(2)$ $\qquad \sum_{i=1}^{n} p_{i} x_{i} = \beta \sum_{t=0}^{T} \frac{F_{t}}{(1+ q_{2})^{t}} \qquad \qquad(3)$ $\endgroup$
    – Marry
    Jan 29 at 19:37
  • $\begingroup$ If $q_1$ is fixed, you do not need to maximize $q_2$. There is at most one value of $q_2$ that will work for a given value of $q_1$; you just need to solve for it. $\endgroup$
    – prubin
    Jan 30 at 17:07
  • $\begingroup$ For your example above with $\beta = 1.01866$ I get $q_1 = 5.450373$, $q_2 = 0.4664311$, $x = (1, 0.1334608, 0)$ and objective value $5.916804$. There's a little rounding error in there. The LHS of the three constraints evaluates to $126.6189$ and the RHSes evaluate to $126.6186$, $126.6188$ and $126.6186$. $\endgroup$
    – prubin
    Jan 31 at 0:01
  • $\begingroup$ Thanks for looking into it $\endgroup$
    – Marry
    Jan 31 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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