# Tagged Questions

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

47 views

### Linear regression with constrained weights

I have a set of $n$ linear combinations, each with $m$ parameters and desired value $b$. I want to find the set of weights $w$ which minimizes the total equations distances (e.g. the sum of distances ...
15 views

### Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
308 views

### Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
53 views

87 views

### Model logical constraints without binary variables?

Is it possible to express "either $f(x) \leq 0$ or $g(x) \leq 0$" where $f,g$ are linear constraints by using a finite number of continuous constraints/new variables, WITHOUT breaking convexity or ...
57 views

### Combining multiple linear programming to minimize the sum

I have a math problem that looks like a bunch of linear programming problem combined where A matrix is shared. Here is the math definition of my problem Minimize \begin{align} & p_1 (x_{11} + ...
64 views

### Is Linear Programming a Combinatorial optimization method?

I want to know LP can be considered as a Discrete optimization or continuous. The solutions can be fractions so it should be continuous. Please suggest. thanks
58 views

### linear programming slater condition

I am wondering if anyone could help to come up with a such example: ...
295 views

### Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region $(X)$ of a Linear Program can be represented as a convex combination of the extreme points of $X$ plus a non-negative combination of the extreme ...
262 views

### Can number of constraints be less than number of variables in Linear Programming?

In standard form of LP we have $n$ variable and $m$ constraint. In simplex algorithm we set all non-basic variable to zero and at most $m$ basic variable have positive value. if $m < n$, then at ...
371 views

### Nested optimization problems solving using mixed integer linear programming

Let us have two vectors of decision variables, $\mathbf{x}$ and $\mathbf{y}$, two linear objective functions, $F \left( \mathbf{x}, \mathbf{y} \right)$ and $f \left( \mathbf{x} \right)$, and two sets ...
35 views

### Job scheduling to minimise squared completion times using mixed 0-1 quadratic program

I have come across an Optimization question as follows: There are $n$ jobs that have to be processed on a machine. The machine can process only one job at a time. The time taken to process job $i$...
87 views

56 views

### Escaping from a point in linear programming

Is there a trick for explaining the following constraint as a set of linear (in)equalities? $$\sum_{i=1}^n|x_i-a_i|>0,$$ where $a_i$'s are real constants.
62 views

### Algorithm to efficiently compute$A^k$

If a symmetric matrix $A$ has SVD $A=U\Sigma U^{\top}$, then $A^k=U\Sigma^kU^{\top}$. What would be the most efficient algorithm to compute $A^k$ such that the worst case time complexity is as low as ...
42 views

### linear programming problem given initial solution

While dealing with a linear programming problem we usually try to start with the basic feasible solution corresponding to the identity Matrix in the coefficient matrix. I have no idea how to solve the ...
363 views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
17 views

### Polar cones' property [duplicate]

I am trying to prove: $A \subseteq B \implies B^\circ \subseteq A^\circ$ where $A^\circ$ is polar cone of $A$ ($A$ convex cone) and $B^\circ$ is polar cone of $B$ ($B$ convex cone)
61 views

16 views

### Optimizing a set of rules to better predict the outcome of events

I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ...
173 views

### Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
889 views

### Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to Ax \...
494 views

### Can calculus optimization problems be turned into linear programming problems?

I found a Linear Programming textbook somewhere, and I skimmed through the first few pages. While I am not nearly enough ready to go through it, the things it dealt with seemed very much like calculus ...
37 views

### Calculating the distribution between a range without an MILP solver?

I am currently using a MILP calculation and I was wondering if anyone can recommend a more mathematically simplistic method of calculating this distribution and arriving at a similar result? Qty - ...
Suppose that we have the following primal LP: $\min z=c^Tu+d^Tv \\ \mbox{s.t.}\ \ \ \ \ \ \ \ \ u+Av=b, u\geq 0, v\geq 0$ I want to find the dual problem of this LP but I am slightly confused as ...
Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...