Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
1answer
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}$$ ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
31 views

mixed-integer linear programming problem with non-linear restrictions

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 -...
0
votes
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 ...
0
votes
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"?
0
votes
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 ...
1
vote
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_3$ $x_4=5-x_1-2x_2$ $...
0
votes
1answer
19 views

Confusion about logical constraints

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 ...
0
votes
1answer
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 |...
1
vote
1answer
27 views

How to compute GCD with a MILP?

How would one formulate a linear optimisation program that computes the Greatest Common Divisor (GCD) of a set of $n$ numbers $\{a_1,...,a_n \}$? I can only think of a non linear formulation : $$ \...
0
votes
0answers
7 views

How does Geometric Duality Theorem work?

I got to the end of Geometric Duality Theorem which is $$\vec c = \sum y_i^*\vec \alpha+\sum w_j^*(-\vec e_j)$$ $\vec c$ = Original objective function being maximized. $y_i^*$ = Optimal solution to ...
0
votes
1answer
36 views

Objective function goodness if variable holds value above a given constant value

In a linear programming formulation, stating that a punishment is to be introduced in an objective minimize function if a variable $S$ holds a value above a given constant $K$ (in the below example, $...
1
vote
3answers
32 views

DNF constraint in integer linear programming

I have the following logical constraint which I am having difficulty to put into an equation (or set of equations): $((x = 1 \text{ AND } y = 1 \text{ AND } z = 1) \text{ OR } (w = 0 \text{ AND } s = ...
1
vote
1answer
43 views

Finding Farkas-type infeasibility certificate(s) for a simple problem in the standard primal conic form

Hi there some classmates and I are trying to understand a review question for a class on convex optimization. Consider the following programming instance: $\text {min} (x_3+x_4) s.t. -x_1-x_3+x_4=1,...
0
votes
0answers
31 views

Find the left and right derivatives of the trade-off curve at a breakpoint

For the region that is the set of pairs $(c^Tx,d^Tx)$ for all possible $x \in P$. We have the values $(c^Tx, d^Tx)$ at the extreme points of $P$. Points $(c^T x, d^T x)$ on the trade-off curve are ...
0
votes
1answer
25 views

Geometry of complementary slackness

Can someone help me understand what's going on in these notes? I don't understand what $e_j$ is supposed to be. How it $\alpha_1$ supposed to be orthogonal to $x_j$? Isn't $\alpha_1$ just a constraint ...
0
votes
1answer
21 views

Using binary variables to linearize a non-linear constraint in LPP

I have a constraint that makes the optimization problem nonlinear. The constraint of interest is: If (a-b)>=0 then c=(a-b) else c=0 where $a$, $b$ and ...
1
vote
1answer
51 views

Stiemke’s Theorem from Farkas' Lemma or Gordan’s theorem

Let me introduce some notations first. For any two points $x=\left(x_{i}\right)$ and $y=\left(y_{i}\right)$ in $\mathbb{R}^{n}$, we define • (1) $x\geq y$ if $x_{i}\geq y_{i}$ for $i=1,2,\cdots,n$ • ...
0
votes
0answers
20 views

Formulate as a linear program

I tried to formulate linear program by using the split method. I used two equations to show the linear program, but it seems not right. Can anyone give me some ideas how to solve this one? ...
0
votes
0answers
9 views

How to match my toy problem to primal dual explanatory formulas?

I am trying to understand weak and strong duality given a toy example LP program, which is to: maximize $m_D$D + $m_L$L s.t. 0.3 L + $\ \ \ \ \ \ \ \ $D $\leq$ 1 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...
0
votes
0answers
15 views

Locating extreme points graphically

$$\begin{array}{ll} \text{minimize} & x_1+2x_2+x_3\\ \text{subject to} & 3x_1+3x_2+x_3\ge3\\ &x_1+x_2+x_3\le2\\ & x_1,x_2,x_3\ge0\end{array}$$ For the given linear programming problem,...
1
vote
0answers
13 views

Defining binary variables on box constraints in mixed integer linear/convex program

I have $n$ variables $y_1,\dots,y_n\in\mathbb R$ with no upper bound and no lower bound. I want to define a binary variable $b\in\{0,1\}$ on condition that $b=1\iff \wedge_{i=1}^ny_i\in[0,1]$. How ...
0
votes
1answer
20 views

Prove that a line is a polyhedral set (can be made by a finite number of inequalities)

I know that to prove this I have to shown that a set of finite inequalities make a line in $\mathbb R^n$ that is $$ L = \{ x_0 + \lambda d : \lambda \in \mathbb R^n \} $$ But can we say a line ...
2
votes
0answers
42 views

Linearize if-then constraints

For continuous variables $x$ and $y$, the constraints are: ...
1
vote
0answers
27 views

Difficult discrete optimization “knapsack” type problem [duplicate]

Take a bounded domain $S$ in which an explosive device is located. A team is deployed to find and disable the device before time $t^{*}$, when it will explode. There are certain constraints in place....
1
vote
2answers
58 views

Why can't the dual and primal linear program both be unbounded?

I know if a dual is unbounded then the primal is unfeasible and vice versa, but I don't know why they can't both be unbounded. Is it because it's impossible to have linear constraints that are ...
0
votes
1answer
58 views

How can I solve this linear optimization problem?

I've come across a question which I was not able to solve I would appreciate if someone could help me out here. Q) Given the constraints, $$x \ge 0$$ $$y \ge 0$$ $$x + y \le1$$ which of the ...
0
votes
0answers
35 views

Both primal and dual have a unique optimal solution. Something wrong in the assumption/theorem/example?

The answer here mentioned a table from Sierksma's $\textit{Linear and Integer Programming: Theory and Practice}$, Volume 1, page 144. Both primal and dual are under standard form in table below (Here ...
1
vote
0answers
18 views

Upper bound of convergence of ellipsoid mathod

Actually, I am looking for a tighter upper bound for $(1+\frac{1}{n^2 - 1})^{n-1} (\frac{n}{n+1})^{2}$. It is easy to prove $(1+\frac{1}{n^2 - 1})^{n-1} (\frac{n}{n+1})^2 < e^{-\frac{1}{n+1}}$. ...
0
votes
0answers
16 views

Nested Linear Program [duplicate]

I have a linear program: minimise $f^T x$ with equality and inequality constraints. This does not have a unique solution, so I would like to find the solution of this that also minimises $g^T x$. ...
1
vote
1answer
158 views

Maximize scalar product with argument in bounded intersection of half spaces

Given $a,v_1,\dots,v_n\in \mathbb{R}^d$, $n,d\in\mathbb{N}$, how to compute a maximizer of $$ f: \begin{cases} \{x\in\mathbb{R}^d\vert\; \|x\|_2\le1\land \forall i\in \{1,\dots,n\}\;\langle x,v_i\...
0
votes
0answers
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 ...
1
vote
0answers
29 views

Perturbation approach to lexicography in Linear Programming

Consider a standard form problem, under the usual assumption that the rows of $\textbf{A}$ are linearly independent. Let $\epsilon$ be a scalar and define $$\textbf{b}(\epsilon)=\textbf{b}+\begin{...
0
votes
0answers
10 views

implementation of coppersmith matrix multiplocation

Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
1
vote
1answer
39 views

Rostering problem - variation of the post office problem

Suppose I have $N$ staff members. I employ each of them for 5 days during the week. Each day, $i$, from Saturday to Friday requires $s_i$ staff members. I wish to maximize the number of staff who ...
3
votes
0answers
36 views

On the Fundamental theorem of Linear Programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
0
votes
1answer
71 views

LP: multiple optimal solutions, unbounded, infeasible? [closed]

I'd like to ask the following question(s), to help me de-confuse things: $5y + x \geq 7$ $-3y + 4x \geq 5$ $4y - x \leq 15$ $y - 3x \geq -21$ $y - 4x \leq 42$ Given these constraints, what could ...
0
votes
1answer
15 views

Sensitivity Analysis. Does changing the coefficient in the objective function produce a different objective value?

Say the change in the coefficient is within the allowable increase or decrease. Can the objective value change? I'm reading that it doesn't change. But, say the simplex solves the problem and one of ...
0
votes
0answers
8 views

Maximizing throughput through correct ratios

I recently came across this interesting game where I have combined several different types of base stations together to produce a certain amount of energy. However, I believe there is a way of ...
1
vote
0answers
51 views

How to derive the Standard Dual using the definition embedded in the Von Neuman Primal and Dual?

Given von Neumann primal Maximize: $c^Tx$ s.t.: Ax $\leq$ b x $\geq$ 0 And von Neumann dual Minimize: $b^T y$ s.t.: $A^T$ y $\geq$ c y $\geq$ 0 How to derive the Standard dual from the Standard ...
3
votes
1answer
54 views

MILP for similarity

I have the following question and I'm not sure how to formulate it as a mixed integer linear programming problem (if possible): I have a set of products i (1..n) where I'm searching a similar product ...
0
votes
0answers
31 views

How to reformulate this optimization problem as a linear program?

Let $Ax \leq b$, $x \geq 0$ define the feasible region. Each constraint defines a hyperplane in $R^n$ and the distance from a point $\hat x$ to a hyperplane is $d_i(\hat x)$ = $(b_i - A_{i,*} \hat ...
0
votes
0answers
36 views

Maximizing a sum of minimums → maximizing a single minimum

Let $\Delta_n$ be the standard simplex. Does there exist a function $$f : \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n} \rightarrow \mathbb{R}^{m \times n}$$ such that $$\operatorname*{...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
1answer
63 views

The fundamental theorem of linear programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
1
vote
0answers
40 views

$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 ...