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

learn more… | top users | synonyms

0
votes
0answers
9 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
0
votes
2answers
268 views

Linear Programming Problem?

You are about to take a test that contains computation problems worth 6 points each and word problems worth 10 points each. You can do a computation problem in 2 minutes and a word problem in 4 ...
0
votes
1answer
49 views

Show both relaxations of boolean LP give equal lower bounds

Given the boolean LP: $$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$ Show that the LP relaxation: $$\text{Minimize}\;\; c^Tx$$ ...
2
votes
2answers
398 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
0
votes
1answer
19 views

Lexicographic Pivoting Rule: Why does that work?

On purpose, I do not write details about it, because I am interested in the intuition and not the details. But if someone asks for it, I can do that. So my question: Could anyone help me with the ...
0
votes
1answer
27 views

Prove that $b_{\perp}^{T}b_{\parallel}=0$

If $A \in \mathbb{R}^{mxn}$ then the unique expansion of every $b \in \mathbb{R^{m}}$ is $b =b_{\perp}+b_{\parallel} $. Prove that $b_{\perp}^{T}b_{\parallel}$. Comment: Saying that they are ...
1
vote
0answers
31 views

Linear program for way optimization with unusual constraints

I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com: The goal of the game is to pick up ...
-1
votes
0answers
18 views

linear programming graphical problem [closed]

I am new in linear programming. I am trying to understand graphical method for solving linear programming problems. so please solve this problem. $$\begin{align}&\max\ Z = 6X_1 + ...
1
vote
0answers
11 views

refomulation of an optimization problem

I have written a program for optimizing a set of generators. And I need to reformulate this problem, to include additional generators and constraints. I have hourly price and cost data and need to ...
-1
votes
0answers
9 views

Can anyone help me solve this problem about linear programming? [closed]

Sailcraft, Inc., is a builder of sailboats in New Bern, North Carolina. The company currently offers three models: the Adventurer (32 feet), the Explorer (42 feet), and the World Cruiser (50 feet). ...
2
votes
1answer
381 views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
0
votes
0answers
20 views

Positive/Negative Definite Bordered Hessian?

I understand how to check a function for concavity and convexity using the Hessian matrix and the rules for the determinants of the leading principal minors. I understand if these rules are violated, ...
0
votes
0answers
16 views

maintaining monotonicity in an optimization problem

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 ...
4
votes
1answer
844 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\\ ...
0
votes
0answers
16 views

Why does the simplexmethod 'break up' - unbounded, LP program, very basic problem

I've calculated a very, very basic LP problem: with >= "greater or alike" and <= "smaller or alike" max x + 2y 4x + 3y >= 12 x <= 4 ...
0
votes
0answers
11 views

Scaling linear constraints to give increased weight to values closer to 0

I am working on devising a integer linear programming model for a gene copy number problem. The general gist of it is that a ILP variable is created for each window for which we have data values. ...
0
votes
1answer
33 views

How to find on each face of a polyhedron one point?

We have a polyhedron in $\mathbb R^n$ generated by the intersection of a collection of finete hyperplanes or the convex hull of the set of vertices. My question is: Is there any algorithm for ...
1
vote
1answer
27 views

Linear Optimization: Objective function value, basic feasible solutions and reduced cost

For the system $$Ax=b, x \geq 0$$ for $A \in \mathbb{R}^{m \times n}$, $m \leq n$, we call a set $B \subseteq \{1, \dotsc, n\}$, $|B|=m$ a basis for $A$, if $A_B$ is invertible, where $A_B \in ...
0
votes
1answer
14 views

Finding the intersection between 2 lines using matrices

My professor uploaded some notes, and there's a step in his explanation of a Linear Programming Problem which I do not understand. He takes 2 lines and converts them into matrices in order to find the ...
0
votes
0answers
19 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 ...
1
vote
1answer
22 views

Primal of Dual of LP problem

Given that the following relation holds: $$\begin{align*} &\textbf{Primal problem} \\ &\max Z = c^Tx \\ &s.t. \\ &Ax \leq b \\ & x \geq 0\end{align*}$$ $\Longrightarrow$ ...
0
votes
0answers
18 views

Linearizing the sum of product of a binary and a continuous variable

Now suppose we have this expression $z = \sum_jA[j] * x[j]$, where $A[j]$ is a continuous variable and $x[j]$ is binary variable. $A[j]$ is bounded below by zero and above by $AM[j]$ , so I know how ...
0
votes
0answers
14 views

Duality of Linear Program

Formulate the dual of the following linear problem: Min $\sum$ $\sum$ $c_{ij}$ $x_{ij}$ s.to $\sum$ $x_{ij}$ - $\sum$ $x_{ji}$ = 0, $\hspace{5mm}$ $x_{ij}$ >= $l_{ij}$ and $x_{ij}$ $\leq$ $u_{ij}$ ...
2
votes
5answers
286 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
1
vote
2answers
36 views

