# Tag Info

14

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

9

$10^{13}$ is beyond tractable on today's largest supercomputers due mostly to memory limits. The largest problems I've seen practically solved have had on the order of $10^5$ rows and columns, but the most important factor tends to be the number of nonzeros, where we are just crossing into solving problems with $10^6$ nonzeros. See Mittelman's parallel ...

9

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

9

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

Checking feasibility of an LP and solving an LP are essentially equivalent problems, as one can be transformed into the other by standard methods changing the complexity by a constant factor only. The best-known algorithms are the simplex method and interior point methods. For both, there are numerous variations. Which of the two approaches is most useful ...

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

6

A huge number of inequality constraints is generally tractable by constraint generation techniques, processing at each time only a limited number of constraints, and adding constraints violated at the current solution to the constraint set (while deleting strongly satisfied ones). But in the cases I have seen, this requires that the number of non-slack ...

6

The constraint $Cx \nless d$ is can be expressed as a mixed-integer program under certain conditions. \begin{eqnarray} C_i x - M_i y_i &\ge& d_i \hspace{0.3 in} \forall i \in I \\ \sum_{i \in I} y_i &\le& m-1 \\ y_i &\in& \{ 0, 1 \} \hspace{0.2 in} \forall i \in I \end{eqnarray} Where $I = \{1, \ldots m\}$, $M_i$ is a constant ...

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

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

6

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

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 easiest way is to add $m$ binary values $s_i \in {0,1}$, and solve \begin{align} \min &\mathbf{f}_0^T \mathbf{x} \notag \\ \text{s.t.} & 0 \le (2s_i-1) \mathbf{f}^T_i \mathbf{x} \le (2s_{i+1}-1) \mathbf{f}^T_{i+1} \mathbf{x} & \forall i\end{align} I think that either (1) nothing substantially faster exists or (2) there is a special trick ...

5

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use ...

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

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

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

As (almost) always in parametric programming, you have to encode optimality of $x$, for a given $y$, using optimality conditions. $c + A(y)^T\lambda=0$ (stationarity) $\lambda^T(b-A(y)x)=0$ (complementarity) $\lambda\geq 0,b-A(y)x\geq 0$ (dual and primal feasibility) To solve your problem, you solve a feasibility problem with the KKT conditions above, ...

4

This is certainly true for any individual problem, but this sort of statement is typically made about a family of LPs. In that case, the dimensions of the matrix and the entries of the matrix are typically expressed in terms of other parameters $\theta = (\theta_1, \theta_2, \dotsc, \theta_k)$ for some $k \geq 1$ - i.e., we have $n(\theta)$ and $m(\theta)$. ...

4

Finding a single feasible point is traditionally done by phase 1 of the simplex algorithm. http://en.wikipedia.org/wiki/Simplex_algorithm#Finding_an_initial_canonical_tableau This means that you can do it by calling any routine for linear programming, just by putting the objective function to zero. Covering the feasible domain by balls of fixed radius $r$...

4

It won't matter to any worthwhile mixed-integer linear programming (MILP, also known as MIP) solver if you keep or omit the integral constraints, as long as your constraint matrix is truly totally unimodular. To be on the safe side, keep the integral constraints and call your MILP solver. Any solver utilizing a branch-and-bound or branch-and-cut framework ...

4

No. The primal LP min $x+y$ subject to $x-y\ge 0$ has no bounded objective. Instead, one must assume boundedness of the primal and dual problem as a hypothesis, and then gets the result that both problems are solvable and their values agree.

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

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