17

Based on personal experience, I'd say that simplex methods are marginally easier to understand how to implement than interior point methods, based on personal experience from implementing both primal simplex and a basic interior point method in MATLAB as part of taking a linear programming class. The main obstacles in primal simplex are making sure that you ...


15

Although mixed-integer linear programming (MILP) is indeed NP-complete, there are solvable (nontrivial) instances of mixed-integer linear programming. NP-complete means that mixed integer linear programming is: a) solvable in polynomial time with a nondeterministic Turing machine (the NP part) b) polynomial time reducible to 3-SAT (the complete part; for ...


15

You can circumvent the problem of choosing a small $\epsilon>0$ by being a bit more ambitious: Try to find $\mathbf{x}$ such that $\mathbf{Ax}\leq \mathbf{b}$ and that the smallest entry in $\mathbf{x}$ is largest possible. To that end, introduce a new variable $$\mathbf{y} = \begin{bmatrix} \mathbf{x}\\ \epsilon\end{bmatrix}\in\mathbb{R}^{n+1}$$ (if $\...


14

Edit: Let's try this explanation again, this time when I'm more awake. There are three big issues with the formulation (in order of severity): There's no obvious reformulation of the problem that is obviously smooth, convex, or linear. It's nonsmooth. It's not necessarily convex. No obvious smooth/convex/linear reformulation First off, there's no ...


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

I assume what you're looking for is some $x$ such that $$\big\|Ax-b\big\|_2$$ is minimal. If this is the case, then what you need is a pseudoinverse of $A$ or the singular value decomposition of $A$ such that $U \Sigma V^\mathsf{T} = A$. The least-squares solution is then given by $$x = V\Sigma^+U^\mathsf{T}b$$ where $\Sigma^+$ is the diagonal matrix $\Sigma$...


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


5

For an LP feasibility problem, I wouldn't use standard simplex. Standard primal (or dual) simplex algorithms will only visit the vertices of the feasible set of the primal (or dual) problems. Let the feasible set of the problem you actually want to solve be $F = \{\mathbf{x}: \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} > \mathbf{0}\}$, and suppose instead ...


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

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

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

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

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

Feasibility problems are a slightly trickier game than general linear problems, which you have noted. If you are solving approximately (by using a floating-point representation of the system of equations and constraints), it is legitimate to require $x_i >= \epsilon$, where $\epsilon$ is some very small numerical value, big enough to assure that $x_i$ ...


4

There are many different types of approximations (or "surrogate models") you could try. Some that come to mind are Kriging, MARS, and Radial Basis Functions. These types of surrogate models (as opposed to polynomial regression) can accommodate a wide range of functional relationships, but you might need to experiment a bit to find which works best for your ...


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