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

learn more… | top users | synonyms

1
vote
1answer
22 views

linear programming problem - how much additional resources should I buy?

I have the following linear optimization problem: Maximize $$\sum_{i=1}^{n}x_{i}B_{i}$$ subject to the constraints $$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \le l_1$$ $$...$$ ...
-1
votes
0answers
18 views

Convex basis and conical basis (how to draw?)

There is a question, I'm struggling with: Find vertices of the following described polyhedron, $P:=P(A,b)=conv(V)+cone(E)$ where $V$ is the set of all vertices of $P$ and $E$ is the set of all ...
2
votes
1answer
11 views

improving symbolic generation of objective function for optimization

I am currently using matlab to solve an optimization problem. I am generating the objective function using the symbolic toolbox. I planned use the symbolic toolbox to calculate the gradient and ...
1
vote
0answers
9 views

Computing the Optimal Simplex Tableau for Linear Programming

I am learning in my class about computing the optimal simplex tableau. I learned that, if you have an initial basic feasible solution, you can apply a series of formulas to compute the optimal ...
1
vote
1answer
32 views

Solving a linear optimization problem with products and work benches

I am taking a linear algebra course and I have a homework assignment of: A factory produces 5 products T1, T2, T3, T4, T5. Products are made on 3 different work benches P1, P2, P3, which can be used ...
3
votes
1answer
776 views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
4
votes
0answers
39 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
0
votes
0answers
12 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
0
votes
0answers
12 views

Dual problem of a linear programming example with an unrestricted variable

I have been asked to find the dual of the following (P): Min $Z= x_1+ 2x_2+ 3x_3$ Such that $$-4x_1 +3x_2 +5x_3=5$$ $$x_1+ 2x_3 \geq 4$$ $$x_1,x_3\geq0$$ $$x_2 \ \text{ unrestricted}$$ I ...
2
votes
1answer
37 views

Description of a constraint for a mixed integer program.

Suppose we have 100 items that are labelled from the set $P = \{A, B, C, D, E\}$. My constraints are as follows: I want to choose exactly seven items. The choice should have at least one item of ...
-1
votes
0answers
23 views

Linear Programming two phase method question [on hold]

Let the Linear programming problem (P) be defined as follows: $\min Z = x_1+2x_2+3x_3$ Such that $$-4x_1+3x_2+5x_3 \ge 5\\ x_1 +2x_3 \ge 4\\ x_1,x_2,x_3 \ge 0$$ How do you go about solving ...
1
vote
1answer
23 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
25 views

Duality - linear programming

I have to find a respective dual programme for the given LP $$ \max \ 2 x_1 + 2x_2$$ s.t. $ -x_1 - x_2 \ge -5 \\\phantom{-}x_1,\phantom{,,}x_2 \ge 0$ I got this: $$\min \ 5y_1$$ s.t. $y_1 \ge 2 ...
1
vote
1answer
25 views

Removing a max function in the constraints

Can the following problem be transformed into a linear programming problem: Find $x_1,..,x_N$ which maximizes the objective function $$\sum_{i=1}^{N}x_{i}\sum_{j=1}^{n_{i}}c_{ij}$$ subject to the ...
1
vote
0answers
21 views

Generating primal solution from dual solution of a LP

How to get the primal solution from a dual solution in general? For example, let the primal problem is $$ \text {maximize } 2r_1+2r_2-2c_1-2c_2 $$ where $$ r_1-c_1\leq1\\ r_1-c_2\leq1\\ ...
0
votes
1answer
10 views

Efficient algorithm for slightly generalized attribution problem

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column. More ...
0
votes
1answer
36 views

Optimization Problem - Lowest Total Price from Multiple Suppliers

I believe this is a linear algebra problem, but if not please let me know: Say you have 4 suppliers. You want to order 4 different items. The 4 suppliers each have a different price for each item and ...
0
votes
2answers
28 views

Minimization problem, both terms in function positive

I have the following problem: Using the simplex method, minimize $z = 10x + 3y$ given the following conditions: $$2x + y \le 12$$ $$4x + y \ge 12$$ $$2x + y \ge 8$$ I've been told that minimizing ...
0
votes
1answer
12 views

MINLP optimization with matlab reaching different solutions every run

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. I describe the problem in more ...
0
votes
0answers
22 views

If the supremum is finite, then the value is attained.

In a linear programming proof we have the: $\sup\{c^Tx: Ax \le b\}$ This supremem can be $\infty$, or defined as $-\infty$, if there are no vectors x such that $Ax \le b$. But it is stated that ...
-1
votes
0answers
19 views

Integer linear programming. ambulance [closed]

......................... nnnnnnnnnnnnnnnnnnnnnnnnnn hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh jjjjjjjjjjjjj
0
votes
1answer
14 views

matlab MINLP optimization with ga

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. There are additional constraints but ...
0
votes
1answer
21 views

