Referring to optimization problems that consist only of linear constraints and a linear objective function.
1
vote
0answers
27 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
38 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.)
...
6
votes
1answer
64 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
31 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
106 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
119 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
74 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
304 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
211 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 ...
