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

learn more… | top users | synonyms

0
votes
0answers
8 views

Set of optimal solutions for a linear programs

Consider the linear program: minimize $z = x_{1} - x_{2}$, $x_{1}, x_{2}\geq 0$ subject to: $-x_{1} + x_{2}\leq 1$ , $x_{1} - 2x_{2}\leq 2$ Derive an ...
0
votes
0answers
5 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
0
votes
0answers
46 views

linear programing problem [on hold]

A paint company produces two kinds of paints. Type A for indoor use and Type B for outdoor use. The production levels of these must be determined so that they meet demand requirements, given ...
0
votes
0answers
8 views

How to justify that a basic feasible solution to a Linear Program corresponds to an extreme point of the feasible region?

Say we have an LP Problem in standard form. That is, $$\text{Maximise} \;\; C^T X $$ $$ \text{subject to:} \;\;\; AX = B --(1) \;\;\;\; \text{where $A$ is an $m \times n$ matrix }$$ I read ...
0
votes
0answers
10 views

Linear Programming sufficient and necessary conditions

Find necessary and sufficient conditions for the numbers s and t to make the LP problem: ...
0
votes
0answers
12 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
0
votes
0answers
9 views

Let V be the space of polynomials in t of degree

Let V be the space of polynomials in t of degree ≤ n.Show that the {1,t,t2,...tn-1is a basis of V.
0
votes
1answer
15 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 ...
0
votes
0answers
14 views

Case of affine hull and linear hull possibly being euqal

Let C be a set in $\mathbb{R}^n$. Let $aff(X)$ denote the affine hull of $X$, and $lin(X)$ denote the linear hull of $X$. Suppose $x \in aff(C)$. Then, is it true that $aff(C-x)=lin(C-x)$? The ...
1
vote
1answer
33 views
+150

Linear programming: Basic solution

Let $P = \{ x \in R^n : Ax \leq b, x\geq 0\}$ and $Q= \{ (x, r)' \in R^{n+m}: Ax + r= b, x \geq 0, r\geq 0\}.$ Show that $$x \text{ is basic solution of } P \iff (x, b-Ax) \text{ is basic solution of ...
1
vote
1answer
24 views

Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
0
votes
0answers
22 views

What is the proof/show that the post of linear transformation generated by LDA is at most k-1

What is the proof/show that the matrix $Sw$ generated by LDA is at most rank $p-k$, where $p$ is the dimension of the data and $k$ is the number of classes. LDA: ...
0
votes
0answers
16 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
0
votes
0answers
6 views

constraint formulation in linear programming

I have a integer variable with a constraint such that is unequal to specific. For example, x ≠ 4*k where k is an integer, which means x can be any value except 0, 4, 8, ... I have no idea to ...
1
vote
1answer
50 views

What constraints are needed to to switch on a binary variable in a linear programming model?

I am trying to create a binary variable ($z$) within a linear model which 'switches' on only when another variable ($d$) becomes greater than zero. I have had some success using the following two ...
1
vote
0answers
12 views

Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$. I am able to write each event as a sum of distinct events that form a partition of the space. My goal is to find all the ...
0
votes
1answer
46 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
0answers
16 views

Squaring Orthogonal Matrix Entrywise is Doubly Stochastic

I'm stuck on this question: Suppose Q is an orthogonal matrix. Show that $Q \circ Q$ is doubly stochastic, i.e. entries are nonnegative, every row sums up to 1, and every column sums up to 1. (the ...
0
votes
0answers
6 views

Problem regarding hyperplane separation

I have a doubt on hyperplane separation theorem. In theorem why one of convex set should be bounded.
0
votes
0answers
12 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
30 views

Need help formulating a Traveling Salesman (Deliveryman) Variation

I am working with the following TSP variation: A deliveryman has to deliver orders of items to several different locations around a city. The orders are: ...
0
votes
1answer
23 views

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities. The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined ...
0
votes
0answers
9 views

How to prove that the solution in every next iteration of Simplex algorithm is a BFS

Let Ax = b x >= 0 be the feasible region. Let A be mxn matrix with m <= n and rank(A) = m. Simplex algorithm starts with a Basic Feasible solution. In each step it moves to a new solution. How do ...
0
votes
0answers
5 views

Linear programming with an independent variable

I have a bunch of linear programming problems to solve of the following form: Maximize $f(a, b, c)$ Subject to: $g_1(a, b, c | x) \ge 0$ $g_2(a, b, c | x) \ge 0$ $\dots$ Where the $g_i$ are all ...
0
votes
0answers
15 views

Devising objective function for integer linear programming

I am working to devise a objective function for a integer linear programming model. The goal is to determine the copy number of two genes as well as if a gene conversion event has happened (where one ...
0
votes
1answer
21 views

Finding Optimal Value with Linear Programming Subroutine

I am stuck on this question: Consider the problem: $\underset{x}{\text{minimize}}{\frac{c^{T}x+d}{f^{T}x+g}}$ $\text{s.t. } Ax\leq b$ $f^{T}x+g>0$ Suppose we have prior knowledge that the ...
-1
votes
0answers
109 views

Express a given integer in terms of given, smaller, integers.

[Please see part beginning with EDIT] I have a number(any number for example 10). We can have another small number(it can be any number for ex 3,2 (any digit). So I need add this number which ...
1
vote
0answers
9 views

Executing Branch and Bound using a Simplex tableau

I'm studying the branch and bound method and how it is used in conjunction with a simplex tableau. The issue I'm struggling with is how you incorporate the branches in your tableau to find out ...
0
votes
0answers
18 views

sensitivity analysis - help!

Hi guys I am doing a quesetion on simplex method and am stuck on the second part of the sensitbity analysis question: I am stuck on the part that is asking for 12 + n. I know that I am changing ...
0
votes
0answers
33 views

Casio fx-83gt - help! Linear Programming

Hi guys I'm studying a module called Operational Research and in particular linear programming. I am doing the simplex method and as anyone who studies linear programming would know, you need to ...
0
votes
1answer
32 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
1
vote
0answers
45 views

Linear programming - Textbook recommendations

Next term, I will attend a course on linear programming. Due to the assignments, we will have to write many thorough proofs. I anticipate that we will be supposed to cope with in-depth background ...
0
votes
0answers
21 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
0
votes
0answers
26 views

Linear Algebra - find basis without reduced echelon

For the start of a simplex solver I'm building in Python, I need to find a basic feasible solution. To do that, I need to find a basic solution/find the basis of the constraint matrix. Here's my ...
0
votes
0answers
36 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0
votes
1answer
22 views

Maximum cardinality affinely independent subset of $\mathbb{R}^n$

Let $S \subset \mathbb{R}^n$ such that $S$ is affinely independent. Then $$|S| \le n + 1.$$ Why? (e.g. does anybody know some place where this is proven?)
0
votes
1answer
20 views

Linear programming, how to do the opposite transformation?

This is from a pdf file I found linked to from this site: They first define the primal dual problem like this: Then they have another representation of (p), and show that it's dual is: Now here ...
1
vote
1answer
32 views

Affine and Linear programming

Can someone give a simple explanation as to why the feasible region of a set of linear program/equations is affine?
0
votes
0answers
23 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
0
votes
0answers
19 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
0
votes
1answer
28 views

Euclidean and rectilinear distance and nonlinearity

Can some one please explain why Euclidean distance and rectilinear distance make a problem nonlinear? Thanks
0
votes
0answers
24 views

Converting nested IF's to ILP

I'm trying to convert a nested if structure into a linear programming problem. Here is a simplified example of what I'm trying to do- r1, r2 are binary s1, s2 are natural (I can give an upper bound ...
2
votes
1answer
39 views

Two forms of duality in linear programming

I do not know much about this subject, but I am trying to learn a little. In a book I have it says that a primal problem is: max $c'X$ subject to $AX \ge b$ $X \ge 0$ It says ...
0
votes
1answer
37 views

Linear problem: maximizing net income

Problem: A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash avaliable and machine capacity. Each unit of the first ...
4
votes
5answers
464 views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
0
votes
2answers
35 views

Line that passes between two vectors

I encountered the following in a text book I'm reading and I can't seem to understand why this is true (I'm translating this into English so excuse me if I'm not using the correct english terms): ...
1
vote
1answer
56 views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where ...
0
votes
1answer
29 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
0
votes
0answers
22 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...
2
votes
1answer
54 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...