Computational Science Stack Exchange
Computational Science Stack Exchange

Questions tagged [linear-programming]

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

140 questions
8
votes
4 answers

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 know if an LP of this scale is tractable or not?
stressed_geek
  • 319
  • 1
  • 2
  • 5
8
votes
1 answer

Implementation of LP with separation oracle?

I'm looking for an implementation of the ellipsoid algorithm for linear programming since the application I have in mind has the constraints represented as a separation oracle. Is such an implementation available anywhere? If there isn't, is there…
G. Bach
  • 183
  • 6
8
votes
0 answers

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 variables. This is to keep the variables from…
Opt
  • 341
  • 1
  • 5
6
votes
2 answers

In linear programming, is there a way to constrain two variables to not have opposite sign

Say I have two sets of variables $x$ and $y$ of equal size. $x$'s have a lower bound $x_{min}<0$, and $y$'s have a lower bound $0$. Is there a linear way to constrain that $x_i\geq0$ if the solution has $y_i>0$, and $x_i\geq x_{min,i}$ if the…
jf328
  • 482
  • 2
  • 8
4
votes
1 answer

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 want to find a value of $y$ such that the solution $x$ of the…
maomoa
  • 41
  • 1
4
votes
1 answer

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.
Star
  • 575
  • 4
  • 13
3
votes
0 answers

Solving multiple linear programs with same constraints but different objective

I have ~30 non-negative variables and 24 equations and I want to find out the upper and lower bound for each variable. Feasible solutions are guaranteed. So for each variable, I solve two LP problem, one for min and one for…
jf328
  • 482
  • 2
  • 8
3
votes
1 answer

Can we express max constraint as a linear constraint?

I have a mathematical program with a constraint involving a maximum function. More specifically, the constraint is: $y = \max\{a_i x_i:1 \leq i \leq n\}$ where $a_i$ are constants and $x_i$ are binary variables. Can we express this constraint as a…
Shubhadip Mitra
  • 31
  • 2
2
votes
1 answer

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 applications, nor have I found an attempt to compare the…
shuhalo
  • 3,660
  • 1
  • 20
  • 31
2
votes
1 answer

How can we model time progress in linear programming?

I am trying to solve a scheduling problem with linear programming. I have N disks that each have a capacity of constant C. At each time interval t_i, a set of write requests with different sizes arrive that we need to store their data on the disks.…
Amin mosayyebzadeh
  • 31
  • 3
2
votes
1 answer

Is it more efficient to capture many constraints in one constraint?

I have a number of variables that need to be set to 0. They are positive real numbers so the way I see it I can do this by setting each one to 0 by separate constraints, or I can set their sum to zero. Would that help with the efficiency? Im working…
Tafel Poot
  • 29
  • 1
1
vote
2 answers

implied equalities and relative interior

What is the best method to find for a linear system of inequalities $Ax\ge b$ with dense $A$ of moderate dimension the affine subspace spanned by the feasible points (i.e., the implied equalities $(Ax)i=b_i$) and a relatively interior feasible point…
Arnold Neumaier
  • 11,318
  • 20
  • 47
0
votes
2 answers

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 recommended to make matrix square. For example in…
Nurlan
  • 373
  • 2
  • 12
0
votes
1 answer

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 $i\in V$ $f_{ij} \geq 0$ $in(i)$ and $out(i)$ are…
Star
  • 575
  • 4
  • 13
0
votes
1 answer

How to perform linear programming sensitivity analysis in MATLAB?

I would like to perform post-optimal analysis using Matlab linprog. But it does not provide any information about that. So required a way to get the info about optimal basis, basic and non-basic variables via the solution of interior-point or…
Parikshit
  • 1
1
2