# Tagged Questions

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

9 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 ...
31 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 ...
13 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 ...
40 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 ...
13 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 ...
38 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 . ...
7 views

### Using duality to prove non-cycling in Bland's pivoting rule

The professor in my Liner Programming course was recently discussing Bland's pivoting rule and mentioned that it can be shown using duality that the rule prevents cycling in the simplex method. I'm ...
16 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$ ...
37 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 ...
16 views

### Is this matirx totally unimodular? [closed]

I think this matrix is totally unimodular but how do I show that it is? ...
33 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 ...
22 views

27 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. ...
38 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 ...
27 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 ...
38 views

### Getting stuck in a loop when trying to solve LP with simplex method [closed]

I'm trying to write a simplex algorithm in java for an assignment. My code works for certain inputs, but quite often, the algorithm gets stuck in a cycle, recalculating from tableau state A to state ...
21 views

### Linear optimization/programming? [closed]

I need help finding the linear programming formulation and optimal solution. Thanks!
22 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 ...
20 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 ...
17 views

24 views

### Progressive Solving of Linear Programming Problem

Suppose you solve a linear optimisation problem: **Maximize:** 2a + 3b + 4c **Subject to:** 3a + 5b + 2c <= 5 8a + 3b + 1c <= 8 C = 0 And then remove the C ...
72 views

### Solve $\max_{x_1,x_2,x_3} \{ \alpha \min \{a x_1,b x_2,c x_3\}\}$ s.t. $p_1 x_1 + p_2 x_2 + p_3 x_3 = w$

Consider the objective function \begin{equation*} f(x_1,x_2,x_3)=\alpha \min \{a x_1,b x_2,c x_3\} \end{equation*} where $\alpha, a, b, c \in \mathbb{R}$ are arbitrary constants. We wish to maximize ...
12 views

### Construct a Primal-Dual Linear Programming Pair such that the feasible domains of both are non-empty and bounded

I've been studying duality and I've been trying to construct primal-dual pairs that satisfy specific properties. I'm wondering if they can both have bounded feasible domains?
176 views

### How many beers can be bought (using exchanges) starting with $n? This is an extension/generalization of this question. Suppose$2 can buy 1 bottle of beer. 4 bottle caps can be exchanged for 1 bottle of beer. 2 empty bottles can be exchanged for 1 bottle of ...
I'm trying to follow the syllabus of 6-251j at MIT OCW and need to understand whether I'm doing fine with the exercises. This is what Ex. 1.11 says: Suppose that there are $N$ available ...