Questions tagged [linear-programming]

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

1,442 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
1answer
131 views

Semi-Infinite Linear Programming: Why is the infimum attained?

I have an optimization problem of the following form: $$\min c^T \lambda\\ \text{s.t. } f(x)^T \lambda \ge g(x) \text{ for all } x \in E,$$ where $E$ is an arbitrary set, $c \in \mathbb{R}^n, f \...
0
votes
0answers
2k views

What are canonical vectors?

I just begun with linear programming. Given an objective function $z$ and certain restrictions defined by $Ax = b$, we got to find the values necessary to maximise or minimise that function's output......
0
votes
0answers
53 views

Linear programming problem - do we have enough data here?

I am to solve a following problem, but it seems to me that it is ill-formulated, i.e. there's not enough data. Am I right? If not what would be the mathematical model for it? Every coffee table ...
0
votes
1answer
150 views

Linear Inequalities - Allocation Problem

The problem at hand can be summarized as follows: we have to allocate a ressource to $n$ production units. The allocation to production unit $i$ is $x_i$. Each of the production unit will produce at ...
0
votes
0answers
511 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
0
votes
1answer
176 views

Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
0
votes
1answer
100 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements $...
0
votes
0answers
712 views

linear program-Simplex method-Dual problem

At an exercise I am asked to solve a linear program using the simplex method(in Matlab).Then I have to formulate the dual of this problem and read off an optimal solution of the dual problem from the ...
0
votes
1answer
148 views

Simplex Algorithm

I'm currently trying to implement the (revised) Simplex Algorithm, but according to my notes the LP in standard form $\left( Ax = b, x \geq 0 \right)$ with $A \in \mathbb R^{m \times n}$ has to have ...
0
votes
0answers
39 views

How to check if steepest gradient method will converge?

So I have this function $ f(x,y) = x^4 - 2x^2 +x + 4y^2 $ and I want to know if the steepest gradient method will converge if I pick an arbitrary point and apply said method. My initial thought ...
0
votes
1answer
146 views

How to check linear independence

How can I check the linear independence of my variables? I have this system $Ax=b$ where $A$ is a $N \times 4$ matrix. I want to check the linear independence between the 4 variables in matrix $A$.
0
votes
0answers
28 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
0
votes
1answer
133 views

Inequality Constrained Optimization Problem

I am working on the question displayed below. I am not sure if I understand it correctly and I am looking for some input. So, I am asked Why is $x^*$ a local maximum for $f$ subject to the set of ...
0
votes
1answer
34 views

have value of variable take on whether two other variables equal?

I'm having a hard time expressing something in a linear program I am writing. I have two variables a and b. I want the ...
0
votes
0answers
32 views

Vertex Set Optimization

I have the following problem: Min $c^Tx$ Subject to: $Ax = b$ $x >= 0 $ Where A is an M x N matrix: But rather a single solution I would like to know the first K best solutions where $1<= ...
0
votes
1answer
162 views

Clarification needed for this linear programming problem

I am stuck on the following problem: I have got only confusion over option (1). The options (2) ,(3) are correct and option (4) is wrong. But how can I check whether the problem has more ...
0
votes
0answers
189 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 ...
0
votes
1answer
85 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
46 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
161 views

Show using duality that exactly one of the following systems has a solution

(I) $Ax=b$ ; $0≤ x ≤e$ (II) $uA +v ≥0 ; ub + ve = -1 ; v ≥ 0$
0
votes
1answer
774 views

Bounded and Feasible of Linear Program?

I have a question on usage of terminology in Linear programming. Why do we have terms like "If an LP is bounded and feasible, then..." My confusion is, if a Linear program is bounded then it has to ...
0
votes
0answers
248 views

linear equations with inequality constraints

The problem is, given a set of linear equations $Ax=b$ such that the system is under-determined, and a set of linear inequalities $Cx\geq 0$, find a solution for the system. Does anyone know a general ...
0
votes
1answer
97 views