Represent if-else or OR condition in a linear equation (optimisation with simplex algorithm)

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L. As my ...
0
votes
0answers
8 views

Showing that every extreme point of the set of solutions of the standard form of constraints of any L.p.p. is a basic feasible solution

Let $\vec y$ be an extreme point of the convex set of solutions of $A \vec x=\vec b $ where only the solutions of $\vec x(\in \mathbb R^n)$ with all components non-negative are taken ; then I want ...
3
votes
0answers
33 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 ...
2
votes
0answers
46 views

Lagrange Multipliers for linear functionals

Say I have a Banach-space $X$ and linear (!) functionals $f,g$, and I'm trying to solve the constrained optimization problem $$max~f(x)\quad s.t.~g(x)= 0,~\Vert x\Vert\le 1.$$ Suppose I can show ...
1
vote
1answer
770 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
1answer
18 views

Does optimal solution always occur at a vertex?

Is it true that if LP $ \text{max} \{c^Tx \ | \ Ax \leq b \}$ has an optimal solution, then $\exists$ a vertex which is simultaneously an optimal solution for LP? I know this works for LP of a ...
0
votes
1answer
28 views

Non-negative solution to a underdetermined linear system

I have an underdetermined linear system (more unknown that equations) Ax=b where both b and x represent probabilities. Im currently using ALGLIB (rmatrixsolvels) to find a least square solution but ...
0
votes
0answers
32 views

LP in standard form

I don't know how to properly named this question but here it goes: Let $x, c \in \Bbb{R}^n$, $b \in\Bbb{R}^m$, $A \in \Bbb{R}^{m \times n}$. Consider LP in the form: min $\{c^tx : Ax = b, x \ge 0\}$ ...
0
votes
1answer
32 views

Linear regression with constrained weights

I have a set of $n$ linear combinations, each with $m$ parameters and desired value $b$. I want to find the set of weights $w$ which minimizes the total equations distances (e.g. the sum of distances ...
1
vote
1answer
298 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
20 views

Simplex minimum ratio test fails on bounded problem

Consider the linear program $\max 3x_1 + x_2 \ @ \\ 3x_1+2x_2 -s_1 = 1 \\ 2x_1+x_2 +s_2 = 2 \\ x_1 \geq 0$ Leting $x_2 = x_2^+ + x_2^-$, introducing slack and solving phase 1 gives $\textbf{x}_b ...
0
votes
1answer
15 views

Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
0
votes
1answer
25 views

Dual part of complementary slackness

The proof of the complementary slackness of P: min $c^Tx $ @ $Ax = b, x \geq 0$ D: max $b^Ty $ @ $A^Ty \leq c$ Goes something like $c^Tx = b^T y = y^TAx \Leftrightarrow c^Tx-y^TAx = 0 ...
1
vote
0answers
14 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
2answers
587 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?
0
votes
1answer
16 views

Find the largest lower bound that covers p percent of the data

Suppose that you have a finite set $X\subseteq \mathbb R$, and you want to solve the following constrained optimization problem Find $\max a$ such that $\frac{|\{ x \in X: x>a \}|}{|X|}\ge ...
0
votes
0answers
11 views

Bicritiera combinatorial/linear optimization problem with an exponential number of non-dominated extreme point

In [Ruhe 1988] an instance of a bicriterial combinatorial optimization problem is constructed such that the number of non-dominated extreme points is exponential in the input size. Are there any ...
0
votes
1answer
16 views

Model logical constraints without binary variables?

Is it possible to express "either $f(x) \leq 0$ or $g(x) \leq 0$" where $f,g$ are linear constraints by using a finite number of continuous constraints/new variables, WITHOUT breaking convexity or ...
0
votes
1answer
28 views

Combining multiple linear programming to minimize the sum

I have a math problem that looks like a bunch of linear programming problem combined where A matrix is shared. Here is the math definition of my problem Minimize \begin{align} & p_1 (x_{11} + ...
0
votes
1answer
899 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 ...
2
votes
2answers
300 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
vote
2answers
26 views

Is Linear Programming a Combinatorial optimization method?

I want to know LP can be considered as a Discrete optimization or continuous. The solutions can be fractions so it should be continuous. Please suggest. thanks
1
vote
0answers
72 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
1answer
1k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
1answer
46 views

how to use linear programming for Heaviside Step function and L1 norm?

I want to find a hyperplane that can divide my sets of points into 2 groups that have nearly equal size. If the hyperplane is $w$, there is a scalar offset $b$. I have $N$ points that are ...