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

learn more… | top users | synonyms

0
votes
2answers
29 views

Right coordinates of a slanting line when slope is zero and left coordinates never changed after transformation

I have a line in a program I am developing that I want to remove the slant (slope to zero) then get the new coordinates after transformation that removes the slope. This is how the line with the ...
1
vote
1answer
23 views

How to have just 3 result variables for this linear programming problem?

I have the following problem: +----------------------+--------------+--------------+----------+ | Process time (hours) | ...
1
vote
3answers
36 views

How to compute the projection of a polyhedron

Suppose that we have a polyhedron in $(x,y)$: $P=\{ (x,y) \mid A_1 x +A_2 y \leq b \}$ How can I find the polyhedron $P_x=\{ x \mid (x,y)\in P \}$? In other words, I would like to write $P_x=\{x ...
3
votes
2answers
55 views

In linear programming, how to check whether a convex polyhedron is contained in another

Suppose we have two convex polyhedra $P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$ and $P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$ Is there a way to check whether $P_1 \subseteq P_2$? I was ...
1
vote
1answer
16 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
0
votes
0answers
8 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
1
vote
1answer
27 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
1
vote
0answers
20 views

Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
0
votes
0answers
6 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
0
votes
1answer
47 views

Proof for the existence of basic feasible solution

I am trying to understand a proof for If F is non empty, the it has a BFS, where F = {x belongs to R: Ax=b, x>=0}, The proof goes likes this, first we collect all the indices(j) where xj > 0, then ...
1
vote
0answers
124 views
+300

Linear programming: constraints that depend on sign

Edit: following a comment, more detail and context, and removed lengthy confusing remains of previous edits I basically want to check whether there is a sequence $y_1,\dots, y_n \in (-\infty,0]$ that ...
0
votes
0answers
14 views

Is there any non-linear optimization technique whose running time depends on the diameter of the underlying polytope(induced by constraints)

It is well known that the running time of the simplex algorithm depends on the diameter of the polytope induced by the constraints. Is there any non-linear optimization technique that also has this ...
1
vote
1answer
29 views

The optimal function value in linear programming has analytic solution

Consider the following linear programming problem: $\min c'x$ subject to $Ax=b$ and $x\geq0$, where $A$ is $m\times n$ with rank$A=m$. The dual is $\max -b'v$ subject to $A'v+c=\lambda$ and ...
1
vote
0answers
21 views

Strong duality in conic programmig

Let $K$ be a convex cone which is not closed. The look at a probem of the from $$\min <C,X>, \,s.t\; <A_i,X>=b_i,\, X\in C.$$ Now suppose I now that both this program and its dual have a ...
0
votes
0answers
17 views

Find $U \subset D $ with $|U|$ minimal s.t $v = (1/2,1/2,1/2)$ belongs to the convex hull of $U$.

Consider the convex hull $\text {conv} \{e_1,e_2,e_3,(1,1/2,1/2),(1/2,1,1/2), (1/2,1/2,1)\}$ in $\mathbb R^3$ and the vector $v = (1/2,1/2,1/2)$. I want to compute $U \subset ...
1
vote
1answer
30 views

What is Weyl-Minkowski theorem?

The book I am reading 'Quantum Probability and Logic by I Pitowsky' has the following lines in the introductory chapter : Under the second description, a vector is an element of the polytope if ...
1
vote
1answer
37 views

smoothing linear graph but keep the spikes

how can I smooth a linear graph, but keep the spikes ? the graph are speed points per second, so it goes up and down frequently (like sinus curve), but sometimes there are spikes, like the speed ...
1
vote
0answers
19 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
0
votes
1answer
25 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
0
votes
0answers
19 views

Guaranteed solution to linear programming problem.

I have formulated a linear programming problem on the form \begin{align} &\min\limits_{x_1,\cdots,x_p}\sum\limits_{i=1}^p x_i \\ &\text{st. } \begin{split} Ax &= b \\ ...
0
votes
1answer
31 views

How to linearize this constraint a summation of a product of a integer with a binary

I have to linearize the following constraint, $$ \sum_{i \in V_C} \sum_{j \in V} \sum_{k \in K} y_{ik} \cdot x_{ijk\ell} \leq I_\ell \qquad \forall \ell \in V_D $$ where $y$ is a integer variable ...
1
vote
1answer
34 views

Check if feasible region is zero

Say I have a system of linear equalities and inequalities with integer coefficients in $n$ variables, and let $R^n$ be the space of all possible solutions. I know that $\vec{0}$ is a solution. Is ...
2
votes
0answers
36 views

Solve constrained system of linear equations from samples of a reference function

I have a system of $2n$ linear equations in $2n$ unknowns represented by the standard matrix equation: $$Ax = b$$ Where the solution vector $x = (p_1, ..., p_n, q_1, ..., q_n)$ represents real ...
0
votes
0answers
36 views

How to decide if solution exists for a linear equation?

I have $p$ ( $P_1,P_2...P_p$ ) positions and $n$ ( $N_1,N_2...N_n$ ) options to fill each position. Thus I have $n^p$ $p$ length strings. Each of these strings has a variable corresponding to them ...
0
votes
1answer
23 views

Understanding graphical meaning of tangent line in optimization problem

In a trivial optimization problem where dependent variable $y(x_b)$ is a curve, I'm seeking the value of $x_b$ that minimizes $\frac{y(x_b)}{x_b-x_a}$,where constant $x_a>0$. The solution has been ...
0
votes
1answer
38 views

Obtain Dual Solution from Primal problem using Simplex

I have been looking for an easy answer for this, but I wasnt able to find a strong answer. I will do it with an example: Given this Primal Problem: Max 14A + 7B 2A + 5B <= 18 5A + 2B <= 24 ...
2
votes
1answer
36 views

Split number into minimum sum components

I was wondering if there is an analytical solution for the following optimization problem? We have a given real number say $k$. It is needed to split $k$ into minimum number of real components, so ...
-1
votes
0answers
26 views

Maximum of function on field

My task is to find a maximum of function: $ f(x,y)=8x^2+2xy+2y^2-7x-4y-6 $ on filed: $ \{ (x,y); 9x^2+2xy+2y^2-5x-10y+12\ge0, x+6y\le14,2x+3y\le8,x\ge0,y\ge0 \} $ I started with just drawing out ...
1
vote
2answers
24 views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
1
vote
0answers
88 views

Primal and dual problem (Optimal solution) - Operations research

I'm currently studying operations research and I want to know and understand how we find an optial solution to the dual problem with minimum effort. Lets say we have this primal and dual problem: ...
0
votes
1answer
44 views

SDP relaxation of a non-convex quadratically constrained quadratic program.

I am very new to SDP and SDP solvers. I have a semi definite program of the following form $$\min_{x,X}\ Q\bullet X+c^Tx$$ $$\text{s.t. } Q^k \bullet X + (c^k)^T x =b^k , \ k=1,2, \dots,m \\ \quad ...
0
votes
0answers
22 views

When is a quadratically constrained quadratic program (indefinite objective matrix) unbounded?

I have a nonconvex QCQP of the form $$x^TQ_0x + c^T x$$ such that $x^TQ_1x+c_1^Tx=b_1$, $Ax=b$, and $l\leq x\leq m$ where $Q_0$ is indefinite diagonal matrix and $Q_1$ is positive semidefinite ...
1
vote
1answer
39 views

Using linear algebra (e.g. matrix) methods to solve a system of linear inequalities

Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is ...
1
vote
1answer
33 views

What to do about equality constraints in the Simplex Tableau method

The question I've got is: Maximise $$2x-y+3z$$ subject to $$2y+z \leq 2$$ $$x+y+z=4$$ $$x-2y+z \geq 3$$ $$x,y,z \geq 0$$ Using the Simplex Tableau method. I know that for $\leq$ constraints you need ...
2
votes
1answer
44 views

Minimize $w=9y_1+4y_2$ subject to linear inequalities

Minimize $w=9y_1+4y_2$ subject to : $4y_1+9y_2\geq 360$ $y_1+4y_2\geq 40$ $y_1\geq 0,~y_2\geq 0$
0
votes
0answers
19 views

Solving modular inequalities efficiently

Is there an efficient algorithm (polynomial in $n$ and $N$? What about subexponential in $n$ and $N$?) to find the set of all solutions of the equations \begin{eqnarray} a_1 < &k_1x& < ...
1
vote
1answer
38 views

Real linear combinations of intervals

Given intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1<1$ and a third interval $I=[-a,a]$ where $0<a<{1}$, when is there an $\alpha,\beta\in\Bbb R$ such that $\alpha I_0 ...
1
vote
2answers
58 views

Positive linear combinations of intervals

Given two intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1=1-a_0<1$ and a third interval $I=[-a,a]$ where $0<a<\frac{1}2$, when is there an $\alpha,\beta\in\Bbb R$ such that ...
1
vote
0answers
16 views

Linear diophantine inequality maximum

For an irrational $\xi$ and given bound $x$, find integer $a, b \ge 0$ maximizing $y = a + b\xi$ subject to $y \le x$. $\xi$ is a square root of an integer, but I guess it doesn't matter. It's ...
0
votes
1answer
40 views

Question about Game theory, matrix games.

Lets say you have a matrix game, where the matrix $A$ is the matrix, the column player can choose a column, the row player a row, and the row player pays the column player $A_{i,j}$. Assume we want ...
1
vote
0answers
23 views

Operations Research - complementary Slackness and optimal Solution

I have to verify the complementary Slackness, but I don't understand what it says and how to do it. Given: primal LP $$\begin{align*}\max&\quad c^tx\\\mathrm{s.t.}&\quad Ax=b\\&\quad ...
1
vote
1answer
41 views

Operation research - postoptimality analysis - find all solutions to problem

I'm currently learning Operations Research from "Introduction to Operations Research - Hillier". I know that somethimes a problem has many optimal solutions. For example in a two dimensional problem ...
0
votes
0answers
73 views

Is a polyhedron an affline manifold?

I was reading the definition of an affine manifold (https://www.wikiwand.com/en/Affine_manifold) and was wondering if a polyhedron is an affine manifold. Could you also provide any hints to the proof ...
0
votes
2answers
64 views

Linear optimization with “max” function (convex) constraint

I am working on a linear optimization problem which has a non-linear constraint. Suppose $x = [x_1 x_2]^T$, the problem is $$ \min_{x} \quad c^T x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ ...
0
votes
0answers
23 views

Extreme rays and lineality spaces

Consider the polyhedron $P$ defined as $$P = \{(x_1,x_2) \mid 4x_1 + 2x_2 \geq 8, \quad 2x_1 + x_2 \leq 8 \}$$ Then $P$ has no extreme points, as the corresponding matrix $A$ is given by $$A = ...
2
votes
0answers
32 views

What subjects properly belong in operations research as their “owning” discipline?

Warning: This is a soft question, hence I would make it a wiki-community post if I could. Operations Research involves a broad swath of disciplines, ranging from probability and statistics/stochastic ...
1
vote
1answer
30 views

Application Farkas Lemma

Let $A$ be a $m \times n$ matrix and $C$ a $k \times n$ matrix. Let $b \in \mathbb{R}^m$ and $d \in \mathbb{R}^k$. Show that exactly one of the following holds: a) There exists an $x \in ...
2
votes
2answers
55 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
1
vote
1answer
50 views

Characterize polytopes resulting from cutting a convex polytope by a hyperplane

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$. If a hyperplane defined by ...
0
votes
0answers
151 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...