45

This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, thus $x = 0$ and/or $y = 0$ implies that $z$ must equal zero. $$z \leq x\\z \leq y$$ The only thing left is to force $z$ to equal one if the product of $x$ and $...


42

Quadratic assignment problem Vehicle routing problem also at HEC Traveling salesman Graph partitioning Quantified Boolean formulas Constraint solvers Shortest paths Mixed integer programming Train timetabling Set covering and packing Beasley's OR library with many problems Maximum clique, Maximum independent set, minimum vertex cover, vertex coloring ...


31

Suppose we can give a finite upper bound for $y$ called $M$. Then this constraint can easily be linearized by using the so-called big $M$ method. We introduce a new variable $z$ that should take the same value as the product $x y$. Notice that the product which we model by $z$ equals zero if $x = 0$ but $z$ can take any value between $0$ and $M$ if $x = 1$. ...


30

There sure is! It's called the SOB Method, originally proposed by A.T. Benjamin. In the SOB method, we classify each variable and each constraint as either sensible, odd, or bizarre (hence the name SOB). For "usual" models, we expect variables to be non-negative (for example, lengths, times, etc.). Sometimes, a variable might be unrestricted (maybe like $xy$...


28

The following answer presumes some familiarity with the limitations of floating-point arithmetic (rounding, truncation and representation errors), which I will lump together as “rounding error”. It is a trimmed down version of a longer blog post [1] with more detail and some astute comments from subject matter experts. $M$ in the constraints The constraint ...


27

If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$". To enforce "if $x=0$ then $y=1$": use $$y \ge 1-x.$$ To enforce "if $x=1$ then $y=1$": use $$y \ge x.$$ If you want to require that $y=1$ if and only if the condition holds, then replace the $\ge$s above with $=$s. If $x$ is continuous: In this case, numerical inaccuracy ...


27

The irreducible infeasible subsystem (IIS) for an infeasible linear program (LP) is a minimal subset of constraints that has no feasible solution, i.e., an inconsistent set of constraints for which any proper subset of the constraints is consistent. It is not true that an IIS is unique. For intuition, consider that there may be more than one source of ...


26

Interesting topic (the question was raised several times by my students as well). My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a very large “unnatural” face where your search is trapped for a long while. Essentially you lose the objective function grip, and do not gain anything. Let me ...


25

For sure Julian Hall meant sparse problems. It is possible to solve huge sparse LP problems. If they have sufficiently nice structure your can solve problems with up 231 constraints or variables. For instance we solve some huge problems in this GitHub tutorial in a moderate amount of time. Saying some about the solution time based of some simple ...


23

Here is a start. Please add to this. BOLIB: Bilevel Optimization LIBrary of Test Problems https://eprints.soton.ac.uk/436854/1/BOLIBver2.pdf CBLIB: The Conic Benchmark Library: http://cblib.zib.de/ . Twitter at https://twitter.com/cblibtw COMPlib: COnstraint Matrix-optimization Problem library (Nonlinear SDPs, control system design, and related problems) ...


23

KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear programming duality is just a special case of Lagrange duality applied to linear programs. Consider the following convex minimization problem \begin{align} p^* =...


21

People do use the term "big-$M$ method" to mean two different things. In both cases, the name refers to the use of a large constant, often denoted $M$. The first use of the term refers to a method for finding an initial feasible solution for the simplex method. (Another common method for doing this is the two-phase method.) Sometimes people also use the ...


20

Alternatively, by observing that $|c \cdot x|= \max \{c^T x, -c^T x\}$, $$\min_x |c\cdot x| \text{ subject to } Ax \le b$$ can be rewritten as $$\min_x \max \{c^T x, -c^T x\} \text{ subject to } Ax \le b$$ which is equivalent to $$\min_{x, z} z$$ subject to $$z \ge c^Tx$$ $$z \ge -c^Tx$$ $$Ax \le b$$ which is a linear program. This ...


20

OpenSolver is an LP/IP/NLP solver that plugs into Microsoft Excel. I used it for some classroom stuff a while back and was quite pleased with it. If you are interested in metaheuristics, there are quite a few open-source contributions floating around (about which I mostly know nothing). I have used the Watchmaker Framework for Evolutionary Computation (i.e.,...


20

This is an extremely interesting question. I agree with @Richard that you have to try it out. I have seen that tiny changes to a model can make huge differences, but in my experience, more general changes to a model may have more impact in the end. There are, I think, some guidelines that may help, from algorithmics and theory. Why do we choose "big $M$ as ...


20

For books with a focus on industrial applications, see this other question of this forum As textbooks, I would recommend to have a look at: General Intro to OR: W. Winston. Operations Research: Applications and Algorithms (4th Ed.). Brooks/Cole. 2004. Modeling: H.P. Williams. Model building in mathematical programming. John Wiley & Sons, 2013. D. Chen, R....


20

This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP. Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. Therefore, the left-hand side is the two-norm of the vector over $i \in I$ having elements $\sqrt{a_{ij}} x_{ij}$. I don't know whether this is the best way ...


20

The following definitions are taken from this lecture. Polyhedron A polyhedron in $\Bbb R^n$ is the intersection of finitely many sets of all points $x$, such that $ax\le b$ for some $a\in\Bbb R^n$ and $b\in\Bbb R$. Polyhedra Polyhedra is the plural of polyhedron. Polytope A polytope is a bounded polyhedron, equivalent to the convex hull of a ...


19

It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \implies (x \wedge y)\right) \bigwedge \left((x \wedge y) \implies z\right) \\ & \left(\neg z \vee (x \wedge y)\right) \bigwedge \left(\neg(x \wedge y) \vee z\...


19

Mittelmann benchmarks a number of (LP-)Solvers, some of which are open source. A recent new open source solver is HiGHS.


19

You should take a look at GCG, a plugin for SCIP and part of the SCIP Optimization Suite. After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to obtain an extended formulation of the problem. The decomposition is based on a structure either provided by the user or automatically detected by one of the ...


19

Hans Mittelmann maintains a well-respected website with benchmarks for optimization software. For LP problems, both simplex and barrier methods are compared. The first instance on the barrier page is L1_sixm1000obs, with 3,082,940 constraints, 1,426,256 variables, and 14,262,560 non-zero elements in the constraint matrix. This problem is solved within the ...


19

It is not true that the Two-Phase methods requires Simplex iterations, it is just the common way to do it. Let's assume we have a linear program with $n$ variables and $m$ constraints. Step 1) Convert this LP into standard form by splitting all unbounded variables into two $\geq 0$ variables, making sure $b$ is non-negative (by multiplying the rows that ...


19

The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity. Consider a linear program. That is, we want to minimize a ...


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

There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks about many details and tricks for implementing general bounds, finding a feasible basis, pricing, and solving linear systems. In particular at about 38:00 he ...


18

I’m assuming that we want our models to be solved as quickly as possible. If that is the case, then the honest answer is: you need to try the models out and see. To give you a concrete example (see here): through what I thought was a super-clever reformulation, I was able to remove 85% of the variables in the problem, and I thought that this would make it ...


18

The pitfall is to only focus on performance, will ignoring scalability, maintenance, integration and reliability. Some of these are easier to measure than others: Performance: if I give 2 constraint solvers a - for example a VRP - dataset with 100 visits, which one is better after 5 minutes. See Marco's answer on this question and my blog post on ...


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

Let's start with the easy one: Ellipsoid Method Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues. Primal Simplex Mostly studied for historical interest, but there are some cases where it might outperform dual simplex (when the basis matrix in the primal revised ...


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