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

18

For context: most (if not all) major LP solvers are built on 2 algorithms: the simplex method, and the interior-point method. The simplex method is intrinsically sequential: you're doing a lot of (cheap) operations called pivots, and the matrices involved are usually sparse. At each pivot, you essentially perform a rank-one update of a sparse LU ...

17

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

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

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

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

10

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

10

There is a new open source solver that looks quite promising, HiGHS: https://www.maths.ed.ac.uk/hall/HiGHS/ But as pointed out by others, for mixed-integer programming problems, at the moment, open-source solvers can't compete on performance and reliability with commercial solvers.

9

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

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

Diagnosis: Cplex can not find a feasible solution. Interesting, as 1788 binary variables is not extremely large. You can play a bit with mipemphasis option. (In general, I am not a fan of using all kinds of solver options, but this option is one of the very few I use on a regular basis). May be fpheur (feasibility pump) is also worth looking at. There are ...

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

8

In Pelánek (2011)1, Sudoku difficulty evaluation was investigated across four existing metrics. These are based on incidences of various logic techniques (see constant folding). Results based on Spearman's correlation coefficient are given in Table 1. Evaluation of difficulty through dynamical systems has also been explored2. In this setting, one considers ...

8

You need a tolerance $\epsilon>0$, and you can strengthen your first two inequality constraints: \begin{align} \Gamma &= \theta x \\ \gamma &= \theta y \\ \epsilon y \le x &\le y \end{align}

8

MINTO has not been updated in many years. It was innovative in its day, but most of its ideas like fractional cuts and presolve were incorporated years ago into commercial MILP solvers like CPLEX and Gurobi. For most applications today, the best option is one of the major commercial solvers like CPLEX or Gurobi; these are available at no-cost for academic ...

7

Without the $c$ variable, you could do a Charnes-Cooper transformation, followed by a linearization of a product of a continuous and binary variable, as shown in my answer https://math.stackexchange.com/questions/3500493/doing-a-charnes-cooper-transformation-with-matrices-and-an-zero-one-constraint/3500608#3500608 If $c$ has a small enough upper bound, you ...

7

@user3680510 gave the correct answer in a comment. Here's a way to derive it via conjunctive normal form: $$i \not= j \\ (i \implies \lnot j) \land (\lnot i \implies j) \\ (\lnot i \lor \lnot j) \land (i \lor j) \\ (1 - i + 1 - j \ge 1) \land (i + j \ge 1) \\ (i + j \le 1) \land (i + j \ge 1) \\ i + j = 1$$ To prevent both to be 1 at the same time: \... 7 The following isn't meant to be exhaustive. It usually depends on the structure of the matrix because that impacts the way you choose it. In general there are sparse variants for many of the general matrix decompositions you see LU, QR, SVD and what not. There are also sparse Kyrlov methods such as the shifted Block Lanczos method. If it isn't symmetric then ... 7 Introduce a binary variable y_{i,j} and linear constraints \begin{align} x_{i,j} &\le M y_{i,j} \tag1 \\ y_{i,j} + y_{j,i} &\le 1 \tag2 \end{align} Constraint (1) enforces x_{i,j} > 0 \implies y_{i,j} = 1. Constraint (2) enforces y_{i,j} = 1 \implies y_{j,i} = 0. Constraint (1) (with the roles of i and j interchanged) enforces y_{... 7 \max(y,z)\le b is equivalent to \begin{align} y&\le b\\ z&\le b \end{align} The \min constraint is similar. 7 Without using a small epsilon, you can’t enforce strict inequality. Here’s one approach that allows ambiguity at the endpoints of each interval, as your proposed constraint does: x+y+z=1\\ 0x+\frac{1}{3}y+\frac{2}{3}z \le \text{cond} \le \frac{1}{3}x+\frac{2}{3}y+1z $$7 A greedy heuristic is natural to try here: Declare all groups to be admissible. Find an admissible group g with the largest weight. Set u_g=1. Declare all groups h with N_h \cap N_g \not= \emptyset inadmissible. If some i is still uncovered, go to step 2. For your sample data in the linked question, this greedy heuristic returns groups$$\{11,12,...

6

You could also use polymake which includes a few exact linear programming libraries (including my own one). It should also be possible to compile SoPlex with GMP support, but I actually never tried it.

6

You obtain all vertices of a polytope using polymake. You can directly try the online version.

6

There is a rich literature on reconciling multiple objectives (which I will not attempt to repeat in its entirety here, although what follows is long-winded enough to appear to do so). The ones I know (possibly not all of them) fall into the following categories. Optimize a weighted combination of the objectives (as you have written). The big problem here ...

6

It sounds like you want something along the lines of a (partial) presolve, which most commercial solvers implement. For example, Gurobi has a presolve accessible from the Python interface which should do what you want, and maybe more. https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work- I suppose you can provide a model just ...

6

As Sune said in a comment, they really are both "big-M" constraints, differing (perhaps) in how "big" $M$ is. If you choose $M$ sufficiently large, then yes, your second constraint will not meaningfully limit the values of the $x$ variables ... which likely is by design. Other constraints in the model will probably restrict the values of ...

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