1
$\begingroup$

I need to solve the following integer program:

$\text{minimize } \sum_{i=1}^n(a_{i0} x_i + \sum_{k=1}^3 a_{ik}w_i^k + \sum_{j=1}^m d_{ij}y_{ij})$

$\text{subject to}$ $$ \sum_{i=1}^n y_{ij}=1, \quad j=1,\ldots,m,\\ \sum_{j=1}^m y_{ij}\le m x_i, \quad i=1,\ldots,n,\\ \sum_{j=1}^m y_{ij} b_{ij} \le x_i, \quad i=1,\ldots,n,\\ \sum_{j=1}^m y_{ij} c_{ij} \le w_i, \quad i=1,\ldots,n,\\ w_i \le x_i, \quad i=1,\ldots,n,\\ x_i \in \{0,1\}, \quad i=1,\ldots,n\\ y_{ij} \in \{0,1\}, \quad i=1,\ldots,n,\; j=1,\ldots,m,\\ w_i \in [0,1], \quad i=1,\ldots,n. $$

where $a_{ik},b_{ij},c_{ij},d_{ij} \in \mathbb{R}$ are real constants.

Note that, if I'm not wrong, the above problem should be convex since the second derivative of the objective function is always positive (that is, some coefficient can be negative but the whole sum is guaranteed to be positive).

I know there is the excellent CVX toolbox, but it is MATLAB only. What I'm looking for is a solver with similar capabilities that has C/C++ API.

Can you suggest anyone?

$\endgroup$
3
$\begingroup$

From a quick look, your problem is LINEAR. This makes a huge difference, since nonlinear mixed integer programming is much more difficult than mixed integer linear programming.

If you are a student you can get academic licenses for GUROBI or CPLEX. Those are pretty much the best commercial solvers for MILPs. If you want something open source, you can try the COIN-OR project. It provides CBC and SYMPHONY, both MILP solvers which are quite good. If your problem isn't too big you can also try GLPK. There's quite a lot of MILP solvers out there so you can try looking for more on google.

On a side note, your variables are all binary, which makes me think this is a combinatorial problem. If you have good structure, I would try to exploit it and go for a greedy algorithm and see if you can prove optimality or use it as a good heuristic.

EDIT: For mixed integer nonlinear programming COIN-OR provides BONMIN and COUENNE. SCIP also claims to be able to solve MINLPs but not entirely sure if they restrict problems to being quadratic.

$\endgroup$
  • $\begingroup$ Are you sure that the problem is linear? I'm not a mathematician (I'm a computer scientists) so I'm not an expert, but I thought that since the objective function contains a cubic polynomial for variables $w_i$ (which are real variables bounded in the $[0,1]$ real interval) the problem is to be considered as a convex mixed-integer nonlinear problem. Am I wrong? $\endgroup$ – seg.fault Aug 6 '14 at 19:09
  • $\begingroup$ You're right, segault, your objective function is not linear, wonko's suggestions here won't work for you. $\endgroup$ – Michael Grant Aug 6 '14 at 19:12
  • $\begingroup$ Ah you're right, didn't notice that. Wasn't reading the model carefully enough. Can you check if you can reformulate this into a linear model? In any case I edited the answer and put in some mixed integer nonlinear solvers. $\endgroup$ – wonko Aug 6 '14 at 19:13
  • $\begingroup$ I cannot remove the cubic polynomial from the objective and unfortunately I'm not aware of techniques to transform such type of problem into linear one. Do they exist? If they do, can you give me some hint or reference? $\endgroup$ – seg.fault Aug 6 '14 at 19:16
  • 1
    $\begingroup$ Yes, it has a separable convex solver but I don't think that solver can handle binary or integer variables as well. If it does, by all means, go for it. $\endgroup$ – Michael Grant Aug 6 '14 at 22:17
0
$\begingroup$

Take a look at dlib - it has some decent routines for general nonlinear optimization that you might be able to adapt to your problem (though on second glance, I'm not sure it handles integer programs directly). I played with it some a while back but it ended up being faster to write my own system. The best part: it's extremely well documented and written.

$\endgroup$
  • $\begingroup$ Thanks. I'm looking for something more specific for my problem (convexity + mixed-integer), As @wonko suggested, there are good MINLP solvers, but, if possible, I'm looking for something more specialized (like CVX) $\endgroup$ – seg.fault Aug 6 '14 at 19:40

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.