Referring to optimization problems that consist only of linear constraints and a linear objective function.

learn more… | top users | synonyms

2
votes
1answer
54 views

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

I have to minimize a linear function with respect to variables u which take values [0,1] The number of variables can exceed 10,000 There are thousands of linear inequality constraints I need a ...
0
votes
1answer
43 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
1
vote
2answers
83 views

What sparse linear programming solver it is better to use?

I have the following LP problem: $$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; s.t. \;\;C x \geq 0, \;\; x_{i}^{0} - \varepsilon ...
0
votes
0answers
24 views

Linear complementarity problems with inequality (box) constraints

I can find many references and matlab or c++ codes for solving each problem separately. But it is very hard to find one that actually solve both simultaneously on the internet. I am quite sure that ...
4
votes
2answers
128 views

Starting at a Given Basic Feasible Solution in the Simplex Method

I have a Simplex problem $ A y \ge b $, where some of the elements of $b$ are positive and some are negative, and thus setting $y = 0$ does not give a basic feasible solution (BFS). By previous work, ...
7
votes
4answers
283 views

Linear programming with matrix constraints

I have an optimization problem that looks like the following $$ \begin{array}{rl} \min_{J,B} & \sum_{ij} |J_{ij}|\\ \textrm{s.t.} & MJ + BY =X \end{array} $$ Here, my variables are matrices ...
4
votes
3answers
126 views

Which algorithm to use for solving an LP with a very large number of variables?

I'm a newbie at modelling and optimization of LPs. My research problem concerns assigning tasks/jobs to virtual machines in a data centre depending on the least energy cost incurred. As you can ...
0
votes
1answer
56 views

Modeling a quadratic constraint with a linear expression

In a problem I am trying to model with a MIP program, the following scenario occurs: I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. ...
4
votes
3answers
252 views

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

I have a mixed integer programming problem. And I am current using GLPK as my solver. But I found that GLPK is good for Linear Programming problem, but for Mixed Integer programming, it requires much ...
2
votes
1answer
66 views

k-splittable flow problem

The maximum k-splittable s-t flow problem(MkSF) that aims to find a maximum k-splittable flow between a given source and sink node is NP-hard. We do not require the paths to be disjoint, not even ...
4
votes
1answer
920 views

Constrained optimization with max and absolute values in objective function

I would like to find the optimal set $ \{ x_i \} $ given $ L $ and $ \{ a_i \} $ that minimizes the problem below. My first thought was to use linear programming. Is there a transformation that ...
2
votes
1answer
59 views

Which variants of the simplex method are actually used in applications

There are several variants of the simplex method known, which differ by the choice of entering and leaving variables. But neither have I found a reference, which variants are used in which ...
2
votes
1answer
177 views

Update QR decomposition when one column is exchanged

I have got an input series of matrices $A_1, A_2, A_3, \dots $ and the difference between $A_i$ and $A_{i+1}$ is the replacement of one single column. Before i get to know $A_{i+1}$, I have to ...
2
votes
1answer
116 views

Sensitivity analysis of linear program with coin-or clp

I have written a short example to run the simplex algorithm with coin-or Clp, something quite simple like this: ...
-2
votes
3answers
219 views

how to make linear program simplex method use user provided feasible initial point

In some linear program that is hard to find an initial feasible point, simplex method will fail in its phase one algorithm. But we can find such a feasible point through other method such as genetic ...
5
votes
3answers
584 views

How to start the Simplex method from a feasible internal point?

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...
0
votes
2answers
793 views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
1
vote
2answers
145 views

Solving a “generalized” linear programming problem

I need to solve the follwing constrained optimization problem. Is there any MATLAB toolbox which can solve this. minimize $A_1 x$ subject to $A_2 x = 0$ $A_1$ is an $m\times n$ matrix where $m ...
1
vote
0answers
76 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
256 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.) ...
8
votes
1answer
312 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
1answer
125 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
2answers
108 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
115 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[ ...
5
votes
0answers
139 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
46 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}$ ...
7
votes
2answers
105 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 ...
11
votes
2answers
553 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
112 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
274 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
80 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
58 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
1answer
190 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
77 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
174 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
172 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
168 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
68 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
391 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 ...
5
votes
3answers
203 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
134 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
158 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
179 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 ...
10
votes
2answers
339 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
103 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 ...
6
votes
0answers
115 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 $$ ...
11
votes
5answers
2k 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
127 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
108 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 ...
6
votes
4answers
218 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. ...