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

learn more… | top users | synonyms

1
vote
0answers
22 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
33 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
53 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
20 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
0answers
20 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
63 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 ...
2
votes
2answers
510 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
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 ...
1
vote
1answer
62 views

Reduced Cost in Network Simplex Algorithm

On page 5 of the slide, [T]he reduced cost of a non-basic arc $(i, j)$ is the sum of the costs of the arcs forming a cycle with $(i, j)$ in the current tree solution. Why is that the case?
2
votes
0answers
50 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
38 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 ...
1
vote
2answers
50 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 ...
2
votes
1answer
40 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 ...
0
votes
1answer
46 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 ...
3
votes
2answers
2k views

Simplex method : Duality by Bazaraa

I use great textbook (Linear Programming and Network Flows by Bazaraa II ed) On the page 240 the author states that for every primal problem, regardless of it's type (canonical or standard), dual ...
0
votes
1answer
62 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 ...
1
vote
0answers
173 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: ...
3
votes
1answer
205 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
1
vote
1answer
157 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
1
vote
1answer
57 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
28 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
58 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$
1
vote
1answer
81 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
43 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 ...
1
vote
1answer
39 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 ...
2
votes
0answers
44 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
2answers
61 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 ...
0
votes
1answer
50 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 ...
0
votes
2answers
76 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 \\ ...
1
vote
1answer
48 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 ...
1
vote
0answers
17 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 ...
1
vote
0answers
26 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 ...
0
votes
0answers
74 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
0answers
27 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 = ...
0
votes
0answers
163 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 ...
2
votes
2answers
57 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
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
1answer
53 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
1
vote
1answer
78 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
2
votes
0answers
16 views

Linear Programming 3 decision variables (past exam paper question) [duplicate]

This is an exam question I was practising. I have the general understanding of Linear programming, but how would you go about finding the Decision Variables, Objective function and Constraints for ...
1
vote
1answer
24 views

Simplex Method issues solving this problem

I have an exam coming up so I have been going over math questions in my textbook to practice the simplex method. I ran into an issue with questions like this one, and also any that have more ...
1
vote
1answer
67 views

Solving an integer linear programming problem without a graph

I am new to linear prorgramming and so far I have been solving LP problems with the help of a graph solution. However, when there are more than 2 variables obviously I can't plot them on the graph. ...
0
votes
0answers
40 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
1
vote
2answers
2k views

Help with binary variable

I need to make a constraint for the following condition: Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all. I have defined Y1, Y2, Y3, and ...
1
vote
1answer
42 views

Expressing problems in canonical form for solving with simplex

The Picnic Hamper Company has a store containing 10,000kg of nuts, 4000 packs of smoked salmon, 2000 bottles of wine and 1500 Victoria sponges. It intends to use these goods to make up three different ...
2
votes
3answers
60 views

Least Squares method and Octave/Matlab [closed]

I'll try to be as clear as possible so that you understand what I'm trying to do and can help me I have twelve pairs of data $(x_1,y_1),....,(x_{12},y_{12})$ and from this data we established a model ...
0
votes
0answers
66 views

Solving constrained linear programming problem

For the variable $t$, problem is to find best multipliers $k$ which minimizes the objective function. Time: $t_1$, $t_2$, $t_3$,... given in input Multiplier $k_1$, $k_2$, $k_3$,... (These are ...
0
votes
0answers
36 views

Necessary condition for existence of a positive solution of a linear system

I would like to know what are the necessary conditions of existence of a positive (componentwise) solution of the system : Ax=b, with A a square ...
8
votes
2answers
5k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...