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

learn more… | top users | synonyms

4
votes
2answers
455 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
1
vote
1answer
30 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
1
vote
0answers
35 views

Modeling 4 people going to same place over 3 different places for at least 5 days

I'm trying to model a linear programming task with the condition 4 people going to the same place among 3 different places for at least 5 days. I have the variables for the time spend each person in ...
0
votes
1answer
82 views

Transform OR clause to algebraic equations (linear programming)

So basically my question is: does it exist a way to transform the clausure (a or b or c) into one or more algebraic equations giving as a result 0 or 1 AND that can be included in a linear programming ...
0
votes
1answer
48 views

Definition of an active hyperplane

We are learning about the Geometry of Duality in Linear Programming, and my prof uses the terminology active hyperplane. I'm wondering what the formal definition of this is. I can't seem to find any ...
0
votes
1answer
256 views

Weak form for Linear Dynamic Wave Equation of Dirichlet/Neumann's boundaries?

I have a linear problem with double derivate of space and time, which has Dirichlet boundary condition in $(1)_{2}$ and Neumann's boundary condition in $(1)_{3}$: \begin{equation} \frac{\delta^{2} ...
1
vote
0answers
70 views

Fitting a sine using linear regression

If I have two functions $s_1 = A_1 \sin(\theta+\phi)$ and $s_2 = A_2 \cos(\theta+\phi)$ is it possible to fit a sine or a cosine using linear regression? I usually have much less that a period ...
2
votes
0answers
57 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
1
vote
0answers
66 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
24 views

elements of oriented matroids belonging either to positive circuits or positive cocircuits

I need to prove the following, which seems trivial because it follows from the Farkas lemma (you may know this as the 3 or 4 painting lemma). Can someone show me how to prove this, please? I'm a bit ...
1
vote
1answer
208 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
1
vote
1answer
89 views

Linear Programming Convexity Proof

Suppose a linear programming problem in standard form has as constraints $A \underline{X} = b$ and $\underline{X} \geq \underline{0}$, where $\underline{A}$ is an $m \times n$ matrix and ...
0
votes
1answer
990 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
0
votes
0answers
26 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
1
vote
0answers
11 views

Lp optimality proof [duplicate]

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
3
votes
1answer
540 views

Largest Circle in a Polygon

My polygon is given by $P=$$\left\{x\geq 0, y\geq 0, 3x-4y\leq 2, 4x+3y\leq 12\right\}$ Now trying to find the largest circle inscribed inside these half-planes. But whenever I formulate it as an LP ...
2
votes
1answer
250 views

Dimension of polyhedron defined by inequalities and rank of implied equalities

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm ...
3
votes
1answer
2k views

Taylor's theorem for vector valued functions

I'm reading about linear and nonlinear programming and on one page I have the following statment (I have highlighted the areas where I have problems and drawn questions for them in the bottom of it): ...
6
votes
1answer
127 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
2
votes
1answer
84 views

What needs to be linear for the problem to be considered linear?

Harry Altman presented an excellent question in a comment here: What needs to be linear for the problem to be considered linear? So is it enough to a have linear objective function or other ...
0
votes
1answer
35 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
1
vote
0answers
30 views

Linear programming: can someone explain how the time steps work here?

I'm reading a paper, "A Player Selection Heuristic for a Sports League Draft". In it, the authors have come up with a method to assist you in picking players for a fantasy sports league. I'm having ...
0
votes
1answer
66 views

Integer Programming

I've been having trouble getting started with this problem. Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$ Then show $$7x_1+8x_2+6x_3=3+10z_1$$. ...
1
vote
1answer
219 views

LP: how to understand Duality and simplex

I am learning about Linear Programming right now.. I learned that we can use simplex to solve linear program and I also learned that every linear problem has a dual problem because of duality.. I am ...
1
vote
1answer
63 views

Help to understand the setting up of this Lagrangian

So..I understand up to step 4..but then there are these things I dont get, to start with , it says on (5) that the utility function depended only on the ratios p1/w p2/w ?? why does it say that? ...
1
vote
0answers
84 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
0
votes
1answer
405 views

Prove the dominant strategy of Game Theory

A row $r$ of the payoff matrix is said to dominate a row $s$ if $a_{rj}\geq a_{sj}$ for all $j$ = 1,2,......,$n$. Similarly, a column $r$ of the payoff matrix is said to dominate a column $s$ if ...
1
vote
0answers
59 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
1
vote
1answer
325 views

''min $c^tx$ subject to $x^tAx=1$'': is is possible to solve it with Lagrange multiplier or in the scope of KKT?

I find a problem: Minimize $c^tx$ subject to $x^tAx=1$, where $A$ is a positive semidefinite symmetric matrix. But the question obligates to use KKT but I am trying to apply simple Lagrange ...
1
vote
1answer
45 views

