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

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

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


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

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

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

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

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

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

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

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

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

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

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


4

If you use a 0 objective function, then the solver should stop as soon as it encounters a feasible solution (because that solution will be optimal.) If the solver is using a 2-phase primal simplex method it will stop immediately after the first phase and the solution will be a vertex of the polyhedron. In practice, LP feasibility problems like this ...


4

Without knowing much about your question it is hard to answer more specifically. So first and foremost - no. These are not equivalent. Minimizing variangce will generally make you converge to some kind of sample mean, whereas minimizing absolute deviation would (generally) make you find some kind of sample median. A generally favourable property of sample ...


4

The short answer to your question is that "nonnegative" is correct. 0 ratios do occur and it is sometimes necessary to perform degenerate pivots in order to ultimately reach a solution which will pass the simplex method's optimality test. However, you need to carefully deal with near zero values of $B_{r}$ and $A_{rc}$ or else round-off can easily lead to ...


4

Not a direct answer to your title question, but I think you are better off attacking this problem from the semidefinite domain instead. Trivial approach is to linearize the objective at some initial guess, solve the linearized problem, perform a line-search along the computed direction, and repeat until the objective doesn't improve. The code below does this ...


4

Adding another answer, as I just realized that the problem is easily solved as a linear SDP. Let $Q=S^TS$ and you have the objective $\mathrm{trace}~Q + \mathrm{trace}~Q^{-2}$. Introduce an upper bound $X\succeq Q^{-1}$ and minimize $\mathrm{trace}~Q + \mathrm{trace}~X^{2}$. At optimality you will have $X= Q^{-1}$. The constraints $X\succeq Q^{-1}$ and $Q\...


4

The short answer to your question is: kind of. There are methods called "preprocessing" or "presolve", that will take a problem with constraints $b_{l} \leq Ax \leq b_{u}$ and $l \leq x \leq u$ as input. Using tests that are usually linear time, you can check sufficient conditions for infeasibility (but not necessary conditions). These methods are commonly ...


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