12 votes
Accepted

Linear programming with matrix constraints

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 ...
user avatar
  • 3,003
11 votes
Accepted

Implementation of LP with separation oracle?

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 ...
user avatar
8 votes

What's the fastest software(open source) to solve mixed integer programming problem

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 ...
user avatar
7 votes

Mathematical optimization software free/openSource

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 ...
user avatar
  • 181
6 votes

Starting at a Given Basic Feasible Solution in the Simplex Method

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, ...
user avatar
6 votes
Accepted

Linear system solution with inequality constraints - methods?

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 ...
user avatar
5 votes

How do I simultaneously minimize two different functions who have the same inputs?

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 ...
user avatar
5 votes
Accepted

0,1 binary polynomial programming

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 ...
user avatar
5 votes
Accepted

Mathematical optimization software free/openSource

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 ...
user avatar
5 votes

Can we express max constraint as a linear constraint?

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). ...
user avatar
5 votes

Is the "practical" complexity of linsolve direct solver O(n^2) ?

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 ...
user avatar
5 votes
Accepted

Checking the feasibility of a system of inequalities

You can check feasibility of a set of linear inequalities by constructing a linear programming (LP) problem with a "dummy" objective, e.g., $$ \begin{align} \max_{\{x_i\}_{i=1}^n} &\;0\\ \text {...
user avatar
  • 731
4 votes

Starting at a Given Basic Feasible Solution in the Simplex Method

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 ...
user avatar
  • 409
4 votes
Accepted

What sparse linear programming solver it is better to use?

The best performance solvers are probably Gurobi or CPLEX; last I checked, Gurobi is slightly faster, but both are competitive. These two commercial solvers are roughly ten times faster than the best ...
user avatar
4 votes

I have to solve a large binary programming task. Should I avoid branch and bound?

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 ...
user avatar
4 votes

Linear programming with matrix constraints

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}...
user avatar
4 votes

Constraints involving $\max$ in a linear program?

In order to formulate the constraints $f \le \max \{ f_1, f_2,...,f_n \}$, we create $n$ binary variables, $b_i \in \{0,1\}$, $1 \le i \le n$. Let $M$ be the bound of variable $f$, then we only need ...
user avatar
  • 161
4 votes
Accepted

Solving a problem using multiple threads using CLP

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 ...
user avatar
4 votes

difference of polytopes in $\mathbb{R}^n$

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 ...
user avatar
  • 372
4 votes
Accepted

LP and SDP nomenclature

$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 ...
user avatar
  • 408
4 votes
Accepted

Use scipy to get any vertex of polytope

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 ...
user avatar
4 votes

Can Variance be replaced by absolute value in this optimization problem

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 ...
user avatar
  • 261
4 votes

Simplex method - cycling and condition ">=" or ">" in choice of pivot row

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 ...
user avatar
4 votes

How to solve a constrained optimization problem using minFunc or minConf

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 ...
user avatar
4 votes

How to solve a constrained optimization problem using minFunc or minConf

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 ...
user avatar
4 votes
Accepted

linear programming feasiblity checking

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 ...
user avatar
4 votes

Checking the feasibility of a system of inequalities

I agree with Stelios' answer, but it could use some fleshing out. This problem is called the "Phase One" problem. First, convert your problem into "standard form". \begin{align*} \min_x 0 \\ s.t. \;\...
user avatar
  • 1,522
4 votes
Accepted

Largest hypercuboid inside a polyhedron

It turns out that the problem has quite an elegant solution. Let the hypercuboid be defined by $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ instead of using the more cumbersome $\mathbf{x_{0}}$ and $\...
user avatar
  • 562
4 votes
Accepted

What is the name for this type of constraint?

I would call the constraint "upper- and lower-bounds on the maximum element." Note that you are actually dealing with two separate constraints. Define the max element function as follows $$ \max:\...
user avatar

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