# Questions tagged [linear-programming]

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

3,561 questions
Filter by
Sorted by
Tagged with
28 views

### Shortest path with multiple source and multiple sink

Let $G = (V,A)$ be a directed graph with arc costs $c_{ij}$, for $(i,j) \in A$. Suppose that you want to find a shortest path in $G$ that can start at either of the nodes $s_1$ or $s_2$ and can ...
45 views

### Absolute value minimization with non-convex constraint

I want to solve the following optimization problem in $x\in\mathbb{R}$ $$\begin{array}{ll} \text{minimize} & |ax+b|+|cx+d|\\ \text{subject to} & x \in [x_1,x_2] \cup [x_3,x_4]\end{array}$$ ...
38 views

### How to show that this set is closed?

Consider the set of points $$O = \{ x \in P \mid \alpha^* = C^T x \}$$ where $P \subseteq \mathbb R^n$ is a closed convex set, $C \in \mathbb R^n$ and $\alpha^* = \min \{ C^Tx \}$. Then, $O$ is closed ...
30 views

### Is this a linear constraint?

I'm wondering, is the following a linear constraint $$x + ry \geq 12 , \quad r \in [2, 3]$$ $$x,y \in {\rm I\!R}$$ I don't think it is, because it's not defined everywhere where x and y are. If ...
31 views

I'm trying to maximize this problem using MILP (mixed-integer linear programming). K represents constant values and decision variables are x1, x2 , x3(binary); $\max \sum_{i = 1}^{p}(x2_{i}\cdot k -... 0answers 78 views ### Formulate a linear program to minimise the total salary paid to professors making sure they sign up each year This link is an image of the question: The Dean of Physical and Mathematical Sciences of ABX University is drawing up her plan for the full time professor needs for the next four years. After ... 1answer 26 views ### In linear programming, what is an “optimal basis”? I keep seeing the term "optimal basis", but can't see an explicit definition anywhere. I suppose it means something like "the basis at an optimal solution"? 0answers 37 views ### solve the LLP. optimum value of the objective function, the basic feasible optimal vector Fruity Ltd manufactures an orange flavoured soft drink called OrangeFiZZ by combining orange soda and orange juice. Each ounce of orange soda contains 0.5 oz of sugar and 1 mg of vitamin C. Each ounce ... 0answers 24 views ### Find all the optimal solutions to the dual problem of this maximization problem This was posted a year ago, but no answer was posted. Here's my crack at it and hopefully I can get some critique because I want to get better at this. Maximize$z=-3x_1-x_2-x_3x_4=5-x_1-2x_2...
19 views

In my linear programming course, when discussing logical constraints, my notes read: If item $i$ is selected, then item $j$ is not selected, and the constraint reads: $x_i + x_j \leq 1$. I am ...
22 views

### How to transform absolute values in the objective function of a linear program?

Referring to this, in the Numerical Example, clearly $x_3$ is useless (looks like the page is not well maintained). I find the explanation confusing though. If I simply have an objective function min |...
27 views

70 views

### Does $A x > b$ have a solution?

Formulate a linear program that will determine whether or not $Ax>b$ has a solution, where $A$ is an $m \times n$ matrix and $b$ is an $m$-vector. We were told to use Farkas Lemma, but are not ...
29 views

64 views

### How to reformulate this model in standard form?

How to reformulate the following linear programming model into an equivalent model that is a linear program in standard form?: Maximize $-e^T |x|$ subject to $Ax \geq b$ x unrestricted where e = (1, ...
37 views

### Converting minimizing wasted string when partitioning 200cm into 90,70 and 50cm to Linear Programming problem

Say you have 3 products that require x amount of string to make: Product A: requires 90 cm of string Product B: requires 70 cm of string Product C: requires 50 cm of string String comes to you from ...
18 views

### Rigorous global optimization

The work by Thomas Hales (see enter link description here) before the formal proof solves a number of global optimization problems that need to be solved exactly. The strategy relies on following ...
### $P:=\{x\in\mathbb{R}^n:Ax\ge b\}, S:=\{c^Tx:x\in P\}$, prove that $S$ is a convex set
Consider the LPP of optimizing the objective function $c^Tx$ over the polyhedron $$P=\{x\in\mathbb{R}^n:Ax\ge b\}$$ Show that the set $$S=\{c^Tx:x\in P\}$$ of values of the objective function over all ...