# Tag Info

## Hot answers tagged mixed-integer-programming

16

If you want something open-source, you probably want to try COIN's CBC code (they also have a couple other MILP solvers, like a branch-and-price framework, or SYMPHONY). Gurobi and CPLEX will be considerably faster, and as of the 2011 or 2012 INFORMS meeting, Gurobi was faster than CPLEX (though the performance metrics are of course problem dependent). On ...

8

Mixed integer linear programming problems are much harder to solve than linear programming problems. In terms of computational complexity, LP's can be solved in polynomial time while solving MILP is an NP-Hard problem. The known algorithms for solving MILP's have exponential worst case complexity. There are other software packages for mixed integer ...

6

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 example, for MILP problems you can choose from the Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi, and MOSEK solvers. Because of this, if you write it in JuMP, you can ...

5

You're dealing with a system that has "hysteresis" that is, the action of the pump depends not only on the current head $h$, but also on the past history of head. Your system has four identifiable states: 1: $h \geq h_{start}$. 2: $h \leq h_{stop}$. 3: $h_{stop} \leq h \leq h_{start}$ and $h$ was most recently at $h_{start}$. 4: $h_{stop} \leq h \leq ... 4 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:\mathbb{R}^{n}\to\mathbb{R}\qquad\max(x)\equiv\max_{i\in\{1,\ldots,n\}}x_{n}.$$ Your first constraint is "take the max element and ensure that it is less than$c$": ... 4 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$is feasible, but the midpoint$x_{1,1}=1/2$,$x_{1,2}=1/2$is not feasible. The feasible set of a system of linear equality and inequality constraints is ... 3 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}^k \delta_{ij} = 1$where$\delta_{ij}$is binary. Using the same binary variables the inverses are simply$x_{i}^{-1} = \sum_{j=1}^k j\delta_{ij}$Here is ... 3 Following others' suggestions, I have used (the commercial) GAMS for many projects. It is very straight forward; all you have to do is to put the mathematic formulation of your problem. It picks up the variables, constraints, objective functions and all the input data. Then, it provides a range of solvers (optimisers) for any case. Depending on your case, ... 3 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 in the previous answer is likely to run faster. But, for nonconvex QPs with products of continuous variables in the objective, this type of reformulation no ... 2 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 for QPs. Both companies have dedicated teams that comb the literature for various cuts to use in constructing a branch-and-bound tree, and employ heuristics ... 2 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. 2 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 the general case, you could solve the LP efficiently using a polynomial time algorithms (for instance, an interior point method) and obtain an optimal solution ... 2 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 objective (maximizing the number of cuboids). In the paper industry, the classical example is the 1-D cutting stock problem, where you try to cut a roll of paper ... 2 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$and so on. Often, a reasonable starting solution speeds up the solution process of a Branch-And-X a lot. Setting initial values is easy for solvers like ... 2 MIDACO is available in plain C/C++ and many other languages: http://www.midaco-solver.com/index.php/download/c 2 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 linear programming to use a constraint programming system with support for the "alldiff" constraint. 2 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 quickly using these). They claim to have support for Dantzig-Wolfe, although I haven't tried that. 1 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 Cone Problem. Here is code to solve it in YALMIP under MATLAB. v = intvar(size(v_o)) optimize([-k <= v <= k, sum(v) == l],norm(v-v_0)) disp(value(v))$ ...

1

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 benders decomposition and outer approximation. You also have heuristics, which pretty much let you do whatever you want. You can try genetic algorithms which are ...

1

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 Weighted Partial MAX-SAT as one of the categories. See here for the results from the 2016 competition. MaxHS looks quite good. Alternatively, formulate this ...

1

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 symmetry group is $G$ and submitting this ILP to Margot's solver for finding the symmetry group. Then you can replace this ILP with the original ILP and submit ...

1

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$. Then your optimization problem is posed on the hyperplane $(x_1,x_2,x_2)$. Similarly, if you allowed the full permutation group, you'd be optimizing on the line $... 1 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 widely used CPLEX and Gurobi solvers. So yes, these techniques can be useful in practice. Your question is really quite vague. Could you be more specific ... 1 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) x = binvar(n,1); objective = var(f(x),g(x)) + ... optimize([],objective) A suitable solver will be called (if f and g are linear operators it is a MIQP and if Gurobi is installed and visible on ... 1 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 list are closed-source, or do not have C++ interfaces. Some of the codes are in Fortran; if you can get copies, you might consider writing C++ interfaces, ... 1 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, for each$i$, modeling the set$\{z_{i,1}, \ldots, z_{i,n_{i}}\}$as a SOS1 set. Your current formulation essentially does the same thing. Is there any ... 1 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 sparsity)? Yes. The reason network simplex is faster primarily has to do with exploiting the total unimodularity of network matrices -- basically, network ... 1 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 solutions. (Of course, feel free to write constraints that exclude currently feasible solutions that are known to be suboptimal.) In the ideal case, this convex ... 1 So you are essentially asking how you can constrain the cardinality of a vector. The answer below is based on a standard approach called big-M modelling. Let$x$be a vector for which you want exactly$c$non-zeros. Introduce a new binary vector$y$which indicates if an element is zero or non-zero. Let$M\$ be an upper bound on the possible value of an ...

1

As far as I know, the only additional pieces you need are functions to convert to a rational approximation and find the least common multiple. Octave (and Matlab) have rat and lcm: x1 = A\[0;0;0;1]; [n,d] = rat(x1); x = x1*lcm(d(1),lcm(d(2),lcm(d(3),d(4)))) Matlab's lcm at least can't handle sets, so you'll need to customize this to other dimensions. It's ...

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