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

learn more… | top users | synonyms

0
votes
1answer
24 views

Express the constraint “$x = 0$ or $y = 0$” in linear programming

How to express the constraint "$x = 0$ or $y = 0$" in a linear program? Is it possible at all?
0
votes
0answers
17 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...
1
vote
1answer
29 views

Integer programming in MATLAB - all different solutions [on hold]

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in ...
0
votes
0answers
20 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in ...
0
votes
0answers
7 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
0
votes
0answers
6 views

Polyhedral Sets and $min$-function

I'm asked to verify if the following set is polyhedral, $$ X = \{[x_1;x_2]: min(x_1,x_2) \leq 0\}$$ Definition of a polyhedral set, A set $Y$ is polyhedral if $Y = \{y: Ay \leq b\}$, for finite ...
0
votes
0answers
9 views

Matching of points in two discrete linear sequences with potentially missing points

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, ...
1
vote
1answer
47 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + ...
-1
votes
2answers
70 views

Is the area of linear programming dead right now? [on hold]

By dead i mean not much/completely no research there . Is the area of linear programming dead right now? If it is not dead, what are the active area called for example except computer science?
-1
votes
0answers
12 views

Removing variables from convex linear program

I am solving linear program (possibly non-convex). Then we know that dual is always convex. Then I noticed that depending on objective functional I can sometimes remove particular variables from this ...
0
votes
1answer
16 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
0
votes
0answers
9 views

Legal operation to transform a linear program into the canonical form

Good morning! What are the legal operations to transform a linear program into the canonical form? For instance can the following linear program \begin{cases} \begin{array}{col1col2…coln} \max ...
0
votes
0answers
53 views

Intersecting rational polyhedral cones

Call A the cone generated by the rays (1,0,0) and (0,1,0) and B the cone generated by the rays (1,1,0),(1,0,1), and (0,1,1). I want to compute the intersection of these polyhedral cones, but I am ...
0
votes
1answer
44 views

How to configure simplex method to start from a specific point

If I have a linear programming problem e.g. $$\max 2x_1 + x_2$$ with these constraints $$x_1-2x_2 \leq 14$$ $$2x_1-x_2\leq 10$$ $$x_1-x_2 \leq 3$$ And I want to solve the problem starting from a ...
1
vote
1answer
35 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
0
votes
1answer
27 views

Canonical form simplex method

In 2-phases simplex method what kind of operations must be done to get the canonical form tableau? In this step(phase 2 of 2-phases method) after the remotion of artificial variables columns of ...
0
votes
1answer
29 views

set up Linear programming problem

How do I set up this problem ? A product can be made in three sizes, large, medium, and small, which yield a net unit profit of $12, 10$ and $9$ respectively. The company has three centers where ...
0
votes
0answers
29 views

Solving a set of linear equations

I have the following linear equations I need to solve: $$Y=\sum_{n=1}^{N}A_nX_nB_n$$ where Y is m x m $A_n$ are m x $\frac{m}{\sqrt{N}}$ $X_n$ are $\frac{m}{\sqrt{N}}$ x $\frac{m}{\sqrt{N}}$ ...
1
vote
1answer
43 views

Project allocation optimization with tricky constraint

I have an allocation problem that should be straightforward, except that it has very specific constraints. I want to assign approximately 300 students to 170 projects in pairs - so that each project ...
1
vote
1answer
35 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
0
votes
0answers
30 views

Minimum cost linear programming problem formulation

I need to formulate a graph and a linear programming problem, and provide a basic solution for the following problem: A singer who lives in city A wants to plan a tour and end it in city E. The ...
0
votes
1answer
28 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: ...
0
votes
2answers
18 views

What if we get fractional value while finding the numbers of workers in a linear programming problem?

I came across a LP problem in which a factory recruited workers on daily basis giving them wages per day. I don't remember the figures but I remember what was in the question. We had to find the ...
1
vote
1answer
26 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
0
votes
1answer
34 views

Scheduling Optimization Problem - 5 days/week

A 24/7 calling center works as follows: every agent works 5 days in a row and has two days rest, e.g., every week works Tuesday-Saturday and rests on Sunday and Monday. The numbers of agents working ...
0
votes
0answers
24 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
0answers
24 views

On the proof of corner points maximising or minimising a linear function over a bounded convex region

This proof says if $Z_P \ne Z_Q$, then $Z$ is maximised (or minimised, I guess) at one of the endpoints -- of what exactly? $\overline{PQ}$? So the maximum value of $Z$ occurs at either $P$ or $Q$? ...
0
votes
0answers
21 views

Can we relax the assumption of nonnegativity in this proof on convexity of a feasible region in a linear programming problem?

