Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

1,443 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
1answer
601 views

Solving 2 × 2 Matrix Games Using Geometric Methods

I think my text book may be wrong. I am trying to learn how to solve matrix games using a geometric method. So I am given the matrix $$\begin{pmatrix}-2 & 4 \\1 & -3\end{pmatrix}$$ So the ...
3
votes
0answers
152 views

Fourier Motzkin Elimination and totally unimodularity

Suppose $A\in \mathbb R^{m\times n}$ and $b\in \mathbb R^m$, and $A$ is totally unimodular (TUM). For the system $$Ax\leq b,$$ suppose I use Fourier-Motzkin elimination to eliminate first $k$ ...
3
votes
0answers
1k views

Geometric interpretation of linear programming dual

Is there a geometric interpretation of the linear programming dual in terms of the primal? I feel like without some sort of intuition of it, I don't truly understand it.
3
votes
0answers
551 views

How to reduce the number of (overlapping) constraints in a linear program?

I am trying to solve a linear program with more than 7 million constraints which could not be solved on my computer (In total around 5000 variables). In the constraints there is a overlap between them....
3
votes
1answer
400 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence $...
3
votes
0answers
1k views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in V^{-}(...
3
votes
0answers
370 views

Warm start of simplex algorithm after update of constraint matrix

Assume we found an optimal solution $\mathbf{x}_1$ of the linear program \begin{gather} \max \mathbf{n}^T\mathbf{x}\mbox{ s.t. }A\mathbf{x} \leq \mathbf{b}\tag{1} \end{gather} using the simplex ...
3
votes
0answers
503 views

What subjects properly belong in operations research as their “owning” discipline?

Warning: This is a soft question, hence I would make it a wiki-community post if I could. Operations Research involves a broad swath of disciplines, ranging from probability and statistics/stochastic ...
3
votes
0answers
195 views

Converting a max-min problem to a max problem with a constraint

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ...
3
votes
0answers
737 views

A basic question related with the solutions of linear programming problems

I have to select one option from the problem statement given below. Which of the following statements is true in case of linear programming. $1$: An optimal solution exists at extreme points of a ...
3
votes
1answer
1k views

Find all optimal solutions by Simplex

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the ...
3
votes
0answers
1k views

Nested optimization problems solving using mixed integer linear programming

Let us have two vectors of decision variables, $\mathbf{x}$ and $\mathbf{y}$, two linear objective functions, $F \left( \mathbf{x}, \mathbf{y} \right)$ and $f \left( \mathbf{x} \right)$, and two sets ...
3
votes
0answers
93 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
3
votes
1answer
135 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in A,\,\sup\...
3
votes
1answer
763 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
3
votes
1answer
165 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
3
votes
1answer
461 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
3
votes
0answers
572 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
3
votes
0answers
81 views

Convexity in oriented matroid theory: proof on closure operator?

I would like to try to solve the following problems. Problem from the Oriented Matroids book by Bjorner, Las Vergnas, Sturmfels, White, and Ziegler. It is problem 3.9 on page 152. Attempt ...
3
votes
1answer
79 views

On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align} \begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; \sum_{i=1}^{N}b_{...
3
votes
1answer
294 views

Rewrite constrained optimization objective

I wanted to ask, under which conditions can one rewrite the optimization objective $\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$ as $\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$ I have particular interest ...
3
votes
0answers
76 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: $$x_{k+1}=Ax_{k}+b....
3
votes
2answers
2k views

Removing redundant linear constraints using Gaussian elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
3
votes
0answers
128 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
3
votes
0answers
149 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. What is the best worst case running time for this decision ...
3
votes
1answer
285 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 $S$...
2
votes
0answers
31 views

Theta-Ratio of a Simplex Method for a degenerate solution, are they always equal?

Are the $\theta$-ratios of two degenerate solutions always equal? So as to say: If we know two unique points yield the same objective value, must their $\theta$-ratios always be equal? For two ...
2
votes
0answers
24 views

In a Linear Programming Problem, how is Degeneracy affected by the number of variables and constraints?

In an LPP, with m constraints and n variables. How does the number of constraints and variables affect the degeneracy of the system?
2
votes
0answers
34 views

Chebyshev approximation and linear programming

I'm trying to do the problem below and I cannot understand what (ii), (iv) and (v) are asking for. From my understanding, Chebyshev approximation is used to transform a norm approximation ...
2
votes
0answers
46 views

Linearize if-then constraints

For continuous variables $x$ and $y$, the constraints are: ...
2
votes
0answers
239 views

Prove that a convex polytope has finitely many extreme points.

$a)$ Prove that a convex polytope has finitely many extreme points. $b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope. Hint : what are the ...
2
votes
0answers
42 views

continuity of lagrangian

Let $X,Y$ be normed vector spaces. Let $f$ be a linear continuous functional and $G:X\to Y$ is linear. By Kuhn-Tucker theorem, if $x_0$ minimize $f(x)$ subject to $G(x)\le 0$, then we can find $y^*\in ...
2
votes
0answers
61 views

