# Tag Info

19

There was an excellent lecture by Bob Bixby in 2015 at the Zuse Institute Berlin (ZIB) as part of Combinatorial Optimization at Work 2015. Bixby founded CPLEX and Gurobi, 2 of the 3 leading commercial MILP+ solvers. The lecture is divided into 3 videos, and gives the actual nitty gritty about what makes LP Simplex family solvers work effectively on large-...

16

the answer is even worse than "no"; I recently used SCIP to compute an LP relaxation, and the outcome (the value of the dual bound) depended on the branching rule I activated (even though I never branched!). How come? I had strong branching activated by default, so some conflicts were evaluated, and once these were known to the solver, it used them to ...

16

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

13

First, the problem is not a linear optimization problem, at least not for the objective function shown (which is nonlinear due the conditional portion in lines 10-13 and particularly the division by E_ges_i in line 13. Simulated annealing might be fine as a heuristic approach, but given the nonlinear objective, only accepting improving steps might or might ...

12

In theory no. In practice this can happen, because everything is done in floating point arithmetic. (See also this post https://www.gurobi.com/documentation/9.0/refman/tolerances_and_ill_conditi.html) If this happens i would look at the optimality certificates of the solutions. They might mention a large violation, even though the solver has terminated with ...

12

One of the best resource I know is the series of lectures on linear programming that was part of the CO@work workshop 2020. I especially recommend the lectures by Bob Bixby (he is the "bi" in "Gurobi"). They are freely available here, and you'll find some theoretical and practical viewpoints. As for presolving: it is fundamental for MIP, ...

12

TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem. Equivalence between primal and dual form Consider the (primal) LP problem \begin{align} (P) \ \ \ \min_{x \in \mathbb{R}^{n}} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & \sum_{j=1}^{n} a_{i, j} x_{j} \geq b_{i}, & i = 1, ..., M, \end{...

11

No, state of the art LP solvers do not do that. They do bring the problem into a computational form that suits the algorithm used. Note that in the case of simplex algorithms, modern solvers use the revised simplex method with lower and upper bounds that does not require standard form. You can get an idea of the computation forms used from "...

10

The problem of enumerating all vertices of a polytope has been studied, see for example Generating All Vertices of a Polyhedron Is Hard by Khachiyan, Boros, Borys, Elbassioni & Gurvich (available free online at Springer's website) and A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets by T. H. Matheiss and D. S. Rubin. ...

10

What I'm about to suggest is less sophisticated than (and presumably less efficient than) the presolvers Mark L. Stone mentions, but would be relatively easy to implement (assuming you have an LP solver). It assumes that the variables are continuous, not discrete. For simplicity, I'll assume that all inequalities are of the form $a_i'x \ge b_i$ ($i=1,\dots,N$...

9

Parma Polyhedra Library supports MIP on fractions. It's based on gmp and is used by gcc and Julia among other projects.

9

I suggest GLPK, which has the advantage of being fully open source and easily available everywhere (as a package on most Linux distribution). Run it from the command line with the --exact option. It is limited to LPs though (no MIPs), and not so easy to use directly from a programming language. From the release notes: GLPK 4.13 (release date: Nov 13, 2006) ...

9

The videos linked in the other answers contain some of what I will write here but both my writing and the videos are still only scratching on the surface of actual simplex implementations. I'll try to directly answer the questions here: Dual simplex is the most important simplex algorithm right now (because of its performance when solving LPs and because of ...

9

Presumably you have binary decision variables like $x_{ik} = 1$ if marble #$i$ is in slot #$k$. Then you can write a constraint like $$x_{ik} \le 1 - x_{jl} \qquad \forall \text{i < j and k > l}$$ In other words, if $i < j$ and $j$ is in slot $l$, then $i$ cannot be in any slot $k$ that comes after $l$.

8

Adding to Marco's answer, the value is most definitely affected. The way problem reduction algorithms work is that we often exploit problem information as it's processed to tighten variable bounds in real time, which of course affects the relaxation. This not only means that problem reduction will often change variable bounds, but the exact changes depend ...

8

A linear problem is always convex, because anything linear is convex. As pointed out by @Marco Lübbecke, any linear function is also concave. But polygons (feasible sets of linear programs) are only convex (and not concave). Check out this link, it is well explained, or this one for an algeabraic proof. Your example has only one feasible point (assuming $... 8 the Simplex algorithm iterates from extreme point to extreme point Technically, no. The simplex algorithm iterates from basis to basis. It just happens that feasible basic solutions correspond to extreme points. (for instance, the dual simplex iterates through dual-feasible basic solutions, which are not extreme points of the primal-feasible region). ... 8 There are many resources available to learn constraint modelling. When learning about constraint modelling I can recommend the following books: Principles of Constraint Programming by Krzysztof Apt is probably the most used constraint programming book that will teach you all the aspects of constraint programming. The book that would most fit your ... 8 When I started learning CP (coming from IP), one of the first things I discovered is that model elements are less standardized in CP than in IP. An IP model typically contains a polynomial objective function and equality/inequality constraints involving polynomial functions (where you are hoping the polynomials are linear or at worst quadratic). Beyond that (... 7 No, linear programming is convex, which you can prove directly from the definition. If$A x \le b$and$A y \le b$, then for arbitrary$\alpha\in[0,1]$, we have $$A (\alpha x+(1-\alpha)y) = \alpha A x+(1-\alpha)Ay \le \alpha b+(1-\alpha)b = b.$$ 7 Let$\epsilon > 0$be a tolerance for what you consider positive. Now impose linear constraints$z \ge \epsilon y$and$t \ge \epsilon y$. Because$z$and$t$are integer variables, you can take$\epsilon=1$. 6 If you want to implement an algorithm by your own, then we suggest you a randomized, derivative-free search, even simpler than Nelder-Mead approaches. Given a feasible solution (respecting the sum equal to 1), move randomly the values of the variables by an epsilon while maintaining the constraint feasible. If the solution is better, then keep it, otherwise ... 6 Your belief that there will be two different vertices in the set of optimal solutions as long as the feasible polyhedron contains more than a single point is incorrect. In practice, most LPs have unique solutions. As far as an upper bound on the number of optimal vertices, let's assume that you have$m$constraints including sign restrictions on the ... 6 Introduce a binary variable$y_j$to indicate whether$x_j(t)>0$for some$t$, and impose linear constraints: $$\sum_{t=1}^T x_j(t) = n_j y_j$$ 6 I have faced a similar issue. The above answer is up to the point but in addition to it, read the answer by Prof. Marco (link). The paper cited by him (pdf) helped me a lot in understanding the performance variability phenomenon. While solving MIPs, various algorithmic choices are influenced by the ordering of the variables, constraints in the input MIP ... 6 If$g=f+c$for some constant$c \ge 0$, then the optimal solutions will be the same, and this does not depend on linearity of either function. But if$f \le g$just in the feasible region and maybe not elsewhere, optimizing$g$is not necessarily equivalent to optimizing$f$. 6 I don't think there is anything special in AMPL for doing this, but it can be done. Option 1 is to add a term to the objective that penalizes the sum of all variables. (I'm assuming that all variables are nonnegative.) This will encourage the solver to force your "free" variables to zero. The catch is that you have to multiply this term by a ... 6 You obtain all vertices of a polytope using polymake. You can directly try the online version. 6 Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are violated ("row generation" or "cut generation"). Explicitly: Omit all big-M constraints and the associated binary variables. Solve the ... 6 You always want $$z \ge 0 \tag1$$ You want$x = 0 \implies z \le 0$: $$z \le M x \tag2$$ Similarly, you want$y = 0 \implies z \le 0\$: $$z \le M y \tag3$$

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