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

learn more… | top users | synonyms

1
vote
1answer
16 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
vote
1answer
7 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
31 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 ...
4
votes
0answers
38 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
11 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
36 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
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
0answers
21 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 ...
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
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 ...
1
vote
0answers
46 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 ...
0
votes
0answers
23 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
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.
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 ...
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 ...
-1
votes
0answers
19 views

Integer linear programming. ambulance [closed]

......................... nnnnnnnnnnnnnnnnnnnnnnnnnn hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh jjjjjjjjjjjjj
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
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
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
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
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 ...
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 ...
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 ...
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 ...
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 ...
0
votes
1answer
30 views

Calculating the distribution between a range without an MILP solver?

I am currently using a MILP calculation and I was wondering if anyone can recommend a more mathematically simplistic method of calculating this distribution and arriving at a similar result? Qty - ...
0
votes
0answers
18 views

Finding the Dual of a primal LP

Suppose that we have the following primal LP: $\min z=c^Tu+d^Tv \\ \mbox{s.t.}\ \ \ \ \ \ \ \ \ u+Av=b, u\geq 0, v\geq 0$ I want to find the dual problem of this LP but I am slightly confused as ...
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

Mathematical model for MILP optimisation problem- power scheduling

I am having trouble trying to formulate a mathematical model for the problem below to solve later as an MILP problem using different optimization software. I want to formulate the model so as to ...
-1
votes
0answers
16 views

Linear programming and their geometry: cones

This is a snippet of a solution in my notes. Why can we conclude that from figure 1? Why can we say that the arrows are between and do not go all the way around the axis?
0
votes
0answers
70 views

Formulating linear programming treatment plan based on costs, periods, and condition

Note that this question is cross posted from OR-exchange Although we have a software that solves this for us, I'd like to understand the background behind the scenes as well as build a validation ...
0
votes
0answers
19 views

Finding the dual of this linear program?

I'm having trouble figuring out the dual to this linear program. When I put it into a online solver I'm not getting the same answer. Heres the Primal: Max $2x_1 - x_2$ $2x_1 + 3x_2 - ...
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 ...
0
votes
0answers
15 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
21 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
39 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
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
36 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 ...