A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

14

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 ...

6

A typical way to deal with this is to replace products $xy$ where $x$ is binary and $y$ continuous with a new variable $w$, and then add a constraint to ensure $w=0$ when $x=0$ and $w=y$ when $x=1$. This can be accomplished with $-M(1-x) \leq w-y \leq M(1-x)$, $-Mx \leq w \leq Mx$ where $M$ is a sufficiently large (but as small as possible) constant to ...

6

In the comments to Johan's post I said it seems a shame to throw a full MIQP solver at this. For a general $n$-dimensional polyhedron, I'd certainly hold to that. But since this is a 3-dimensional problem, it might be competitive to do an intelligent exhaustive search. I suppose it depends on the application. First, suppose we have constructed a generator ...

6

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 ...

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 It won't matter to any worthwhile mixed-integer linear programming (MILP, also known as MIP) solver if you keep or omit the integral constraints, as long as your constraint matrix is truly totally unimodular. To be on the safe side, keep the integral constraints and call your MILP solver. Any solver utilizing a branch-and-bound or branch-and-cut framework ... 4 If you simply want a formulation (not necessarily a good way to solve the problem), you can state it as minimizing the distance$||x-z||$where$z$is an integer vector, satisfying$Az\leq b$(inside polyhedron) and$x$is a binary combination of the vertices$x = \sum_{i=1}^N \delta_i v_i$where$\sum_{i=1}^N \delta_i = 1$,$\delta$binary, and$v_i$are ... 4 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 ... 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 ... 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$": ... 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 Both linear and integer programming can be solved in fast polynomial time if the dimension is fixed. Here is an example reference for the integer case: Eisenbrand, "Fast integer programming in fixed dimension", 2003. 3 You haven't said whether$f$can be evaluated at points where$x$,$y$, and$z$are real numbers within the specified ranges that aren't integers. If this makes no sense, than the function isn't actually convex. You also haven't said whether$f$is smooth (e.g. is it twice continuously differentiable?) Conventional gradient based optimization algorithms ... 3 I came across this issue recently, and discovered that if you first add the constraints to an IloRangeArray, and then add that object to the model, you'll see a significant speed-up. Removing constraints is also faster if they are contained in a container object like an IloRangeArray. 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 ... 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 ... 2 Disclaimer: I'm not an expert in this field; I've just worked with people who do this sort of thing. Binary decisions are always solved using a glorified guess-and-check algorithm Setting aside the differential equations for a moment, any integer component of a mixed-integer linear (or nonlinear) programming solver is probably going to use some sort of ... 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 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 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 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. 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 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

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

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 ...

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