Tagged Questions
3
votes
0answers
163 views
Bender's Decomposition for Mixed Integer Programs
Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1).
$LP_1$ has the form
...
3
votes
0answers
400 views
How to Minimize A Function Where The Number of Variables is Unknown
I have a standard linear programming problems I want to solve:
$$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
2
votes
0answers
55 views
fundamental theorem of linear inequalities
Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm?
Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...
2
votes
0answers
53 views
Determine if a polyhedron is a polytope
Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.
Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
2
votes
0answers
72 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
2
votes
0answers
60 views
How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?
If what I assume is correct,
assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
2
votes
0answers
50 views
Feasibility checking
I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution.
1- What is the best worst case running time for this decision ...
2
votes
0answers
160 views
Approximate Set Cover Problem by Rounding
Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets ...
2
votes
0answers
169 views
real-time linear programming
I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
1
vote
0answers
33 views
Prove mathematically
Q.1 Consider the dual simplex method applied to a standard form problem with linearly independent rows. Suppose we have a basis which is primal infeasible, but dual feasible, and let i be such that ...
1
vote
0answers
33 views
Linear Program Transformations
I have a Linear Program with constrains of the form:
$$a_{11}x_1+a_{12}x_2+\ldots\le 0$$
$$a_{21}x_1+a_{22}x_2+\ldots\le 0$$
$$a_{31}x_1+a_{32}x_2+\ldots\le 0$$
My problem is that if I try to ...
1
vote
0answers
13 views
Issues with solving large sparse linear equations
I have some issues solving sparse linear equations Ax = b
My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
1
vote
0answers
39 views
Showing a dual LP solves a primal LP
I originally asked this question:
Does solving the LP dual SOLVE the primal LP?
It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
0answers
46 views
Linear Programming: Modifying Coefficients of the Objective Function
Consider a final tableau with entries:
Row 1: 0,(-1/2),1,1,2,0,-1
Row 2: 1,(1/2),0,2,-1,0,-2
Row 3: 0,2,0,-1,(-1/2),1,3
Basic variable values (4,2,1)
and objective function coefficients ...
1
vote
0answers
138 views
Defining Dual problems in Linear programming optimization
I have this Primal problem:
$
Max \sum\limits_{i=1}^{50} X_iC_i \\
S.T.\\
\sum\limits_{i=1}^{50} X_iw_i\le W \\
\sum\limits_{i=1}^{50} X_iV_i\le V \\
X_i \le 1 \\
X_i \ge 0 \\
$
Now according the ...
