# Tagged Questions

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

21 views

### Finding a suitable solver

I have a problem finding a solver that can solve a mathematical programming model with a quasi quadratic object function. I have tried some commercially available quadratic and non-linear solvers, but ...
33 views

### How to find extreme directions?

objective:min $−3x_1−2x_2−x_3$ The set is : $X=\lbrace (x_1,x_2,x_3):2x_1+x_2-x_3\le2; x_1,x_2,x_3\ge0 \rbrace$ Attempt: $2d_1+d_2-d_3\le0$ (a) $d_1+d_2+d_3=1$ and $d_1,d_2,d_3\ge0$ Since from (...
41 views

### Solving a modified numerical heat equation

I'm having a bit of trouble finding a good numerical form for this modified version of the heat/diffusion equation and I was just wondering if I am tackling this question the correct way. Firstly, I ...
95 views

19 views

### Relationship between Primal and Dual problems

Considering the following program: \begin{cases} \max & 8x_1 & + 3x_2\\ & x_1 &-6x_2&\ge2\\ & 5x_1 +&7x_2&=-4\\ &x_1&&\le 0\\ && x_2&\ge 0 \end{...
19 views

### What is the initial tableau for simplex method with big M method for this problem?

I have an optimization problem with formulation: min f = x1+x2+x3 subject to: x1+2*x2+x3=8 2*x1+x2+x3=12 x1,x2,x3>=0 I should solve it by Big M method. For this I added two extra variables (a1,...
43 views

### Dual and Primal in Linear programming.

I am stuck on these two questions. I have tried to get information on these but what am getting is not even close to the questions. What can you say about the dual if you already know that : an ...
92 views

### What programing language Thomas Hales used in 1998 to prove Kepler’s conjecture?

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal ...
16 views

### Primal + Dual relation with Complementary Slackness.

If let's say there exist an optimal solution to the primal with $x_1 = 0$, what can we deduce about the dual? Here is my attempt to answer this particular question: Since there exist an optimal ...
21 views

### Remove redundant vertices in graph

My group is currently working on a project concerning Combinatorics: Graph-theory and optimization. In the project we need to find the optimal sales strategy to the following problem. Background ...
35 views

### Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
36 views

### An polynomial time algorithm to solve LP

Is there a polynomial time algorithm that gives the extreme point as output for which objective function is minimized/maximized ? I am not looking for any solution that minimizes/maximizes the ...
28 views

### Optimization using Linear programming

I have a set of machines in the cloud (charged hourly). Some of them have been running already. I want to add and remove these machines dynamically in the cloud. Each type of machine has a ...
25 views

18 views

### How to calculate the Bouligand derivative (B-derivative)

Let $H(x)=\min (f(x),h(x))$ where $f$ and $h$ are continuously differentiable functions from $\mathbf{R}^n$ to $\mathbf{R}^1$. The Bouligand derivative (B-derivative) $BH(z)$ at $z$ of $H$ is given ...
28 views

### How does changing the cost vector of a primal linear programming problem affect the solution of the dual?

Say the linear program: max $p'x$ such that $Ax=b$ and $x \geq 0$ is primal and dual feasible, and $\bar{u}$ is known to be the optimal solution to the dual. If the $\lambda \ne 0$ times the $i$th row ...
35 views

### Formulating the Dual of a linear program

I have a linear program: Maximize 18x + 12y subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0 I have found ...
11 views

### Use duality to solve LPP

I have some confusion regarding the solution of LPP by solving its dual. I have drawn the following table to indicate possibility/possibilities. I have made an attempt to correlate the two columns but ...
19 views

### Unbounded solution of LPP

In connection with LPP, what is meant by 'unbounded solution' and 'unbounded objective function'? Are they same or they are distinct concepts?
152 views

### Why can/should we use 5 instead of 10?

Problem: A pharmacy has a uniform annual demand for 200 bottles of a certain antibiotic. It costs \$10 per year for a storage place for one bottle, and$40 to place an order. How many times during ...
23 views

### Conditionals without use of binary variables

I would like a linear programming expression that has to satisfy certain criteria without the use of binary variables. i.e.: Let 0 <= B <= C However, if ...
18 views

### Graphical solution of lpp

I need to solve the following LPP using graphical method Min $z=-2x_1+x_2$ subject to $x_1+x_2 \geq 6$, $3x_1+2x_2 \geq 16$, $x_2 \leq 9$, $x_1, x_2 \geq 0$ The common feasible region is ...
27 views

### Mathematical formulation of LPP

I want to formulate the following problem as a LPP A manufacturing company produces two types of computer monitor- color and monochrome. The data in the manufacturing context are as follows 6 days ...
29 views

10 views

### Estimate size of smallest solution to linear program

I have a linear program: a system of linear inequalities of the form $$Ax \le b, \qquad x \ge 0.$$ where $x \in \mathbb{R}^n$, $b \in \mathbb{R}^m$, and $A$ is a $m\times n$ matrix. I am looking ...
49 views

### Prove a set is convex

I have problems to make proof for below two statements. Let Γ be the LP max cᵀx s.t. Ax ≤ b. prove that set of all optimal solutions to Γ is a convex set Let x' be a basic feasible solution of Γ. ...
55 views

### Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
37 views

20 views

### Formulation of LP Problem with three constraints

I have an assignment in a Linear Programming course that I'm having some trouble with understanding. The problem is, or should be, pretty simple, but for the life of me I can't seem to be able to get ...