# How to know if a combinatorial optimization problem is linear or not?

I want to know if a combinatorial problem like the knapsack problem is linear or not. And how do we know if a given problem is convex or not?

• You can start by checking if the formulation (objective function and constraints) is linear or not. But keep in mind that many problems can be formulated both ways, so it is not because you have a non linear formulation that there does not exist a linear version (especially if you allow integer variables, and consider that an integer formulation is linear). Oct 8 at 11:57
• @Majid majid, from the solver point of view, there are some of the useful facilities to detect type of the problem and its specifications. For instance, Lindo, Mosek, Knitro, Shot, etc. Have had nice features to do that. Oct 8 at 12:31
• The equivalence of problems may not be obvious and sometimes surprising, like the linear equivalent of linear-fractional programming (Boyd 4.3.2). I don't think it is easy (if possible) to mathmatically prove the non-existence of such transformation for a given problem.
– xd y
Oct 8 at 13:15
• a linear problem or not, a convex problem or not did affect the performance of a given metaheuristic? when do these informations help us? Oct 8 at 18:05

In general, you need to examine the structure of all expressions.

If you want an automated way for a specific model, with the Octeract Engine Python API (our free solver) you can do:

from octeract import *

model = Model()
model.import_model_file("/your/model/file")
print(model)
print(model.is_problem_convex())


If I e.g.run this for ex6_1_1.nl, I get the following:

Structure : NLP
Convexity : nonconvex
------------------------------------------
var x1 >= 1e-07, <= 0.5;
var x2 >= 1e-07, <= 0.5;
var x3 >= 1e-07, <= 0.5;
var x4 >= 1e-07, <= 0.5;
var x5 >= 0, <= 1e+07;
var x6 >= 0, <= 1e+07;
var x7 >= 0, <= 1e+07;
var x8 >= 0, <= 1e+07;

minimize obj : (x4*(log(x4)+(-1*log((x2+x4)))))+(x2*(log(x2)+(-1*log((x2+x4)))))+(x1*(log(x1)+(-1*log((x1+x3)))))+(x3*(log(x3)+(-1*log((x1+x3)))))+(0.746*x3*x5)+(0.746*x4*x6)+(0.925*x1*x7)+(0.925*x2*x8)+0;

subject to

c1 : (x5*((0.159*x3)+x1))+-1.0*x1+0.0 = 0;
c2 : (x6*((0.159*x4)+x2))+-1.0*x2+0.0 = 0;
c3 : (x7*(x3+(0.308*x1)))+-1.0*x3+0.0 = 0;
c4 : (x8*(x4+(0.308*x2)))+-1.0*x4+0.0 = 0;
c5 : 1.0*x2+1.0*x1+0.0 = 0.5;
c6 : 1.0*x4+1.0*x3+0.0 = 0.5;
------------------------------------------

Model is convex:
False

• In general there might convex but non-linear problems such as cone programming. Oct 8 at 17:46