integer linear programing in matlab with the symbolic toolbox

I am writing a program to optimize a set of generators. I have hourly data and but dont want to necessarily optimize the whole time series. For a similar problem in the past I used the symbolic ...
4
votes
1answer
81 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
1
vote
0answers
48 views

Proof that a convex set is polyhedron [closed]

How can I prove that a convex hull is a polyhedron? Given are vectors $x_1, ..., x_m$. Show that $P:=\text{conv} (\{x_1,...,x_m\})$ is a polyhedron. Polyhedron is defined as $P=(A,b)$ and ...
1
vote
0answers
11 views

Modeling a lower-bound constraint on a euclidean distance in quadratic programming

I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either ...
1
vote
2answers
46 views

Escaping from a point in linear programming

Is there a trick for explaining the following constraint as a set of linear (in)equalities? $$ \sum_{i=1}^n|x_i-a_i|>0, $$ where $a_i$'s are real constants.
1
vote
0answers
54 views

Prove $\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$

Prove the minimum directed cycle mean cost satisfies: $\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$ using the Bellman-Ford algorithm. Let ...
1
vote
1answer
665 views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
0
votes
0answers
24 views

Solution existence on $ax + by = c$

I have to produce an program which resolve the following equation: $ax + by = c$ With the following condition: $a$, $b$ and $c$ are known positive integer. $x$ and $y$ are positive ...
0
votes
1answer
37 views

Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?

I want to solve the problem of minimizing $$\mathbf{c}^T\mathbf{x}$$ subject to the condition that $$A\mathbf{x} = \mathbf{b}\text{,}$$ where $\mathbf{b},\mathbf{c}$ are given vectors in ...
1
vote
1answer
265 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
0answers
35 views

Algorithm to efficiently compute$ A^k$

If a symmetric matrix $A$ has SVD $A=U\Sigma U^{\top}$, then $A^k=U\Sigma^kU^{\top}$. What would be the most efficient algorithm to compute $A^k$ such that the worst case time complexity is as low as ...
1
vote
0answers
14 views

linear programming problem given initial solution

While dealing with a linear programming problem we usually try to start with the basic feasible solution corresponding to the identity Matrix in the coefficient matrix. I have no idea how to solve the ...
1
vote
0answers
33 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$ ...
0
votes
0answers
14 views

When can i solve simplex tableau

I saw exercises where they give an objective function ( without restrictions ) and a simplex tableau to be completed , if you can solve How do I know when it may solve the tableau ? What are the ...
2
votes
1answer
61 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
0
votes
0answers
13 views

Polar cones' property [duplicate]

I am trying to prove: $A \subseteq B \implies B^\circ \subseteq A^\circ$ where $A^\circ$ is polar cone of $A$ ($A$ convex cone) and $B^\circ$ is polar cone of $B$ ($B$ convex cone)
1
vote
1answer
33 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost.

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
0
votes
1answer
877 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
4
votes
2answers
256 views

why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic?

Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an articial variable becomes nonbasic, it need never again become basic. Thus, when an articial ...
2
votes
2answers
288 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
-1
votes
0answers
17 views

Optimization problem with embedded absolute values (how to turn to LP)

say I have a problem of the form $$\begin{align*}\min&\sum_i{c_i\,|x_i-|y_i-z_i|+|s_i|\,|}\\[0.3cm] \text{s.t. }&0\le x\le 1\\[0.2cm] &0\le y \le 1\\[0.2cm] &0\le z\le 1\\[0.2cm] ...
1
vote
0answers
47 views

Prove an artificial variable that leaves the basis will never return.

Prove an artificial variable that leaves the basis will never return. Edit: This is for the simplex method (I think). I have no idea how to start this. Anyone know any books with these kinds of ...
0
votes
0answers
15 views

Calculating ONeill prices in combinatorial auctions using the dual (Linear programming)

I am trying to calculate the O’Neill prices[1] for the individual atoms in a combinatorial auction. The method is: Solve the IP to find the optimal allocation for the auction. Remove the integer ...
1
vote
0answers
25 views

How to create a linear set of proportions summing to 1?

I'm not even really sure what this concept is called. But my objective is to create, for any n, a linear distribution of numbers less than 1 summing up to and plateauing at 1. It would have to work ...
0
votes
2answers
545 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
0answers
12 views

Optimizing a set of rules to better predict the outcome of events

I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ...
0
votes
1answer
38 views

Pseudoinverse system of linear equation

$Ax = b$ describes a convex polyhedron, where $A$ is a real matrix and $b$ is a real vector. Now assume $A$ has less rows than columns. If you take a look here: ...
2
votes
2answers
29 views

Can calculus optimization problems be turned into linear programming problems?

I found a Linear Programming textbook somewhere, and I skimmed through the first few pages. While I am not nearly enough ready to go through it, the things it dealt with seemed very much like calculus ...