8 votes

What's the fastest software(open source) to solve mixed integer programming problem

If you want to try a bunch of different solvers, give Julia's JuMP modeling framework a try. It lets you write your model as a JuMP model, and then switch out the solvers with one line of code. For ...
user avatar
4 votes
Accepted

What is the name for this type of constraint?

I would call the constraint "upper- and lower-bounds on the maximum element." Note that you are actually dealing with two separate constraints. Define the max element function as follows $$ \max:\...
user avatar
4 votes
Accepted

Constraints 'exactly/at most one non-zero element' without binary variables

No, this is not possible. There is a standard way of showing this: The feasible region of your constraints is not convex. For example, $x_{1,1}=1$, $x_{1,2}=0$ is feasible, $x_{1,1}=0$, $x_{1,2}=1$ ...
user avatar
3 votes
Accepted

Sum of Inverse of Variables in an Optimization Problem

For the discrete version, it can be cast as a mixed-integer linear program. You just have to note that every element $x_i$ can be written as $x_i = \sum_{j=1}^k \frac{\delta_{ij}}{j}$ where $\sum_{j=1}...
user avatar
3 votes

Solver for a MIQP with an indefinite coefficient matrix

Note that CPLEX 12.6 and later includes functionality to solve general nonconvex QPs and MIQPs. However, for the special case of the product of a binary and continuous variables, the reformulation ...
user avatar
2 votes
Accepted

Mixed-integer quadratic programming, state of art

For LPs, MILPs, and QPs, Gurobi and CPLEX are considered best-of-breed. They beat any open-source general-purpose solver by at least an order of magnitude. I see no reason why that would be different ...
user avatar
2 votes
Accepted

Converting linear BIP constraints into convex hull

I don't think such a method exists. 3-SAT is polynomial-time reducible to integer programming.. If you could find the integer hull (i.e., convex hull of the integer feasible set) in polynomial time in ...
user avatar
2 votes
Accepted

Is there general algorithms to solve such 3D cutting problems?

This problem looks like a variant of a cutting stock problem. The general idea is to set up an optimization problem that encodes the geometric constraints (in your case, the cuboid shapes) and the ...
user avatar
2 votes
Accepted

Solving nested MILP problems

If the problems $P_k$ are not too difficult each, I would suggest to solve the problem for the lowest value of $k$ first and use the optimal solution as initial value for the second lowest value of $k$...
user avatar
2 votes

C++ mixed integer nonlinear programming (MINLP) solver

MIDACO is available in plain C/C++ and many other languages: http://www.midaco-solver.com/index.php/download/c
user avatar
2 votes

Ways to speed up solving an LP with Google's ortools

Have you tried any of the Coin-OR tools, like cbc or clp? They are pretty comparable to CPLEX for LP (not MIPs though), at least until a certain scale of the problem (your size should be solvable ...
user avatar
  • 21
2 votes
Accepted

Capturing the order of certain objects in an MILP

Encoding this constraint in a mixed integer linear programming formulation requires $n^{2}$ variables and doesn't work very well in practice for large $n$. An alternative is to go beyond integer ...
user avatar
2 votes

C++ mixed integer nonlinear programming (MINLP) solver

A list of MINLP solvers can be found at: MINLPLib Instances Some of these solvers are written in C++ and could be called directly from your code.
user avatar
1 vote

Linearize problem with absolute value

I don’t have any to mind, but you can use a family of functions which are parameterized and smooth with absolute value as their limit. Then you can solve for multiple, usually shrinking, values of the ...
user avatar
  • 10.8k
1 vote

Using MILP to place a set of primers along a genome

Formulating the problem This MILP method you've constructed is pretty cool! But it's not the way I would choose to solve this problem. Rather, I would use dynamic programming. To do so, recognize that ...
user avatar
  • 3,111
1 vote
Accepted

MILP formulation and optimization

Is there any obvious easier way of modelling this problem? e.g. as a MILP with less integer variables or using another optimization methodology. The first tactic that immediately comes to mind is, ...
user avatar
1 vote

Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

Practically speaking, from the aspect of time efficiency, are there any significant differences between modelling as a mixed integer programming and modeling as a network problem? And why (other than ...
user avatar
1 vote

$L_2$ projection with integer constraints and prescribed sum

Presuming you have a suitable solver (CPLEX, GUROBI, MOSEK, SCIP, many others), you can solve this as a Mixed-Integer Quadratic Program (by squaring the objective) or as a Mixed-Integer Second Order ...
user avatar
1 vote

Nonlinear integer program with linear constraints

There are solvers for non linear mixed integer programming that can solve problems to optimality under certain conditions, or provide good quality solutions otherwise. These are based in generalized ...
user avatar
1 vote

optimal SAT solver with weighted variables

This is an instance of the Weighted Partial MAX-SAT problem. You could take a look at MAX-SAT solvers; many of them will support this kind of query. For instance, the annual MAX-SAT competition has ...
user avatar
  • 350
1 vote

Breaking symmetries in a (binary) integer program

It is possible to use any group $G$ for isomorphism pruning with Margot's isomorphism pruning (ISOP 1.1) solver. One way of doing this is by creating a different integer linear program (ILP) whose ...
user avatar
1 vote

Breaking symmetries in a (binary) integer program

I think you should explore the geometry of the object described by your permutation group. Consider for example if you had three variables and if your permutations allow to permute $x_2$ and $x_3$. ...
user avatar
1 vote

Breaking symmetries in a (binary) integer program

At this point quite a few papers have been written about exploiting symmetry in integer programming and symmetry breaking techniques have been implemented by lots of people and are available in the ...
user avatar
1 vote

How to formulate variance minimization as a mixed integer quadratic program

As answered elsewhere, for MATLAB you have things like CVX and YALMIP. In YALMIP, you would solve using something like (assuming you have defined function f and g) ...
user avatar
1 vote

C++ mixed integer nonlinear programming (MINLP) solver

Of that list by BrianBorchers, the main MINLP C++ codes that I'm familiar with are Bonmin and Couenne. Both are part of the COIN-OR project, and are open source. The remainder of the libraries in that ...
user avatar
1 vote

enhancing a MIP formulation of Ising model

Generally speaking, you want to construct formulations such that the convex hull of the linear programming (LP) relaxation is as small as possible, while retaining all potentially optimal feasible ...
user avatar
1 vote

What's the fastest software(open source) to solve mixed integer programming problem

I'd recommend SCIP or HiGHS (www.highs.dev). On the industry standard benchmarks (http://plato.asu.edu/bench.html) their relative performance is similar, but on specific classes of MIPs one may be ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible