2
votes
0answers
8 views

Determining maximum number of groups - maybe Linear Programming

Given a set D dogs, C cats, and B birds, for each dog d in D, there is a set c(d) which indicates the set of cats that dog d likes and a set b(d) birds that dog d likes. How do I find the maximum ...
1
vote
0answers
19 views

Optimizing over a set of optimization problems

This is my first time asking an optimization question on here, so I am looking forward to see what will happen here. In the lack of a better title, I wrote it as it is. At a high-level, I can perhaps ...
0
votes
1answer
17 views

making a function non-linear using a Lagrangian function

How Is this formula a Lagrangian function ? And how can a non-linear element be added to a function using this "Lagrangian function" This is where i got this In order to improve the performance ...
1
vote
0answers
18 views

Linear Programming, Optimal Solutions

I posted the whole question to give some context, but my problem lies with (iv). I think you're meant to use a formula for the generalization of the optimal solution, but I'm not really sure what ...
0
votes
0answers
17 views

Linear programming to find minimal additive and multiplicative factors

Consider samples $\{x_i,y_i\}$ with $x_i\in\mathbb{R}^N$ and $y_i=\pm1$ and additional $z\in\mathbb{R}^N$. Can one use linear programming to find the minimal $m>0$ and minimal $\epsilon>0$ (e.g. ...
0
votes
0answers
70 views

maximization function of a matrix given a scoring system

This is, from a mathematics standpoint, trivially solvable, but my goal is to solve it with the fewest number of comparisons. I'm hoping to discover that this problem is identical to something in ...
0
votes
0answers
21 views

Minimise a cost of elements into given length - Optimisation - Linear programming

I've been researching optimisation methods used to minimise the cost of elements that could be used in a given length. Here is an example of my problem : For a given length 40 : X1 Length l1 = 13 ...
0
votes
1answer
19 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
18 views

Statistical Meaning of LP problem

What is the statistical interpretation of this LP problem for different values of $\mu$? $\min \sum_{j} \left( |x-b_j| + \mu (x-b_j) \right)$ I know that $\min \sum_{j} |x-b_j|$ is the median but ...
2
votes
0answers
36 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
1
vote
1answer
34 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
0
votes
0answers
45 views

Application of the Simplex Method using Gauss-Jordan to solve Transportation Minimization Problem

I am attempting to implement the Simplex method using Gauss-Jordan elimination to solve the transportation problem. This is a minimisation problem, whereby I want to starting from a feasible solution ...
0
votes
1answer
29 views

Can the search space of a solvable linear optimization problem be discontinuous?

Background Say you have a traditional linear-optimization problem, there is a linear cost function, $\vec{c}\cdot\vec{x}$ and a set of linear constraints, $A_1\vec{x} \geq b_1 $ $A_2\vec{x} \leq ...
1
vote
0answers
25 views

Maximize minimum optimization using linear integer programming

I am trying to solve a maximize minimum optimization. I have four different items that each of them has 10 values of Rates and for each value it has a corresponding weight. Then I have a free table ...
0
votes
3answers
52 views

Linear Programming and differentiation, why can't we differentiate to find the optimum solution?

I do understand that differentiating a linear function (for a maximization) subject to some linear restriction (such as the problem $p=ax+by$ s.t. $cx+dy \leq m$) won't necessarily give me the right ...
0
votes
0answers
31 views

Linear programming with quadratic constraints

I want to solve a problem of this form: $max_{y,k} \,\,\, w^\top y + C 1^\top k$ s.t. $k y^\top B^\top = I $ $A^\top y \geq b$ is there an algorithm that can solve such a problem? Is there an ...
3
votes
2answers
47 views

Can a non-extreme point be an optimal solution of a Linear Programming problem?

Consider a linear programming problem. Is it possible for an optimal solution to exist, but not at an extreme point? According to Bertsimas & Tsitsikalis ("Introduction to Linear Optimization", ...
1
vote
1answer
27 views

Big M constraint question

I have a question regarding using Big M constraints to solve the following problem: Given: $a, b \ge 0$ and integers. $$2a + 5b \le 17\\ a + b \le 5\\ 3a + 6b \le 20$$ For at least two of the ...
1
vote
1answer
38 views

Finding $\max_{||x||_2=1} \min_i |(Ax)_i|$

Let us define for $x \in \mathbb{R}^n$ $$M(x)=\min_i|x_i|$$ Is there a way to solve the following optimization problem: $$\max_{||x||_2=1}M(Ax)$$ for a given $A$?
2
votes
1answer
39 views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
0
votes
0answers
18 views

Finding equivalent minimization problem

I am having some trouble while implementing the minimization problem of a paper. My goal is to minimize the following: $\epsilon_L = \epsilon_1 + \lambda \epsilon_2$ where: $\epsilon_1 = \sum_i ...
0
votes
0answers
20 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in ...
2
votes
0answers
22 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
0
votes
1answer
47 views

Minimized sum of the distances with street distance

This exercise comes from Bazaraa Linear Programming and Network Flows book : Consider the problem of locating a new machine to an existing layout consisting of four machines. These machines are ...
0
votes
0answers
15 views

Generalization of size reduction of Linear Assignment Problems

It is well known, that the LAP has super linear complexity. Hence, problem-size reduction is a viable optimization strategy. For instance, if one task is incident to exactly two workers, one can ...
0
votes
0answers
9 views

way to find angle of objective function and constraint in lp

I want to find the angle between objective function plane and hyperplane in LP problem . For example , let I have the following LP problem: $ \text{minimize } 10x_1-57x_2-9x_3-24x_4 $ $$\\$$ $ ...
1
vote
1answer
55 views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
1
vote
1answer
33 views

Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes. Basically, I have a directed graph of $N$ nodes where I know the following: The sum of the weights of the ...
2
votes
1answer
57 views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
2
votes
1answer
31 views

Linear Programming - Handling $\max(x,0)$ in the objective function

Hello I have to solve the following problem $\min_P (\max (K_1+P,0)+ K_2 P)$, s.t. $P \in \mathcal{P}$. Is there a any trick to convert the $\max(\bullet,0)$ and convert it into a linear programming ...
1
vote
1answer
69 views

Is finding the maximum of a polynomial of degree one a linear programming problem?

Is the following problem expressible as a linear program \begin{align} \textbf{P1} \\ \mathrm{maximize} \; \; \; &\left[\left(a_1x+a_2y,b_1x+b_2y\right)_+ - \left(c_1x+c_2y\right)\right]_+ - ...
0
votes
1answer
68 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 ...
1
vote
1answer
46 views

Maximization of a function defined with $\max$

Define the function $$ f(a,b,c,\alpha,\beta,\gamma,x) = \max\!\bigg(0 , \, \max\!\big( \left(a+x\right)\alpha,\left(b+x\right)\beta \big) - \left(c+x\right)\gamma\bigg), $$ where $$ a,b,c,\alpha, ...
1
vote
1answer
32 views

Is there a name for this type of optimization problem?

I want to optimize a linear function of $(x_{1}, x_{2})$ subject to constraints that look like $1(x_{2} \geq x_{1})(b_{1}x_{1} + b_{2}x_{2}) \geq 0$ $1(x_{2} \leq x_{1})(b_{1}x_{1} + ...
2
votes
1answer
117 views

Previous table of simplex algorithm

I have this problem of simplex method which shows cycle . Problem : Maximize $Z=10x_1-57x_2-9x_3-24x_4$ Constraint to : $ 0.5x_1-5.5x_2-2.5x_3+9x_4<=0 $, $ ...
1
vote
0answers
21 views

Highest (lowest) index of positive time-indexed variable

I have a simple problem involving a variable $x_{it}$ representing the amount of a resource allotted to a task $i$ in time $t$. The quantity of the (renewable) resource is constrained at a value $R$ ...
1
vote
0answers
76 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
5
votes
1answer
117 views

Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question. I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have ...
1
vote
1answer
34 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
1
vote
1answer
78 views

Maximize $ax + by + c$

Working on a problem of comparative advantage of the economist David Ricardo, I've gone into solving a more general case of that study in which I stumbled over this question : how do we maximize the ...
1
vote
1answer
43 views

Fitting Vogner's formula for phyllotaxis to an actual plant.

A simple model for the arrangement of florets in a sunflower was given by Vogel: $r = c\sqrt{n}$ $\theta = 137.508 n$ Where $r$ and $\theta$ are polar coordinates, $c$ is some constant and $n$ is ...
4
votes
0answers
51 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
1
vote
1answer
63 views

First-order necessary condition for relative minimum point

I'm studying linear and nonlinear programming and I came across with the following proposition : given $\rm x\in\Omega$ we are motivated to say that a vector $\mathbf d$ is a feasible direction at ...
5
votes
2answers
136 views

Almost a linear program. How to solve efficiently?

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP. $$ ...
0
votes
1answer
74 views

Are my linear program equations correct?

Here's the problem: "An electronics company has a contract to deliver 21,475 radios within the next four weeks. The client is willing to pay 20 dollars for each radio delivered by the end of the first ...
1
vote
0answers
132 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
0answers
73 views

Application of Farkas' Lemma

Suppose matrices $A_{p\times n}$ and $B_{q\times n}$. Use Farkas' Lemma to prove that one and only one of below systems has solution: $$(1)\qquad AX<0,\quad BX = 0, \quad X\in\mathbb{R}^{n} $$ ...
0
votes
0answers
29 views

Finding dual LP of a graph optimization problem

This is homework, so please no full solutions. I really am stuck at only one small place. So, this is a graph thingy with a bipartite graph with bipartition $L,R$. Each vertex has a "requirement" ...
0
votes
0answers
24 views

Finding dual of incredibly complex LP; any trick?

This is homework, so only hints please. This is about a LP relaxation of the minimum cost perfect matching problem, with another constraint that shrinks the solution space in a way that a lot of ...
1
vote
0answers
53 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!