Is the $\color{red}{\text{non-negativity constraint (see red box)}}$ used at all in the proof? If so, where? If not, does the proof then hold for a standard LP problem without the non-negativity ...
0
votes
2answers
32 views

How to describe $\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$

How to describe the set $A$=$\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$ where $x_j^+\ge0$ and $x_j^-\ge0$ The answer says: $B$=$\lbrace ...
0
votes
0answers
13 views

Optimization: second order condition

This is the condition Where $L(x, \mu\,\lambda)$ is the Lagrangian function in a given point that satisfy the first order condition. Problem $ min (-4x -y)$ $ -x^2 -y^2 +1 <= 0 $ $ y- 1 ...
3
votes
1answer
89 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
0
votes
1answer
42 views

Polytopes defined by $x_i >=0, Ax = b$ are generic ? (Understanding simplex method)

Consider polytopes in $R^n$ defined by $x_i >= 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions. The following properties seems to be correct. I would be ...
0
votes
1answer
14 views

About Dual Simplex Method

I have a question about Dual Simplex Method (for minimization problem). While we are solving the method, when we obtain a non-negative $\bar b$, we stop the algortihm. But in addition to $\bar b ...
-1
votes
0answers
11 views

mathematica Linear programming with summation and product

I want to solve Linear programming in mathematica that have summation and products in objective function and in constraints. I ...
0
votes
0answers
24 views

Does this transformation of a problem into a Linear Programing normal form is correct?

An oil refinery produces four types of raw gasoline: alkylaten catalytic, striaght and isopentane. Two important characteristics of each gasoline are its performance number $PN$ and ints vapore ...
0
votes
1answer
21 views

Definition of Optimality test - Simplex method

To clarify, this is not a question about how to conduct test of optimality or about what is the test good for. Nor am I asking for mathematical proof supporting it. I am asking specifically for ...
0
votes
1answer
29 views

Maximise volume given inequality constraint on its dimensions without using Lagrange, KKT or Linear Programming

The problem (from Calculus for Business, Economics, Life Sciences and Social Sciences 12e): I found this and that, but they use Lagrange/KKT. What I tried: Girth $= 2w + 2h$ Maximise ...
0
votes
1answer
17 views

How to find what maximizes the total net profit?

A meat packing plant produces $480$ hams, $400$ pork bellies and $230$ picnic hams every day; each of these products can be either fresh or smoked. The total number of hams, bellies and picnics ...
0
votes
2answers
35 views

Help buying a calculator program [closed]

Is there an economical calculator program I can buy that will let me multiply and divide numbers in the hundreds of digits and show all of the digits?
0
votes
1answer
23 views

Basic and non basic variables in linear programming

I dont understand what are Basic and non basic variables,why we are talking them specially, what they have got to do with the rank of the coefficient matrix and augmented matrix ,and some deal with ...
0
votes
2answers
27 views

Operation Research: system of equations

I have a system of equations for my Operations Research class, and the book is solving them by using algebra. However, I think it would be easier to solve them using linear algebra, and will also ...
0
votes
1answer
16 views

Bounded feasible region condition

Suppose $M=\{x \in \mathbb{R}^n: Ax \ge b\}$ is nonempty and $x_0 \in M$. Prove that $M$ is unbounded, then there exists a vector $d \in \mathbb{R}^n$, such that $x_0+\lambda d \in M,\forall \lambda ...
1
vote
3answers
45 views

How do I graph Linear Programming questions?

So let's say I have the following constraints: $2a + 3b \leq 30$ $a + b \leq 15$ $a \geq 0$ $b \geq 0$ (I just made this problem up, so I'm not sure if it may make any sense when I graph it.) ...
1
vote
3answers
34 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
3
votes
1answer
61 views

Proof of Why Optimal Solutions Occur at Extreme Points

I'm taking my first class in Linear Programming. The book I am reading from is good in that it uses a lot of examples, but bad in that it provides few proofs. I need a proof for the following theorem. ...
0
votes
0answers
16 views

Creation of a cononical form

I wrote during a lecture that the canonical form of linear program was \begin{equation*} \begin{cases} \max C^Tx \\ Ax = b\\ x\ge 0 \end{cases} \end{equation*} But ...
0
votes
2answers
17 views

Constraint Set of Canonical Linear Programming Problem is Convex

I'm reading through my first textbook on linear optimization. The book states a theorem without proof and I'd like to understand why it's true. Glossary of Terms: Definition 1 The problem Maximize ...
2
votes
3answers
27 views

When to use which simplex algorithm?

in linear programming we use simplex method to find optimal solution. But I have also seen methods like Two Phase Method, Dual method, M-method. My question is, how do I know which method to use? For ...