Reduction to LP

What will be the primal and dual of the following problem/ Given an undirected graph $G = (V,E)$, we want to assign non-negative weights to all the edges of $G$, denoted $\{ x_e \mid e\in E \}$ , such ...
1
vote
2answers
116 views

Optimal production for factories

A firm produces two different models of heavy machines; say (A) and (B). The market demand implies that the final profit of each model is 1200 and 2500, respectively. The production of each car (of both ...
1
vote
0answers
160 views

Linear Programming Problem About Inventory and Cost Minimizing

http://www.endustri.anadolu.edu.tr/zkamisli/ENM%20203/duyuru/ENM203%20Assignment%202.pdf In that link, you can find my question. I'm having trouble about defining decision variables. The objective ...
0
votes
0answers
59 views

Formulating an optimization problem

I am having difficulty formulating a schedule/pay statement in to an maximization problem. Problem: If you are AT work for ${\leq }40$ hours/week your pay/hour is $r$, if $>40$ your pay/hour is ...
1
vote
0answers
17 views

Equivalent System of equations

Let system $$\left\{ \begin{array}{l} {A_1}X = {b_1}\\ a_1^TX = {b_2} \end{array} \right.$$ where the last constraint is dependent to others. Prove that if this system be a feasible system then it is ...
2
votes
0answers
42 views

Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
1
vote
2answers
34 views

Linear program dual

We are trying to find the dual of the following linear program. $$ \max_x \ 2x_1 \ + x_2 \ \ \ \ -- (1) $$ such that, $$ x_1 + x_2 \leq 2 \ \ \ \ -- (2)\\ -x_1 - x_2 \leq -4 \ \ \ ...
1
vote
2answers
68 views

Duals of Linear Programs

We are trying to find the dual of the following linear program. $$ \max_x \ ax_1 \ + x_2 $$ such that: $$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$ ...
1
vote
1answer
7k views

Finding dual of linear programming problem

I have to find the dual to this linear programming problem: Maximize $-15z-\frac{11}{20}w-3a-3b=-132+p$ subject to $y+9z+\frac{13}{10}w+3a-2b=12$ $x-2z-\frac{7}{20}-a+b=4$ ...
1
vote
0answers
63 views

Linear Programming- are my equations correct?

A dairy produces cheese, milk, sour cream, and yogurt. Suppose: Every 100 lbs of cheese requires 2 units of plant capacity, 3 workers, and 7 gallons of culturing additive, and gives $1,500 in ...
1
vote
0answers
37 views

Is the coefficient uniquely determined by the sign function?

Suppose $a\in R^p$, $b\in R^p$, and $||a||=||b||=1$, is it true that if $sign(a'x)=sign(b'x)$ for any $x\in R^p$, then $a=b$, where $sign(t)=1$ if $t\geq 0$ and $sign(t)=-1$ if $t<0$?
1
vote
0answers
58 views

How to solve linear system of equations in 1 and inf-norm?

I have the problem to find a linear program that is equivalent to solving the problem that finds a minimum for $||Ax-b||_1$ and $||Ax-b||_{\infty}$. We defined a linear program as follows: $min_{x} ...
0
votes
1answer
217 views

Maximize two-variable linear function

How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known ...
1
vote
1answer
51 views

Having trouble understanding this proposition from my textbook.

I'm seeing this perplexing proposition in my optimization textbook: Suppose an LP $$\max\{z(x)=\vec{c}^{T}x+\bar{z}:A\vec{x}=\vec{b},\vec{x}\geq\vec{0}\}$$ and a basis $B$ of $A$ are given. Then, ...
1
vote
1answer
786 views

travelling salesman understanding constraints

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
0
votes
0answers
56 views

travelling salesman [duplicate]

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
1
vote
1answer
43 views

Proving certificate of inequality

I have a question about proving the certificate of inequality in the given question: If there exists $y$ such that $y^T A \leq 0$ and $y^T b < 0$, then $Ax = b$, $x \leq$ 0 has no solution. I ...
0
votes
1answer
56 views

Inequality Constrained Optimization Problem

I am working on the question displayed below. I am not sure if I understand it correctly and I am looking for some input. So, I am asked Why is $x^*$ a local maximum for $f$ subject to the set ...
1
vote
0answers
42 views

On solving non-linear programming problem and the relevant software

I have a non-linear programming problem, in which all the inequality is linear and only the optimization goal is in a non-linear form. The problem is as following. $x_j$ is the variables and $a_{k,j}$ ...
1
vote
1answer
1k views

Number of subtrees of a tree

Define a subtree to be any connected subgraph of a tree. Prove that the number of subtrees of a complete binary tree is not polynomial in the number of nodes. Give an example of a class of trees ...
1
vote
0answers
226 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...