# Tag Info

## Hot answers tagged linear-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 ...

12

Overview You might want to try a variant of the Alternating Directions Method of Multipliers (ADMM), which has been found to converge surprisingly quickly for $l_1$ lasso type problems. The strategy is to formulate the problem with an augmented Lagrangian and then do gradient ascent on the dual problem. It is especially nice for this particular $l^1$ ...

11

Here's a longer answer that summarizes my earlier comments: I'm not aware of any implementations of the ellipsoid algorithm that are practically usable for solving LP's. It's easy enough to cook up an implementation of the ellipsoid method in MATLAB but if you try to solve relatively small test problems (e.g. the afiro test problem from NETLIB which has ...

8

CPLEX is commercial grade and solves very large LPs and IPs. If CPLEX didn't pan out for you, then switching to a different solver may not be the answer. Here's one SO Question on good solvers. Instead, here are three suggestions for you, rather than going for the solver speed or the specific algorithm. Focus on your formulation. How many constraints and ...

8

There is an extensive literature on numerical aspects of the implementation of the simplex method including methods for updating the factorization of the basis as well as techniques that maintain the inverse of the basis in product form. Replacing a column of the basis matrix is a "rank-one update" since it can be written in terms of adding a matrix to the ...

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

7

Is there any real free alternative to AMPL? Yes! (Sorry to contradict you, Geoff.) There is a real free alternative to AMPL. JuMP is a free and open-source modeling language built on top of Julia. It is capable of modeling large-scale linear, mixed-integer, and most recently nonlinear programming problems. SCIP support will be coming soon, along with mixed-...

6

Every book on linear optimization explains the simplex method as a two-stage algorithm: the first for finding a feasible corner as a starting point, and the second for finding the optimum. The first uses a dual problem. Take a look at D. Bertsimas and J. N. Tsitsiklis: "Introduction to linear optimization", for example. The reason one needs the two-phase ...

6

You haven't told us what set $i$ ranges over, so I'll just assume $i=1, 2, \ldots, n$. A standard trick in LP formulation of problems with absolute values is to introduce auxiliary variables and constraints with the basic idea that $\min | x |$ is equivalent to $\min t$ $t \geq x$ $t \geq -x$ Applying that idea to your problem, introduce ...

6

If your problem is in standard form (that is, with constraints $Ax = b$, $x \geq 0$), and you know a BFS, then you should know which columns of the standard form $A$ matrix to select to form a basis, from which you can set up your initial tableau by calculating reduced costs, etc. Unless you have to implement the simplex algorithm yourself, I would use a ...

6

This is a linear programming feasibility problem (since you don't have an objective function to minimize or maximize.) You can simply use an objective function of $0$ and hand this off to any reasonable LP solver. You'll either get back a solution or the bad news that the problem is infeasible.

5

Unfortunately, the vendors of linear programming software have often been unwilling to tell us about the particular tricks that they use in implementing the simplex method, so there aren't many published articles that will give you these kinds of details. Robert Bixby's 2002 paper, Solving Real-World Linear Programs: A Decade and More of Progress is a good ...

5

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 probably want to use a matrix-free method for linear programming. I don't know of any method specifically geared towards linear programming, but there exist matrix-free interior point methods for quadratic programs and for general nonlinear programs. The quadratic program case corresponds exactly to your problem, where the quadratic form coefficients are ...

5

First note that because your $x_{i}$ are binary variables you aren't really in the world of linear programming any more. Rather, this problem is a mixed integer linear programming problem (MILP). Depending on your other constraints and objective, this may be doable by simply minimizing $y$ in the objective and enforcing the constraints: $y \geq a_{i}x_{i}... 5 Is there any free alternative to AMPL? (Edit: I spoke too soon; thanks to mlubin for pointing this out.) If you don't care too much about convenience, there are open-source formats for specifying nonlinear programs (the SIF and NOP formats), but then you have to translate that format into a form your solver can actually use. Since the CUTEr/CUTEst test sets ... 5 The problem posed is a multiobjective optimization problem, and the usual notion of optimality for these types of problems is Pareto optimality. Scalarization (as proposed in the comments by ChristianClason, TheNobleSunfish, Paul, and DougLipinski) is one way to solve the problem. This approach leverages the large body of theory and algorithms for single ... 5 If the$s_{i}$are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred Glover has a sequence of papers to that effect in the mid-to-late 1970s, and subsequent work has built upon it. For example: Fred Glover, "Improved Linear ... 5 Your matrices are far too small to see the asymptoptic$O(n^3)$running time behavior of the LU factorization used by linsolve. For very small matrices the overhead of computations surrounding the LU factorization will make it difficult to see the$O(n^3)$growth. Furthermore, MATLAB will typically be making use of parallel routines for computing the LU ... 4 The big solvers like CPLEX / GUROBI are usually quite good, especially concerning linear programs and not integer linear programs, however they have natural difficulties beyond a certain problem size. Tackling the problem with c++ alone will probably not help, since I doubt that it is to easy to beat CPLEX implementations. CLPEX itself provides a c++ api, ... 4 Can you afford those SVDs Geoffrey Irving mentioned? If you can, I would consider an iteratively reweighted least squares (IRLS) approach. This approach would solve problems of the form $$\begin{array}{ll}\text{minimize}&\sum_{ij} W_{ij}J_{ij}^2\\\text{subject to}&MJ+BY=X\end{array}$$where$W$is a weight matrix. The iterations begin with$W^{(0)}$... 4 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. 4 Solved it. Actually, Barrodale and Roberts solved it and I just did not read carefully. In my question I left it to the reader to understand that the variables Barrodale and Roberts labeled$u_i$stand for the positive residuals the$i$-th datapoint in relation to the current fit. If the residual is negative,$u_i=0$and$v_i$takes the corresponding value.... 4 Nonlinear equality constraints involving continuous variables are not convex. Here is a counterexample for your problem: Suppose without loss of generality$x_{1}x_{2} - x_{3}x_{4} = 0$is your nonlinear equality constraint, and let$S = \{(x_1, x_2, x_3, x_4, \ldots, x_{n}): x_1 x_2 - x_3 x_4 = 0\}$be its associated feasible set. Then$(6, 1, 3, 2, 0, \...

4

Can you simply modify your problem from $$Ay\geq b$$ to $$Ax \geq b−Ay_0,$$ where the new unknown is $x=(y−y_0)$ and $y_0$ is your known specific BFS? Then you can use $x=0$ to start, and recover the solution of the initial problem by means of $y = x+y_0$.

4

10,000 variables is a lot for an integer programming problem, but everything depends on the details of your particular problem. With the information provided, there's really no way for us to tell you in advance how easy or hard it might be to solve this problem. My advice would be to try CPLEX's integer programming solver on this problem with its default ...

4

By Clp, I assume that you're referring to the linear programming code that is part of the COIN-OR project: http://www.coin-or.org/Clp/ Clp's primal and dual simplex codes aren't multithreaded so even if you call Clp from within a multithreaded program in Julia, each LP will be solved by a single thread. It is possible to use the primal-dual interior point ...

4

That heavily depends on the representation. If you're given $P_1$ and $P_2$ as systems of linear inequalities (or, dually, as the convex hull of a finite set of points) with finite precision, you can reduce each linear system (or finite point set) to an irredundant system of linear inequalities by solving linearly many linear programs. Then scale each ...

4

$x$ is primal variable, $y$ is dual variable ($y$ is usually not referred to as Lagrange multiplier unless you form Lagrangian explicitly). Others are usually referred by symbol directly rather than name, the linear coefficient ($c$), linear constraint matrix ($A$), right-hand-side of linear constraint ($b$). If you have quadratic term $x^\top Hx$, then \$...

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