What's the difference between GLPP and LPP

$a)$ Express the following optimization problem as a linear programming problem(LPP): $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$ Hint: you will need to express the ...
2
votes
0answers
55 views

Linear Program such that Simplex (w/ any pivot rule) takes exponential time?

I had this exam question last semester, and it's still bothering me: For every natural number $n$, you want an LP (not necessarily with $n$ inequalities) such that simplex cannot solve it in ...
2
votes
0answers
26 views

Structure of an Optimal Solution to a Fractional Packing Problem

Packing LP We have the following optimization problem: $$ \max_{x_{ij}} x_{ij} c_{ij}$$ s.t. $$(i)\forall j\mbox{ }\sum_{i} x_{ij} \leq \beta_j$$ $$(ii)\forall i\mbox{ }\sum_{j} x_{ij} D_{ij} \leq 1$...
2
votes
0answers
23 views

Weird subspace/equality-constrained LP problem/variant of change-making problem

Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve $$\sum_{i=1}^n c_i\leq\delta$$ $$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$ where $0\...
2
votes
1answer
57 views

Linearize a constraint

I have intermediate knowledge of optimization and mathematical modeling I have this constraint. I know how to model it with integers (which leads to a mixed-integer linear program). However,I was ...
2
votes
1answer
32 views

How can I adjust the coefficients in the constraints of a Linear Programming problem with no objective function until I get a solution?

I have a system of linear equations that I need a solution for that is strictly positive. I have 4 solutions and 4 unknowns, and the solution I obtain for my current system involves negative numbers. ...
2
votes
0answers
32 views

Inverting Linear System of Inequalities

I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities: $$m\leq m' \leq p+m$$ $$m \leq m'-z' \leq p+m$$ $$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$ (The last one is an equality)....
2
votes
1answer
72 views

Given a convex polytope, is the Chebyshev center unique?

Consider a convex polytope over n-dimensions defined by m linear inequalities. Is the Chebyshev Center (Chebyshev Center) unique? Currently, I am getting different coordinates for the center in ...
2
votes
0answers
71 views

Solving Linear Programming Via Big M method

$$\text{Max } x_1 +3x_2$$ $$\text{s.t } 3x_1+x_2\leq 3$$ $$x_1-x_2\geq 2$$ $$x_1,..,x_2\geq 0$$ So we first transform to the standard form: $$\text{Min } -x_1 -3x_2$$ $$\text{s.t } 3x_1+...
2
votes
0answers
66 views

Can strong duality for linear programming be viewed intuitively?

Is there a somewhat intuitive way of understanding strong duality in linear programming? I do understand weak duality quite well since it pretty much follows from how the dual problem is defined but I ...
2
votes
1answer
27 views

simplex algorithm help for continuing in case of $\lambda \equiv 0$

Is it possible that while the simplex algorithm is working, we get a lambda $$ (Ax < b, \max c^T x )$$ $$ \lambda_B = c^T A^{-1}_B $$ with only zeros in it ? if so what does it would represent/ ...
2
votes
0answers
40 views

Warm start a simplex algorithm using a feasible solution

I've been searching a lot for relevant answers to my question. However, I was unable to find a problem formulation with satisfactory answers that would help for my problem. In a nutshell, I would ...
2
votes
1answer
53 views

how do we know from a degenerate simplex tableau of an LP problem if the current basic feasible solution is optimal?

(simplex method) In degenerate cases, the current basic feasible solution with positive reduced cost coefficient can also be an optimal solution (in non-degenerate cases, the optimal solution is ...
2
votes
0answers
80 views

Q: Literature for Vehicle Routing Problem with different Fleets?

I'm trying to investigate the impact of different fleet types in the vehicle routing problem. To be precise, I'm trying to check whether a fleet of small vehicles is more efficient that a fleet of ...
2
votes
1answer
35 views

Knowing that a feasible solution exists and has a finite optimal solution

I have the following linear programming problem: constraints: $x_1,x_2,x_3\geq200$ $0.45x_1+0.41x_2+0.5x_3 \leq 960$ $x_1+x_2+x_3 \leq 2000$ $ x_2+x_3 \leq x_1$ objective functions: max $0.35 ...
2
votes
0answers
36 views

Multiple Sensor Pointing Optimization: Formulation and is MILP the correct approach

SourceDataFile So i am attempting to optimize the following pointing problem. I have a set of sensors (cameras) and a set of targets. Each camera can be oriented directly at one one target, but based ...
2
votes
0answers
37 views

Work the least possible without ever seeing your coworkers, or minimize the sum of two coprime numbers such that their product is at least $n$

The solution to the associated continuous problem: $$ \min_{(x,y) \in S} x+y $$ where $$ S=\left\lbrace (x,y)\vert n \leq xy\right\rbrace $$ Is $x=y=\sqrt{n}$. There is an associated problem where: ...
2
votes
1answer
90 views

Dual Simplex Method

Suppose that in a Linear Programming problem in the dual Simplex Method there is a first element (in the first column) negative. If there are in that pivot row some negative numbers we take $\max$ ...