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

learn more… | top users | synonyms

0
votes
1answer
24 views

KKT Conditions for NLP [closed]

How may I state the KKT conditions for minimize $f(x) = ax^2$ subject to $Ax \leq b$, $x$ unrestricted?
0
votes
1answer
20 views

A problem about $-\max$ and $\min$

Suppose $X$ and $Y$ are convex compact subsets in $\mathbb R^n$. Let $\langle.,.\rangle$ be the standard inner product. Does the following equality $$\max_{y\in Y} [\langle y, z\rangle- \max_{x\in ...
1
vote
0answers
63 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
0answers
16 views

Tangential surface of an extreme point of a convex subset of a simplex

Suppose that there is a convex set (polyhedra) $H$ which is a convex subset of a simplex $G = \{x\in R^d ~|~ \sum_{i=1}^d x_i=1, x_i \ge 0, i=1,2, ..., d \}$. Clearly, $H$ has extremal points $x^*$ ...
1
vote
0answers
44 views

Maximum over Probabilistic Distribution Functions Space

Suppose $P$ is the set of functions where $p\in P: R^{+2}\to R^+$ and $p(t,s)$ is differentiable in $t$. $\forall t, p(t,\cdot)$ is a probability distribution on the positive axis $s\in [0,\infty)$, ...
0
votes
1answer
40 views

how to take the dual problem of a problem that has a sum in it?

I'm learning about dual problems and was trying to get to an understanding of how to take the dual of a problem that has a sum in it. For example if we try to optimize the sum of all values while ...
0
votes
1answer
41 views

How to determine bounds for variables for an underdetermined linear system of equations?

I want to determine bounds of variables of a system of linear equations which is an underdetermined system. I illustrate with a simple example. For instance, considering a small system -- x+y+z = 10 ...
2
votes
1answer
61 views

How can I determine B-inverse from an optimal tableau of a LP?

(This is NOT a homework question, I am reviewing for my upcoming exam) Given this linear program: and this optimal tableau: I am attempting to determine $B$ inverse using the table above. From ...
0
votes
0answers
29 views

Matrix of LP has not full rank after converison to standard form

I have coded a reader for MPS files in MatLab, which yields A, b and c as in ...
0
votes
0answers
9 views

Pcross-like in near-linear time

I have a problem with a puzzle game like pcross in which I have a $n\times n$ square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that ...
0
votes
1answer
40 views

negative roots of a squared term in Matlab

I have an array of numbers, $B$, that can be written as $B = A^2$, where $A$ is also an array of numbers consisting of positive and negative numbers. If I take the square root of $B$ in MatLab using ...
-1
votes
1answer
61 views

Simplex algorithm reaches optimal solution but with negative slack variables [closed]

I am working on a VBA algorithm that will solve simple versions (single stock length, <1000 patterns) of the Cutting Stock problem, and after a lot of research I have managed to write a VBA program ...
0
votes
1answer
33 views

optimization with constrained coefitients of linear combination

problem description: Given is: set of $m$ arbitrary real value $n$-dimensional vectors $\vec{a}_j$; $m$ can be both larger or lower than $n$; so matrix $\matrix{A}$ composed of the vectors ...
2
votes
0answers
70 views

linear problem with $\|.\|_\infty$ and $\|.\|_1$ norm constraints

I have a question regarding a straightforward linear algebra problem, yet the solution is (at least for me) not trivial. Assume the sequences $\phi_i$ with coefficients $\phi_i[n]\in\mathbb{R}$, and ...
0
votes
0answers
58 views

Is it true this problem cannot be solved with linear programming?

A paraphrasing of the relevant information: An oil company produces two types of oil, X and Y. The refinery is to buy four different sorts of crude oil which when refined result in three halfproducts ...
1
vote
2answers
32 views

Simplex method: Third iteration has same pivot row as earlier

I have the following minimization problem: $F(x)=-5x_1-4x_2$ Subject to: $4x_1+x_2<20$ $3x_1+2x_2<18$ $x_2<6$ And of course $x_1,x_2>0$. ...
0
votes
1answer
31 views

How to formulate LP for shortest path problems?

I'm trying to understand how LP formulaton for shortest path problem. However I'm having trouble understanding constrains. Why this formulation work? http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf ...
1
vote
0answers
19 views

Function Extension

I am faced with a problem: Let $A$ be an $m\times n$ rational matrix, $c$ be a rational $n$-vector. Consider $f$: $f(u)=\max\{c^Tx|x\in S^u\}$, where $S^u:=\{x\in \mathbb{Z}^n|Ax\le u\}$ and $f$ is ...
0
votes
0answers
26 views

KKT Conditions for Euclidean Distances

Suppose that we have an undirected and edge weighted graph $G = (V,E)$. The weight $w_{ij}$ of an edge $\{i,j\} \in E$ determines the Euclidean distance between the vertices $i$ and $j$ s.t. $i,j \in ...
0
votes
0answers
7 views

How to develop a second order conic robust optimization model for a linear programming problem

I have the following linear programming problem and I was wondering if anyone can help me how can one transform a general linear programming problem to a second order conic robust optimization ...
1
vote
1answer
27 views

Disprove that the given strategy pair is a solution to the game.

Problem: For the following matrix game, prove or disprove that the given strategy pair is a solution to the game. \begin{align} A &= \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & ...
0
votes
2answers
24 views

LP Constraint Problem

If you have an investment fund which has four options $x_1,x_2,x_3,x_4$ More should be invested in the combination of funds $x_2$ and $x_3$ than funds $x_1$ and $x_4$ by a ratio of at least $1.5:1$. ...
0
votes
0answers
38 views

Solving a linear programming problems is no harder than solving systems of linear inequalities

Suppose that we are given a subroutine which, given a system of linear inequalities $Ax \leq b$, $x \in \mathbb{R}^n$ , either produces a solution or decides that no solution exists. I would like to ...
0
votes
0answers
38 views

linear equations soluton with constraints

The problem arises from FEM solver where I have to integrate some constraints to the linear equations which has the known formation shown as below, it is normally called member releases which actually ...
0
votes
0answers
13 views

Set of Feasible Directions

I don't even know what to do for the first part. How do you even find all the feasible directions of a particular Set...? Then how do you proceed to finding basic directions?
4
votes
2answers
52 views

prove that if A is M-matrix then A is also a P-matrix

$A \in \mathbb{R}^{n \times n}$ is a $P$-$matrix$ if all its principal minors are positive. Let $I$ be the identity matrix of rank $n$. $A \in \mathbb{R}^{nxn}$ is a non-singular $M$-$matrix$ if ...
1
vote
1answer
26 views

Generalized Farkas Lemma

Farkas lemma can be stated as follow: If for all $\mu$ such that $\mu^T\cdot a_i \geq 0$ implies that $\mu^T\cdot b \geq 0$ then $b=\sum \lambda_i a_i$ with $\lambda_i \geq 0$ I need a generalized ...
0
votes
0answers
12 views

Modellling a newspaper delivery route as an MILP

I am trying to model a smaller version of this problem as an Integer programming problem and I am having some issues while formulating it. Suppose there are 2 vehicles and 6 customers, and a single ...
0
votes
1answer
38 views

How to read Linear Program from an optimal tableau

Suppose we are given an optimal tableau and the objective function. How can we determine the RHS of constraints or if possible the constraint equations? For example consider the given tableau with ...
1
vote
0answers
23 views

Use Fenchel Duality to minimize cTx, subject to x ∈ A∩C

minimize cTx subject to x ∈ A∩C, where $x,c∈R^n$, C is a convex closed nonempty set in $R^n$, A=a+S is an affine set, where $a∈R^n$ and S is a subspace of $R^n$, and A ∩ ri(C)≠ ∅. Use the Fenchel ...
2
votes
2answers
46 views

Minimize $x^2+y^2$, subject to… (optimal points, KKT conditions, dual theories)

I am new to this. I am self learning to get ahead of my next years course and came across this question. I thought it would be a good question to look at due to it touching an many different aspects ...
0
votes
1answer
17 views

Simplex Method : Entering variable and leaving variable

i have a homework question and i am not sure if a understood the first part correctly ( english is not my native language ). For the entering variable : I guess $ 10x_1 - 32x_2 + 8x_3 + 5x_4$ is ...
1
vote
2answers
48 views

Let $A$ be a given matrix. Then there exists some $x \ne 0$ such that $Ax = 0$, $x \ge 0$ or there exists some $p$ such that $A^Tp > 0$

Exactly one of the alternatives must hold. My attempt: Suppose that there exists some $x \ne 0$ such that $Ax = 0$, $x \ge 0$. By contradiction, let's suppose that $A^Tp \gt 0$ for some $p$. Since ...
0
votes
2answers
23 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1$=1 ...
0
votes
2answers
39 views

Linear Optimization modelling : Finding Constraints

i have a homework question : I figured out that the profit for keyboard 1 is 3€ (k1 = 25-(5+5+12) = 3) and for keyboard 2 its 2€ (k2 = 22 - (4+10+6)) Therefore we want to maximize p = 3*k1+2*k2 . ...
0
votes
2answers
20 views

Integer Programming Conditional Constraints

I have a set of integer [0,1]variables $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$ I want a conditional constraint such that if any of the $x$ variables is equal to 1, I want the sum of the subsequent $y$ ...
3
votes
1answer
109 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
0
votes
2answers
41 views

Scheduling Algorithms

I Need to send a number of packets from A to B. A and B are connected by different paths of different lengths (all disjoint). Paths have different capacities too (like I can't overfill them). I have ...
-3
votes
1answer
24 views

Solve the above program [closed]

Consider the problem of covering the triangle with vertices at the points $(0, 0), (0, 1),$ and $(1, 0)$ with a ball of smallest radius. $$\min r$$ $$s. t. \> x ^2 + y ^2 ≤ r$$ $$(x − 1)^ 2 + y ^2 ...
-1
votes
1answer
23 views

Find all the points satisfying the Fritz John conditions

Consider the problem $$\min \>x^2+y^2 $$ $$s.t.\> x^2-(y-1)^3=0$$ Find all the points satisfying the Fritz John conditions Solution The FJ conditions are $$2x+\mu_1 2x=0$$ $$2y-\mu_1 ...
0
votes
0answers
47 views

Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. ...
1
vote
1answer
53 views

Linear Programming Duality Proof

I have really no idea where to go in this problem. This is from Bertsimas Introduction to Linear Optimization, Exercise 4.26. My teacher would like us to create a primal and dual LP to solve the ...
2
votes
1answer
30 views

Is there a connection between duality in linear programming and duality in functional analysis?

In linear programming we optimize a linear function which is constrained by linear inequalities or linear equalities. Under some conditions you can rewrite the problem to the dual problem, so that you ...
0
votes
1answer
27 views

Linear programming with quadratic constraints

I have a given set of variables: $x_1,y_1,x_2,y_2,x_3,y_3$ The objective function is to minimize the sum of these with quadratic equality constraints: $y_1(x_1+x_2+x_3)$=0 $y_2(x_2+x_3)$=0 ...
1
vote
1answer
27 views

How to set up linear programming problem for maximizing score of various combinations?

I have a sample data set that looks like this: x y w 1 1 5 1 2 1 6 2 3 1 7 3 4 2 8 4 5 2 7 5 6 3 5 6 7 4 6 7 8 4 5 8 x and ...
0
votes
1answer
39 views

Formulate the dual problem for primal problem with absolute value constraint

Let $y \in R$, the goal is to find the dual problem to: $$\min y\\ s.t. |y| \leq 0$$ The lagrangian of the problem is: $$L(y, \lambda) = y + \lambda|y|$$ The dual function is: $$g(\lambda) = ...
1
vote
1answer
25 views

What is $ {z_j} $ in this tableau? (Simplex algorithm)

I've hightlighted the section in the tableau I don't understand. Clearly the 28 comes from plugging in the 4 and 2 in the objective function but where do the other numbers in the row come from? Any ...
1
vote
1answer
40 views

Transportation problems

i'm a master student at the deparment of statistics. And i will prepare a presentation on transportation problems in the course of optimization (or linear programming / mathematical programming) I ...
0
votes
2answers
27 views

How to minimize given functional

I confronted the next problem: we have certain values $\psi_1, \psi_2, \psi_3$ in 3 points $x_1, x_2, x_3$, also we have a general functtion with 2 undefined coefficients ($A,x_0$): ...
4
votes
1answer
40 views

How to setup the correct transportation tableu for this Caterer Problem?

The problem said: A caterer must supply 110 napkins on Monday, 90 on Tuesday, 130 on Wednesday, and 170 on Thursday. The caterer initially has no napkins on hand. New napkins can be bought for ...