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

learn more… | top users | synonyms

0
votes
1answer
206 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 ...
0
votes
0answers
63 views

Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
0
votes
0answers
175 views

question on linear programming problems in three variables

maximize $3x+4y+2z$,subject to $x+y+z\le12$,$x+2y-z\le5,x-y+z\le2$ where $x,y\ge0$ then which of the following are true 1)the problem has more than one feasible solution. 2)the objective function ...
1
vote
0answers
35 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 ...
0
votes
1answer
127 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 ...
0
votes
0answers
38 views

Linear Programming - How do I format an if/else in an objective?

How can I write this trivial example as a valid linear programming problem? maximize: if x >= 0, 4x if x < 0, -3x subject to: x <= 5 x >= -6
1
vote
1answer
40 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
80 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
60 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
1answer
333 views

Shortest path problem dual formulation

For the shortest path problem, I know that the IP formulation is this: And now I am given that the corresponding dual problem is this: I tried to derive the dual formulation myself, the way I ...
0
votes
0answers
23 views

Calculating a 3d vector based on two functions based on time

I have an object who's position is defined by a 3d vector, startposition. I want to translate this object towards another position, endposition. At the same time, I also want to translate this ...
0
votes
0answers
31 views

Finding the dual of a linear program

I have an exam next week and I would like to make sure I am doing this problem correctly and I would also appreciate if somebody could explain to me the purpose of duality? What is the ultimate goal ...
0
votes
0answers
43 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 ...
0
votes
0answers
81 views

Proof of corollary of Farkas' lemma

I tried to prove the following lemma of Farkas' lemma: Given the system $Ax<b$, $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^m$, the system is infeasible iff there exists $\lambda\in ...
1
vote
0answers
13 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 ...
0
votes
0answers
28 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
18 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
53 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
658 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
40 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
32 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
36 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
97 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
47 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, ...
0
votes
1answer
128 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
43 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
41 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
41 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
35 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
278 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
150 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 ...
3
votes
0answers
160 views

The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that: For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex ...
0
votes
1answer
89 views

Linear Programming - Overtime restriction

hopefully I can get some help on this problem, it's got me quite stumped. I was given a linear programming problem with the goal of minimizing labor costs. The variables x_t represent the number of ...
1
vote
1answer
80 views

Binary constraint integer programming problem

Hi I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let x and y be integer variables bounded at 1000. How can you ...
2
votes
1answer
38 views

Whether a feasible set is empty?

Given $a\in \mathbb{R}^N$ with at least one positive entry, and a positive definite $N\times N$ matrix $A$, I would like to prove the following set is non-empty: $$S=\{ x\in \mathbb{R}^N : x\geq 0, ...
0
votes
0answers
26 views

Total unimodularity in quadratic programming.

I have a quadratic integer problem of the following form: \begin{align} minimize & \quad \tfrac{1}{2} x^T Q x + c^T x \\ subject \ to & \quad M x = 1 \\ & \quad x_i \in \{0, 1\} ...
1
vote
0answers
105 views

problem related to duality theorem in linear programming

Please help me to prove the above variant of the duality theorem. I am a masters student and linear programming is new to me. This question is a part of my assignment. I was not able to prove it.
0
votes
1answer
43 views

Conditions for a system to be solvable.

I have the following system of equations: $$\begin{aligned} \left\{\begin{array}{l} a+dz+cy+exy = 0\\ 10a+3bx-exy =0\\ -5a-dz = 0 \end{array}\right. \end{aligned}~~.$$ I would like to solve for ...
0
votes
1answer
22 views

have value of variable take on whether two other variables equal?

I'm having a hard time expressing something in a linear program I am writing. I have two variables a and b. I want the ...
1
vote
0answers
61 views

Area of a 2D convex polytope made of halfspaces

For a computer program I am attempting to solve the area of a convex polytope defined by a finite number of halfspaces. I understand that this forms a polygon and given the vertices of a polygon I am ...
1
vote
1answer
777 views

Linear Programming Inventory Problem

I'm still trying to get used to the nature of these problems and I'd appreciate some further explanation. ...
2
votes
1answer
575 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 ...
3
votes
2answers
652 views

Financial Linear Programming Problem

I'm very new at linear programming and I'm trying to figure out a way to approach this problem below: ...
0
votes
0answers
46 views

Existence of strictly positive solution

I have a linear system \begin{equation} \left[\begin{array}{c|c} A & \\ \hline I & I \\ \end{array}\right] \left[\begin{array}{c} x_0\\ x_1 \\ \end{array}\right] = \left[\begin{array}{c} ...
0
votes
0answers
28 views

How to do regression for an exponential model?

I have data in the form of: (x1, y1, z1 || t1) (x2, y2, z2 || t2) ... (xN, yN, zN || tN) Where (x,y,z) pairs are inputs, are t's are outputs. Using this data I ...
1
vote
0answers
564 views

Graphically solving a Linear Programming Problem?

I was given the following linear programming problem and have been asked to find all optimal solutions graphically. I am quite new to the subject, so please forgive my naivety. ...
0
votes
1answer
78 views

Intersection of Cartesian product and set - what is the meaning?

I came across the following two definitions in a book about Integer Programming: Definition 1.1 A subset of $R^n$ described by a finite set of linear constraints $P=\{x \in R^n: Ax \leq b \}$ is a ...
0
votes
2answers
64 views

How can I find the center of a region in a linear programming problem?

I have an optimization problem that in most respects can be very elegantly expressed via linear programming. The twist is that I don't actually want to minimize or maximize any of my variables; I ...
0
votes
0answers
36 views

Finding an optimal set of weights for combining correlated classifiers

In order to combine classifiers that are correlated with one another, I would need to solve the following optimization problem: Find a vector $\mathbf{w}$ that minimizes $\mathbf{w}^T M \mathbf{w}$ ...
1
vote
1answer
53 views

Containment of one convex hull in another

This question is related my previous question (Comparing two probability distributions) which are both related to my current research. Suppose we have two bounded convex hulls in $\mathbb{R}^n$ ...