Questions on linear programming, the optimization of a linear function subject to linear constraints.
0
votes
0answers
19 views
Nash Equilibrium of 2-players game
I have a rather interesting exercise in Game Theory.
Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 ...
0
votes
0answers
19 views
Linear optimization: doubt about the Big M method
I'm trying to implement the Big M method on javascript, but I have some difficulties to completelly understand it.
I'm reading this explanation.
However, I get stuck on the final step when ...
0
votes
0answers
18 views
Existence of a Linear Optimization Problem
I am working on a linear static optimization problem. I found a solution to the problem. However, I want to formally check the solution existence. I tried some methods but I don't know if it is enough ...
1
vote
2answers
34 views
Changing the Parameter in Linear Programing, Changes the Solution to the Dual
Consider a linear optimization problem such that the RHS of the constraints depends on a parameter $a$, as in $$Ax=b+ae_j$$
Here $e_j$ is a unit vector in the direction of $x_j$.
Suppose that for ...
0
votes
1answer
24 views
linear programming constraint for conditional
I having formulating the following (what should be fairly simple) ilp constraint. Basically let $p$ be a binary variable and $s$ be an integer that is greater than or equal to 0.
The constraint is ...
0
votes
1answer
17 views
Least Square Method for solving system of equations
So I am following this procedure through MathCad, but when I get to the bottom of page 3, he says I can use a built in command, which he doesn't include. So I am trying to figure out how to solve ...
0
votes
0answers
55 views
Its just one point… How do I find it?
Okay so here is the deal...
I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$)
and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$
where $0 \le ...
1
vote
1answer
10 views
Characterization of Subset Sum via Linear Programming
I have a sample subset sum problem.
Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$
Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$
such that
0 <= $y_1$ <= 1
0 <= ...
0
votes
0answers
41 views
correctness of this Linear Programming formulation
Problem: A Company that produces a product has 2 seats A and B and the cost of production of the same product for seat A and seat B is the follow:
The company has 2 customers C1 and C2 ...
1
vote
0answers
16 views
Problem generating random vectors with a randomized linear programming with equality constraints (weird clustering)
Summary
For simulation problems, I need to be able to generate large numbers of random lists of numbers, say $x_1, x_2, \dots, x_n$ (where $n \approx 1000$), subject constraints similar to what one ...
0
votes
1answer
26 views
Find min/max $\|x\|_{1}$ of a linear system of the form Ax = b with simplex method
Let $Ax = b$ be a system with $a_{i,j} \in \{0,1\}$ and $b_{i} \in \{0,1,2,3,4,5,6,7,8\}$. The constraints on x are $x_{i} \in \{0,1\}$.
We suppose that the system admits at least one solution.
...
0
votes
1answer
37 views
Linear optimization problem
$\mathbf{Problem}$: Varying amount of goods have to be transported along three paths: A,B,C; 780, 2425, 1000 units respectively. Three trucks are available: 1.5, 3.5 and 5 tonne capacity. First two ...
0
votes
0answers
27 views
Dictionaries which share Basis, are they the same?
I am (trying) to understand the following theorem:
If the simplex method does not terminate, it must cycle
Now I know that two dictionaries with the same $\mathcal{B}$ have to be encountered ...
0
votes
1answer
60 views
Optimal Solution Set To Linear Programs
I have the following assignment question, and I am not quite sure how to proceed.
Q: Consider the following LP (P): $\max\{{c^Tx:Ax=b, x \geq 0}\}$, where $A$ is an $m$ by $n$ matrix. Prove or ...
0
votes
1answer
46 views
Move to LP corner point from feasible solution in plane.
I have a feasible solution for a linear programming problem that is not necessarily a corner point. What algorithm can I use to move to a corner point feasible solution from this solution, so that I ...
0
votes
0answers
18 views
Solvability of overdetermined system of linear equations with constraints on coefficient matrix
Consider the following overdetermined system of linear equations:
$\quad \quad
Ax=\left[\begin{array}{cc}
a_{1} & b_{1}\\
a_{2} & b_{2}\\
\vdots & \vdots\\
a_{m} & b_{m}\\
1 & 1
...
2
votes
0answers
36 views
Explicitly solving linear programming problems
Linear programming problems generically involve the use of a repeated algorithm to solve. Is there a reason they can't be solved algebraically/formulaically?
Ex:
Minimize x1 + x2 + x3....
x1, x2, ...
0
votes
0answers
8 views
Formulating square packing as a form of optimization
I was looking at square packing problem which is defined as:
Given a number N... Find the smallest square that can pack N unit squares
Each square can be associated with a 3 dimensional point ...
0
votes
0answers
15 views
general tips on how to attack linear programming problems
Now for my exam in linear programming I will of course have to be able to translate a given problem into decision variables and an objective value.
But my problem is that most of the time I don't ...
1
vote
0answers
28 views
Linear Program for Correlated Equilibrium
I try to solve an exercise in Game Theory so far with no success. I would appreciate if could help me.
Exercise. Consider an $n$ person game where each player has $2$ strategies. For this problem, ...
1
vote
0answers
30 views
Determine the values of $a,b,c,d$ and $e$ for a convex, piecewise function
Consider the following Linear Programming problem
\begin{align}
z(\lambda)=\max(1+3\lambda)x_1+(3+2\lambda)x_2 & \\[8pt]
-x_1+x_2 & \leq 1\\[8pt]
x_2 & \leq 2\\[8pt]
2x_1+3x_2 & \leq ...
1
vote
1answer
47 views
Linear programming lemma
As part of a review of some famous proofs in Hypergraphs matching I ran into this lemma in Linear programming that I am having difficulty showing (or finding an existing proof online):
Let ...
1
vote
1answer
26 views
Linear Programming - values of x and y yielding maximum values for the following problem:
I found the following linear programming question in a past exam paper while preparing for an upcoming exam:
"The daily production of a sweet factory consists of at most 100 kg chocolate covered nuts ...
1
vote
1answer
75 views
Integer linear program for Final Exam Schedule Problem
I am studying for my exam of linear programming and came across the following optimization problem:
The set of all courses is partitioned into 21 groups. For each group, each student is enrolled in ...
0
votes
0answers
24 views
Integer linear programming, energy constrained max-flow problem, column generation
We have graph $(V,A)$, $V$ is teh set of nodes, $A$ is the set of arcs. There is a source node $s \in V$ and a sink $t \in V$. Each node $i$ has a battery with capacity $E_i$. Sending flow on arc ...
3
votes
2answers
36 views
Very symmetric convex polytope
Let $C_n$ be the convex polytope in ${\mathbb R}^n$ defined by the inequalities
(in $n$ variables $x_1,x_2, \ldots ,x_n$) :
$$
x_i \geq 0, x_i+x_j \leq 1
$$
(for any indices $i<j$).
Denote by ...
0
votes
0answers
16 views
Network flow problem with s-t flow and s-t cut
We have a directed graph $G=(N,A)$ with set of nodes $G$ and set of arcs $A$. The capacity function is $c: A \to \mathbb{R}_+$. We have supply node $s$ and sink node $t$. Let $f$ be a $s$-$t$ flow, ...
1
vote
1answer
33 views
Farkas' lemma application
Farkas' lemma: Let $A$ be $m \times n$ matrix and $b \in \mathbb{R}^m$ $m$-dimensional vector.
Then, exactly one of the following holds:
(a) there exists some $x \in \mathbb{R}^n$, $x \geq 0$, such ...
0
votes
0answers
20 views
Least square distance between matrices under linear constraints
I have got a set of $n$ elements and a square matrix
I = $
\begin{bmatrix}
I_{11} & I_{12} & \dots & I_{1n} \\
I_{21} & I_{22} & \dots & I_{2n} \\
\vdots & \vdots & ...
0
votes
0answers
22 views
Semi definite programming for MAX-2-SAT
I didn't understand something in formulating this program, to a vector program.
Assume that each clause is of the form $C_{j}=\left(u_{j}\lor v_{j}\right)$ where $u_{j},v_{j}$ are literals (meaning, ...
1
vote
1answer
33 views
formulate this scheduling problem as linear programming problem
Sorry if this very silly, but i am something new to optimization theory:
We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
1
vote
0answers
40 views
Formulate the dual problem in matrix notation
Consider the standard LP problem $\max\{c_0^Tx : A_0x \leq b, x\geq 0\}$. After introducing the slack variables this problem can be written as
$$\max c_0^Tx$$
$$s.t. Ax = b$$
$$x\geq 0$$
...
0
votes
0answers
18 views
From a primal problem optimal solution to a dual problem optimal solution
Having this linear programming problem:
$minimize$ $ 2x_1 + 9 x_2 + 3x_3$
subject to
$-2x_1 + 2 x_2 + x_3 ≥ 1$
$x_1 + 4 x_2 - x_3 ≥ 1$
$x_1, x_2, x_3 ≥ 0$
and its dual
...
0
votes
0answers
26 views
Proving minimax theorem
So zero sum games can be modeled as follows:
Player 1:
maximize v
s.t.
ve <= Px
ex = 1
x >= 0
Player 2:
...
1
vote
0answers
40 views
Solving linear equation with some conditions
Consider the equation $y=af+bg+ch$ where $a+b+c=1$ and $a,b,c$ are between 0 and 1. y,f,g,h are vectors with the same size and a,b and c are parameters that must be constant values. How can I solve ...
2
votes
2answers
73 views
How to convert a matrix of decision variables in a vector for solving a linear programming problem?
I want to solve this problem :
find the minimum of the function F = sum(sum(A - Q*E)),
were A is an i x j matrix, Q is an i x k matrix and E is an k x j matrix. This is basically a least absolute ...
1
vote
1answer
31 views
Determining the convex hull of the union of two polyhedra
I'm doing an introductory course to linear programming and I'm working through some exercises to prepare for the final exam, I'm stuck on an exercise and I would really appreciate a hint:
Let ...
1
vote
0answers
20 views
How to visualize duality
In My course of linear programming we are given the definition of a primal/dual problem. However I cannot really get my heard around what it actually is? It helps us in later exercises. Are we ...
1
vote
1answer
31 views
Compute $v,W,k$ such that the following is true
$$
\left\{ x \in \mathbb{Z}^4 |
\begin{pmatrix}
5 & 3 & 7 & 0 \\
2 & -4 & 6 & 5
\end{pmatrix}
x =
\begin{pmatrix}
5 \\0
\end{pmatrix}
\right\} = \left\{ v + Wy \ | \ y \in ...
1
vote
1answer
36 views
How to construct an LP problem that makes a (partial) theorem fail?
I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem.
The theorem is Theorem ...
1
vote
0answers
44 views
Model Linear-Programming Problem
A factory needs to complete $n$ jobs by using $m$ machines. To complete each job $j, j=1,\dots,n$, an amount of $r_j\geq 0$ processing units is required. Each machine $i$ has a processing speed ...
0
votes
0answers
25 views
finding the optimal solution of the dual problem
This is homework.
I have the following dual problem, formed by using lagrangian relaxation.
$$
\begin{align}
min & \{&89y_1 +&3y_2 +&10y_3\}\\
s.t.& &3y_1+& &y_3 ...
0
votes
0answers
23 views
Prove that this linear programming problem has the following dual problem
Consider the following Linear Programming problem:
$$max \sum_{j=1}^nc_jx_j$$
\begin{align} s.t. \quad
\sum_{j=1}^na_{ij}x_j=b_i \quad 1\leq i\leq m\\
x_j\geq 0 \quad 1\leq j \leq n.\\
...
0
votes
1answer
46 views
Construct a linear programming problem for which both the primal and the dual problem has no feasible solution
Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution.
For ...
0
votes
0answers
34 views
Basic Solutions in Linear System
I am studying Linear programming and we have just learnt about Basic solutions. I know that a basic solution (x) should have 2 properties:
should indeed be a solution. $Ax = b$ should hold.
for some ...
1
vote
2answers
39 views
Linear programming problem neither max nor min
Heres the actual question:
television provider broadcasts two movie channels, A and B. Channel A broadcasts 1 romantic
movie, 3 action movies and 3 comedies per month at a cost of 50 Euro. ...
1
vote
1answer
18 views
Minimizing deviations from threshold value from a given group of numbers
Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
0
votes
1answer
44 views
Partial linear relaxation yields an integer solution
Consider a binary integer program
\begin{align}
\min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\
\mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
4
votes
0answers
106 views
Can you verify a Wikipedia article I wrote? [closed]
I'm a college student in a country of Serbia (South East Europe) studying IT and CS, and for one of the courses I have an asignment to do. The assignment is to make a good, standards following, ...
0
votes
1answer
24 views
How to linearize the following LP
I want to minimize $|d_1-d_2|+e1+e2+e3$ where $d_1,d_2,e_1,e_2,e_3>=0$ and $|.|$ denotes the absolute value, for some linear constraints. Is there any way I can linearize the objective function?
