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

learn more… | top users | synonyms

0
votes
0answers
9 views

Can we find some of those variables verifying this inequality

Let us consider $7$ variables verifying these inequalities: $c>2$ , $x<y$ , $z>w$ , $t^{c}>t$ , $t>x$ , $z<B$ , $w<B$ My question is: Can we find some of those variables ...
0
votes
0answers
5 views

Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...
2
votes
3answers
36 views

Prove $A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m} $ in $\mathbb R^m$ are linearly independent viewed as vectors in $\mathbb R^{m-1}$?

Suppose I have linearly independent vectors $A_1, A_2, \ldots, A_m$ in $\mathbb R^m$ Consider the matrix $B = [A_1, A_2, \ldots A_m]$ consisting of these vectors and suppose $B^{-1}[A_1, A_2, ...
0
votes
0answers
28 views

In your opinion, what's happening if in following linear programming problem we have A=A Transposed? [on hold]

Max Z=Cx s.t. Ax <= b In this case, primary problem and Dual problem are Equivalent. In fact that, my question is what's the meaning of above question? Thanks in advance.
0
votes
0answers
13 views

*SOLVED* Largest lower bound that covers p percent of the data

Solved: Rahul wrote the solution to the problem in the comment to the question. Thank you Rahul. The original question is below: Suppose that you have a finite set $X\subseteq \mathbb R$, and you ...
1
vote
1answer
35 views

An inequality about Hermitian matrices

Say one knows the following statement, That for any Hermitian matrix $H$ with eigenvalues $\lambda_1 \geq \lambda_2 ..\geq \lambda_n$ one has, that in any basis, for any positive integers $1 \leq i_1 ...
0
votes
0answers
11 views

Replace BigM by SOS sets?

is there any way to get rid of Big-M when forming Mccormick envelopes by SOS sets ? eg x1 >= x2 - BigM*(1-w) x1 <= x2 x1 <= BigM*(w) where ...
0
votes
0answers
12 views

Why we always chose minimum Ratio in Simplex method? [on hold]

Why we always chose minimum ratio in simplex method? (linear programming problem)
1
vote
2answers
39 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
0
votes
0answers
8 views

linear programming Q [on hold]

Actully I dont know about that but I'm trying to solve this case: we have a 300000 LE and we want to make surgeries for children in three fields "Cardio, burn and Eyes surgeries" the cardio ...
0
votes
0answers
9 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
0
votes
0answers
20 views

How can I use Mehrotra's predictor-corrector primal-dual interior point method to solve a problem that is not in the form of cTx?

I am not very familiar with optimization methods. I am studying the paper "Blind channel identification for speech dereverberation using l1-norm sparse learning" (here: http://linyq.com/NIPS2007.pdf). ...
2
votes
1answer
24 views

Modeling with Linear Programming

Here is the scenario; Let's say that a wholesaler have a storage with the capacity of $75,000$ $m^3$. The stock of corn at the beginning of the year is $15.000$ $m^3$ and the working capital is $ ...
0
votes
2answers
20 views

Maximising radius of a circle inside a 2D shape

I'm given a set of inequalities which define constraints of a geometric shape. For simplicity, let's assume its a 2D object, say a triangle. I want to find the maximum radius $r$ of a circle $c$, that ...
0
votes
1answer
13 views

LP model constraint formulation

We have a production plant that for each ton of $a$ requires $p_x$ tons of $x$ and $p_y$ tons of $y$ and we must decide how much material to ship to this plant. Is it just $a = y/p_y = x/p_x$? Do I ...
0
votes
0answers
10 views

Show that B is an optimal basis matrix obtained by replacing b with b*?

I need help with the following 2 part question: Let $B = [a_{B1}, a_{B2}, \ldots , a_{Bm}]$ be an optimal basis matrix for the following linear program: Maximize $CX$ Subject to $AX \leq b$, ...
0
votes
0answers
19 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
1
vote
1answer
41 views

Games on betting from a set

Two players each chooses a number from the set $\{1,2,4\}$ and correspondingly bets an amount of \$$1$, \$$2$, or \$$4$. There is no collaboration between players. Rules: $1.$ If the two chosen ...
3
votes
1answer
37 views

Upper bound on maximum absolute value of all subdeterminants of a matrix

Let $A \in \mathbb{R}^{m \times n}$ and let $\Delta(A)$ be the maximal absolute value of the determinants of the square submatrices of $A$. A simple lower bound would be $$ \Delta(A) \geq ...
2
votes
0answers
19 views

mathematical model of an assignment/scheduling problem

I am solving a scheduling problem and I am able to abstract it into an assignment problem of assigning 45 machines to 42 jobs. the assignment problem was given as having 14 jobs, each with 3 tasks and ...
0
votes
0answers
10 views

Solving the problem of Affinity using Linear Programming

The affinity problem states that when we have a set of requested instances to be launched on a set of hosts, the placement of instances should be such that they must be close to each other. There can ...
-1
votes
0answers
17 views

Optimization (Excel Solver) [closed]

Coordinating Advertising and Production. The Hawley Lighting Company manufactures four families of household lighting at its factory. The product families are table lamps, floor lamps, ceiling ...
0
votes
1answer
50 views

How can I tell if a two-person game is non-degenerate, given its payoff matrices?

Consider a two-person game with payoff matrices defined by \begin{equation} P= \left( \begin{array}{ccc} 0 & 4 & 1 \\ 2 & 2 & 4 \\ 3 & 2 & 2 \end{array} \right) \quad ...
1
vote
1answer
47 views

Payoff matrix with a specific form

I am very stuck on this question: Suppose that $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$, $A$ is a $m \times n$ real matrix, and all components of $A$, $b$ and $c$ are positive. Consider the ...
2
votes
3answers
41 views

Convert the non linear problem into standard minimization linear programming form

I have to convert the non linear problem into standard minimization linear programming form Minimize: $|x|+|y|+|v|$ Subject to: $$x+y\le1$$ $$2x+v=3$$ I dont have any idea how can I do it...I would ...
0
votes
0answers
9 views

Necessary and sufficient conditions for a feasible Linear Programme

I am trying to solve the following problem. I have set up the dual, and drawn a graph of the dual. I know solutions must be in the first quadrant as $ x\ge0$ but I don't know how to complete the ...
2
votes
1answer
24 views

Linear Programming Problem - Looking for an Explicit Solution

How can I solve a linear program of the form: $$\min c^Tx\\ \mathrm{s.t.}\ Ax=b\\ x\geq0\\$$ where $c$ is fixed. In the specific case I am looking at, $$x \in R^n$$ $A$ is an $m\times n$ ...
0
votes
0answers
18 views

Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming? Update: say you want to do SVD. Can you model it as a ...
1
vote
0answers
4 views

solve multicommodity flow in polynomial size

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size?
-3
votes
0answers
18 views

Simplex Algorithm go wrong [closed]

When can Simplex Algorithm go wrong? Is there any other way to solve Simplex other than the traditional way of pivoting?
0
votes
1answer
35 views

Probability & darts(in Python)

Suppose you toss a dart at a circular target of radius 10 inches. Given that the dart lands in the upper half of the target, find the probability that its distance from the center is less than 5 ...
2
votes
0answers
30 views

Simple Linear Program Problem in Constrained Optimization

Here is a subproblem I am having difficulties with: $$d = \arg\min_x \ c^Tx$$ subject to $$x: \sum_{i=1}^{n} x_i = 0,\quad x_i \ge -b_i$$ for some $b \in \mathbb R^n$. So I'm looking for an ...
1
vote
1answer
21 views

Question about “linear programming problem” in reference to joint pmf

I'm working on a homework problem and I'm not totally sure what the question is asking... The question reads: "Consider the linear programming problem: maximize $Ax_1+Bx_2$ subject to $x_1+x_2\leq ...
0
votes
0answers
16 views

Let $P$ be a minimization primal problem $\min c^T x$. Does $P$ and its dual $P^*$ always have the same number of optimal solutions?

Let $P$ be a minimization primal problem $\min c^T x$ and let $P^*$ be its dual. I've been wondering about the following: Suppose $P$ has exactly $n$ optimal solutions. I know that $P^*$ also has ...
1
vote
1answer
13 views

Dual problem of a maximization primal problem $P$?

Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$. The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a ...
1
vote
0answers
58 views

Normalizing Vectors to get short numbers

$\vec{A}$ is vector agent, $\vec{O}$ is vector Object, $m$ is a constant integer. The following expression is repeated with a different O for every loop cycle: ...
0
votes
0answers
30 views

Shadow Prices in relation to a Simplex Tableau

I've solved the maximisation problem $z = 5x_1+6x_2+2x_3$ subject to $x_2 + 0.5x_3 \leq 2000$ $20x_1+20x_2+12x_3 \leq 100000$ $x_1 \geq 2000$ $x_3 \geq 2000$ using long-hand Simplex Method ...
0
votes
1answer
35 views

How does the Simplex method of solving LPs use the starting solution?

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic ...
0
votes
0answers
13 views

The network simplex algorithm: finding initial basic feasible solution by auxiliary problem.

Suppose we have a network flow problem without capacities on the edges and want to find a basic feasible solution to start of the network simplex algorithm. It is then stated that if we introduce an ...
0
votes
0answers
17 views

Ford-Falkerson's algorithm for undirected graphs (What am I missing?)

I "found" an algorithm for finding maximum flow in undirected graph which I think isn't correct, but I can't find my mistake. Here is my algorithm: We construct a new directed graph in the following ...
1
vote
1answer
17 views

Formulating Solution for Branch and Bound

I have a linear programming question which I am setting up for a branch and bound solution. I am having issues with where to begin. The question is asking to find the minimum operating cost to ...
0
votes
1answer
25 views

Combining the duality principle and the graphical method

I am trying to minimize this linear program by combining the duality principle and the graphical method: I can't seem to find an example of how to approach this, can anyone show me how I would go ...
0
votes
0answers
13 views

Solve LP-problem in standard form where the right-hand side vector depend on real variable

Suppose we have a LP-problem in standard form $\min c^T x \\ s.t. \ A x = b \,, \ x\ge 0$ where $b$ is an $1 \times 2$-matrix. Suppose we have an optimal basis $B$ corresponding to $b$ and suppose ...
1
vote
1answer
35 views

How to find a polynomial of order $4$ which minimizes a given condition

How to find a polynomial $P(x)$ of order $4$ such that $\max\{\vert\ln(n)-P(n)\vert : 1\leq n \leq12\}$ is as small as possible? I guessed the solution with linear programming, but I don't know ...
0
votes
0answers
21 views

Maximal area intersection of half-planes in $\mathbb{R}^2$

Suppose we have $m$ half-planes $H_1,...,H_m$ in $\mathbb{R}^2$ such that $H_1 \cap \dots \cap H_m = \emptyset$. Let $A$ be a set of subsets $S$ of $\{H_1,...,H_m\}$ with non empty intersection and ...
1
vote
0answers
14 views

Expressing nonlinear problem as LP

I am using GLPK to solve a simple linear problem. Given is a set of distances $d_{ij}$ between nodes of a graph. We want to assign to each edge a velocity $v_{ij}$ such that the average time of ...
0
votes
0answers
20 views

Simplex Method Geometrically

Suppose that at some iteration of the simplex method the slack variable $x_s$ is basic in the $i$th row. Show that $$ \large y_{ij\leq 0, j =1,\ldots, n, j \neq s } $$ then the constraint ...
0
votes
1answer
25 views

unnecessary constraint in optimization problem

I have some optimization problem (optimizing parameter $\alpha$)with those constraints: $$\alpha_i\ge0$$ $$\sum\limits_i \alpha_i y_i =0$$ and a third constraints: $$w-\sum\limits_i \alpha_i y_i x_i = ...
0
votes
0answers
25 views

Linear Programming question involving a data set of consumer purchases

I am from Netherlands and preparing for an interview with Two Sigma Capital, which for the position I am applying for is notorious for asking linear programming questions. I was trying to solve this ...
2
votes
0answers
32 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...