I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total unimodularity ensures an integer solution at optimality. However, I need to incorporate an additional constraint that disrupts the TU property of the matrix. To avoid losing the TU advantage, I'm considering reformulating the objective function to preserve integrality without directly adding the problematic constraint. This reformulation would change the objective function of my model into a nonlinear convex function, which is of the form like this:

\begin{align*} \min \sum_{i\in I} c_i x_i + \sum_{i\in I, j\in J} (x_i - x_j)^2 \end{align*}

I have limited practical experience with nonlinear convex optimization and am uncertain about the performance of modern solvers for such problems. Specifically, can optimization solvers handle nonlinear convex models with similar efficiency to LPs for most practical cases?

  • $\begingroup$ You can formulate that as a second order cone problem, which solves efficiently. See docs.mosek.com/modeling-cookbook/index.html $\endgroup$ Feb 20 at 11:38
  • $\begingroup$ Thanks. I just realized though that the TU property isn't too helpful to nonlinear convex optimization problems since it doesn't guarantee that the optimal solution will be at an extreme point $\endgroup$ Feb 20 at 14:55
  • $\begingroup$ @graphtheory123, as far as I know, many of the standard MIP/MINLP solvers, convert non-linear terms internally, in your case quadratic ones, into whose linear or approximated equivalent by adding extra variables and constraints. This may disrupt TU conditions. $\endgroup$
    – A.Omidi
    Feb 21 at 5:58
  • $\begingroup$ Yes, solving a nonlinear problem will in general lead to a basic solution. $\endgroup$ Feb 21 at 11:26
  • $\begingroup$ @ErlingMOSEK could you please clarify what you mean. Isn't it possible that a nonlinear convex problem does not have an optimal solution which is basic? $\endgroup$ Feb 21 at 14:28


Your Answer

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