Just formulate linear program

A company produces fragrances $A$, $B,$ and $C$. There is virtually unlimited market demand for these. Fragrance $A$ sells for \$$10$ per gallon, $B$ for $\$56$ per gallon, and $C$ for $\$100$ per ...
0
votes
0answers
49 views

Uncertaint linear program

I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It ...
0
votes
1answer
58 views

intuitive explanation of sparsity / references

I know it is a vague question, but I am confused by why/when we actually want sparsity of a matrix. For example, interior-point methods work better when constraint matrix is sparse. Similarly, it is ...
0
votes
1answer
23 views

why the optimized point always appear in the interception in LP problem

As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.
0
votes
0answers
89 views

A programming problem requiring mathematical optimization

This is a problem statement in one of the online Judges for programming. I am looking for an algorithm that gives optimized solution, not the best solution. I'm given a set of triplet of balls, each ...
0
votes
1answer
61 views

Terminating condition of Simplex Method - Stronger termination conditon

My textbook states "If there are no negative values in the top row of the Simplex tableau, then we have reached optimality" That seems intuitive enough. However, I am wondering if the following, ...
0
votes
1answer
23 views

Dealing with log functions

I have a function where all variables are linear except for the log function. In one equation I have $\log(x)$ and another equation I have $\log(1-x)$. How can I linearize $\log(x)$ and $\log(1-x)$?
0
votes
2answers
181 views

Project allocation optimisation Code

I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference. ...
-1
votes
2answers
70 views

Linear Programing: Set binary variable 1, if two variables are not equal

I guess I have a simple problem, but I can't find a fitting solution. I have a certain amount periods $D$, and every period is described by the decision variable $X_d$. What I want to do is set a ...
-1
votes
2answers
67 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
-1
votes
1answer
40 views

Reducing data sparsity in linear integer programming

I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix ...
-1
votes
1answer
55 views

Satisfiability of inequality array with binary and arithmetic operators

I have a problem as follows. Really appreciate if anyone can give me some suggestions. I have $4000$ binary variables $\{x_0, x_1,...x_{3999}\}$ and $4000$ inequalities which have both binary ...
-1
votes
1answer
133 views

transforming an absolute value objective function into a linear programming model

I am having a little trouble converting this problem into a linear programming model and how it affects the constraints. max-z = |2x1 - 3x2| s.t. 4x1 + x2 <= 4 2x1 - x2 <= 0.5 x1, x2 >= 0
-1
votes
1answer
55 views

Finding the number of solutions.

$$x_1+x_2+...+x_p+y_1+y_2+...+y_q \ge X$$ where $$x_1,x_2..x_p, y_1,y_2..y_q$$ are all non-negative integers, $$x_1..x_p\le a$$ $$y_1...y_q\le b?$$ The original problem is "You are given $N$ ...
-1
votes
1answer
87 views

Silly question about system of inequalities

I need a confirmation Let's say I have a system of inequalities $$ \left\{ \begin{array}{l} Ax \leq b \\ x \geq 0 \end{array} \right. $$ $A \in \mathbb{R}^{m \times n}$ , $x \in \mathbb{R}^{n \times ...
-1
votes
2answers
104 views

How to solve this question by the two-phase simplex algorithm?

A clever but ethically corrupted mathematics student used to sell assignment solutions to her lazy fellow students. The student, however, learned that she can make much more money by charging the ...
-1
votes
1answer
37 views

Question about simplex method mentioned in A. Schrijver's book

I am reading section 1 of chapter 11 of A. Schrijver's book Theory of Linear and Integer Programming. He frist introduces how to find an optimal solution of LP problem $$\max\{cx|Ax\le b\}$$ if you ...
-1
votes
1answer
2k views

Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

I need to solve the following linear programming minimization problem using the Simplex method: ...
-1
votes
1answer
164 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ |...
-1
votes
1answer
924 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x &...