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

learn more… | top users | synonyms

0
votes
1answer
21 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
15 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 ...
2
votes
1answer
89 views

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
32 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
27 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
28 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
8 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
56 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
14 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
54 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
20 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 ...
-1
votes
0answers
8 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
16 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
33 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
24 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
11 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
16 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
27 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
vote
0answers
14 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
20 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
44 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
53 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
24 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
37 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
2answers
36 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
36 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
31 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
33 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
27 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
40 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
60 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
632 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
36 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
124 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
30 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
33 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
57 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$ ...
2
votes
1answer
26 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at ...
0
votes
1answer
46 views

Shadow Price in Linear Programming - Finite Mathematics [closed]

Why is it true that if a slack variable is nonzero, then the shadow price of the associated constraint will be zero?
0
votes
0answers
37 views

Counting the Number of Combinations Conditionally

A bank issues 10 loans ranging from 1000 to 10000 dollars each and charges 5% interest on each loan. On average, the bank finds that 1 in 10 loan recipients defaults. If the loan that defaulted is ...
0
votes
1answer
22 views

The meaning of initial value in linear programming

I am new to LPP. I would like to know what is meant by setting an initial value(IV) to a variable. For example I was solving a problem where objective function(OF) is non-negative. When I give some IV ...
1
vote
0answers
58 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
1answer
56 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
0answers
51 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
1
vote
2answers
35 views

How to introduce flat cost of flow over a node using mixed integer programming.

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program. \begin{array}{ll} \text{minimize} ...