Referring to optimization problems that consist only of linear constraints and a linear objective function.
0
votes
0answers
23 views
Cplex C++ Interface: Repeated calls of setQuadCoef are slow. Is there an alternative?
I noticed that repeated calls of the member function setQuadCoef of the class IloObjective can be prohibitively slow.
The Cplex ...
2
votes
1answer
36 views
Cplex C++ Interface: How to add many constraints quickly?
I noticed that adding constraints to an IloModel one by one can be prohibitively slow. (I am referring to the construction of the model, not the optimization.)
...
2
votes
3answers
106 views
How to implement this trigonometric polynomial maximum finding semidefinite program
Hi All, I posted this on the math.se site, but this may be a better location.
I need a method of finding the maximum of a real valued trigonometric polynomial where I can trade accuracy for speed. ...
6
votes
1answer
54 views
Least absolute deviations solving using the Barrodale-Roberts-algorithm: Premature termination?
Please excuse the longish question, it just needs some explanation to get down to the actual problem. Those familiar with the mentioned algorithms probably could jump directly to the first simplex ...
0
votes
0answers
30 views
Robust Counterpart of an uncertain LP
Consider the following robust optimization problem:
min c'x
s.t.: $Ax\geq b \;\;\forall (A,b)\in \mathcal{U}$.
Why can the robust counterpart of the problem be written in this form?
$min_x{\{ ...
2
votes
1answer
71 views
polynomial time solvability
Consider the following optimization problem:
$Min \qquad C^TX$
S.t.: $\qquad AX=0;$
$x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$
$X=(x_1,x_2,...x_n)$
and $\quad x_j\geq 0\;\; ...
0
votes
1answer
105 views
Semidefinite programming
I have a convex optimization problem that is essentially a linear objective function over some linear constraints and also a semidefinite matrix in the following form: $
M=
\left[ ...
4
votes
0answers
118 views
Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:
The element 1 is in position 1, and element N must be ...
0
votes
0answers
14 views
linear programming- dual of maximum flow [duplicate]
Possible Duplicate:
Dual max flow- linear programming
I have a hard time understanding dual of max flow problems. Can experienced thinkers solve the problems below and possibly give ...
0
votes
0answers
45 views
Lagrangian Duality [duplicate]
Possible Duplicate:
Linear programming boundedness
Consider the following LP:
$\max$ $\sum_{i=1}^N b_i \pi_i$
s.t. $\;\;$ $\pi_i-\pi_j\leq 1 $ $\quad$ for each $(i,j) \in \tilde{A}$
...
6
votes
2answers
72 views
Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?
I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise.
The other variables in the linear ...
10
votes
2answers
296 views
Absolute Value in Linear Constraints
I have the following optimization problem where I have absolute value in my constraints:
Let $\mathbf{x} \in \mathbb{R}^n$ and $\mathbf{f}_0, \mathbf{f}_1, \ldots, \mathbf{f}_m$ be column vectors of ...
5
votes
1answer
92 views
Linear Programming with constraints of the form $Cx \nless d$ where $C\in R^{m\times n}$
I have an optimization problem that has a linear objective function. The constraints are of the form: $(Ax \leq b) \wedge (Cx \nless d)$.
In other words, I have:
\begin{align}
\min &f^T x
...
3
votes
1answer
210 views
parametric linear programming
I have a linear programming problem
min $c^T x$
$Ax\leq b$
However, in my problem, $A$ contains also some variables $y$, e.g.
$$A = \begin{pmatrix} y_1 & 4 \\ 3 & y_2 \end{pmatrix}$$
I ...
1
vote
1answer
61 views
Fast Algorithms for solving sparse LP problems
For solving a very sparse LP: {min $cx$: s.t.: $A_{m \times n}x=b$ , $x\geq 0$}, which one of the following algorithms is faster?
Logarithmic barrier method
Other variants of the interior point
...
2
votes
1answer
53 views
Rational LP to integer LP
In the worst case complexity analysis of all the polynomial algorithms in linear programming such as ellipsoid method and interior point method, there is an assumption that the input data must be ...
0
votes
0answers
35 views
Feasibility of min cost flow problem
Consider the min-cost flow problem. How can the feasibility of this problem be checked without solving the LP from scratch?
0
votes
0answers
99 views
boundedness of a linear programming [closed]
Assume we are given a linear programming problem. It is well-known that a linear programming problem is unbounded iff there exists an EXTREME direction $d$ such that cd>0 (consider maximization case). ...
0
votes
1answer
93 views
Min-cost flow problem
Consider a min cost flow problem in a directed graph $G=(V, E)$ as follows:
(*) Min $\sum {c_{ij}f_{ij}}$
s.t.: $\sum_{j\in out(i)}{f_{ij}} - \sum_{j\in in(i)}{f_{ji}} =b(i)$ for each ...
3
votes
1answer
70 views
Linear programming boundedness
Assume the optimal value of a primal problem is bounded. Is the following statement true?
If the primal problem is bounded, then its dual problem is bounded as well.
0
votes
0answers
112 views
Finding a permutation that makes a matrix lower triangular
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
1
vote
2answers
80 views
LP feasibility checking
I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?
1
vote
1answer
152 views
Why isn't every linear program combinatorial?
A linear program (LP)
\begin{alignat}{1}
& \min_{x} {c}^{T}x, \\
\mathrm{s.t.} & \quad Ax = b, \\
& x \geq 0.
\end{alignat}
is called combinatorial if the size of entries of matrix $A ...
1
vote
0answers
57 views
Proportional equality constraints
Consider a node $s$. Let's assume that there are three outgoing arcs from node $s$ namely $(s,i)$,$(s,j)$ and $(s,k)$. Corresponding to each of these arcs, there is a flow proportion value $t_{sj}\in ...
2
votes
2answers
338 views
Exploring feasible points in a linearly defined space
What is the quickest way to find a point inside a linear feasible space? (Defined by the intersection of several hyperplanes and halfspaces). I want to be able to choose an initial point in the ...
0
votes
0answers
76 views
Is there a Mathematical Optimization API? [closed]
I mean something like:
I have to solve a Knapsack problem in my application
I describe an XML with all variables, objectives and more
I Upload this XML to a remote server (via a restful API)
I get ...
5
votes
3answers
125 views
Is there an in practice limit on the number of constraints on a linear programming problem?
I am new to linear programming and have formulated a linear program (LP) with order of $10^{13}$ variables and $10^{13}$ constraints, although the constraint matrix is extremely sparse.
I wanted to ...
4
votes
1answer
88 views
Should I include integral constraints in a integer linear program with a totally unimodular constaint matrix?
I have formulated an integer linear program (ILP). The constraint matrix for the ILP is totally unimodular.
Should I solve it as an LP without the integral constraints, or should I keep the integral ...
2
votes
3answers
103 views
How to add back integral constraints to linear program solution
I am implementing a machine learning algorithm for which I need to solve an integer linear program. To get the solution in polynomial time, the authors of the algorithm have dropped the integral ...
2
votes
1answer
168 views
Solving PSD matrix in Newton's method
I have functions defined as follows:
$f1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f2(A) = \sum\|x_k-x_l\|^2_A$ where A is PSD matrix, x are number vectors.
Task is to minimize ...
9
votes
1answer
212 views
Decomposition methods for solving large optimization problems
I was wondering if anybody had any suggestions for texts or survey articles on decomposition methods (e.g. primal, dual, Dantzig–Wolfe decompositions) for solving large mathematical programming ...
6
votes
0answers
80 views
Potential Reduction and Primal Path following methods
In both the potential reduction and primal path following interior point methods for linear programming, a barrier function is constructed which contains the terms $-\sum \log x_j$ where $x_j$ are the ...
5
votes
0answers
101 views
Fast algorithms to solve Markov Decision Processes
In my master thesis I used an Algorithm called Approximative Dynamic Programming [1] to solve equations of the form
$$
...
9
votes
5answers
981 views
Constraints involving $\max$ in a linear program?
Suppose
$$\begin{align*}
\min A &\mathrm{vec}(U) \\
&\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n
\end{align*}$$
where $U$ is a symmetric $n\times ...
0
votes
1answer
126 views
LP infeasibility
Consider the following original LP: $\mathit{min}$ c'$x$ s.t: $Ax=0 \wedge 0\le x\le 1$ . This is my original LP which has to be solved.
Now, using some reductions, I reduced the original LP to the ...
5
votes
1answer
100 views
Using an approximation algorithm to adapt parameter values of a given algorithm
Problem:
I have an incremental online clustering algorithm which need 4 parameters that should be specified by the user before execution. The algorithm will gives "good results" if "a good parameter ...
5
votes
4answers
192 views
Approximately “solving” a linear system of equations without a feasible solution
A linear system of equations has the form $Ax = b$, where a matrix $A$ and a
vector $b$ are given, and I wish to find a solution vector $x$.
Suppose that the system $Ax = b$ has no feasible solution. ...
7
votes
4answers
710 views
Linear programming feasibility problem with strict positivity constraints
There is a system of linear constraints ${\bf Ax} \leq {\bf b}$ . I wish to find a strictly
positive vector ${\bf x} > 0$ that satisfies these constraints. That means, $x_i > 0$ is
required for ...
6
votes
3answers
986 views
What are the advantages/disadvantages of interior point methods over simplex method for linear optimization?
As I understand it, since a solution to a linear program always occurs at a vertex of its polyhedral feasible set (if a solution exists and the optimal objective function value is bounded from below, ...
7
votes
1answer
363 views
Efficient solution of mixed integer linear programs
Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation ...
