Questions tagged [linear-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Performance metric for algorithm with multiple numeric targets

I am constructing an algorithm that predicts the weights of all ingredients in a food product. This is a linear programming algorithm that chooses ingredient weights such that the nutrient profile of ...
0
votes
0answers
3 views

How to specify the number of output variables in step() stepwise selection in R?

I want to find important variables. Thus, I want the step() result to contain 20 variables, but it contains about 40 variables. Can I write some codes to accomplish this?
0
votes
0answers
7 views

Non-linear function optimization using constrOptim()

I wanted to know if choice of starting value affects the output of constrOptim() function (it uses an adaptive barrier algorithm). The problem I noticed was in the following: I have a function f(x1, ...
0
votes
0answers
30 views

Formulate Linear Programming problem from brute force approach

Suppose you have a matrix $a$ where $a_{ij}$ represents whether or not person $i_{1...m}$ likes item $j_{1...n}$. I have two things I'd like to be able to accomplish using linear programming rather ...
0
votes
0answers
15 views

Minimize variance of sum of weights in clusters

Let us assume we have $n$ products, with $w$ weight for each. Group $n$ products in $k$ bags such that the weights of the bags have least variance. Let there be $h$ bags. Let $h^{th}$ bag contain ...
0
votes
0answers
40 views

Formulating a mixed integer programming problem with a binary maximization term

Real-world description of the problem: In the US, funding for school lunch programs is given to local school districts by the Federal government. If >=40% of students in a school or group of schools ...
0
votes
0answers
86 views

Linear programming in R for Data Envelopment Analysis

Suppose I have this dataframe. ...
2
votes
1answer
22 views

An artist published M albums. How to make a selection from the album so that all my N favorite songs are covered, while minimizing my cost?

This is a real life question.. I have a list of N favorite songs from an artist. Out of all M albums from the artist ever published,I want to buy a few albums to cover all of my N favorite songs, but ...
1
vote
0answers
34 views

how to set up an optimization problem to split a group of people into two groups, with several constraints

I am a bit stuck with this problem; I found a temporary (an perhaps suboptimal) solution using Excel, but I'd like to hear your opinion /advice, please. 9 people want to form a group and go on on a ...
8
votes
2answers
1k views

Formulating quantile regression as Linear Programming problem?

How do I formulate quantile regression as a Linear Programming problem? When looking at the median quantile problem I know it is \begin{align} \text{minimize } & \sum_{i=1}^n |\beta_0 + X_i \...
0
votes
1answer
98 views

Assignment Problem (Linear Programming, Genetic Algorithm, etc.)

I'm looking for advice on how I should approach a specific problem. Some background first: The problem is about shipments falling into a bin. There are 19 such bins, which are further sorted into 20 ...
2
votes
0answers
101 views

Linear programming optimization [closed]

I have found through my reading that applying linear programming optimization techniques are substantially more expensive compared to mean squared error-based methods. Could someone please help in ...
0
votes
1answer
59 views

If we “delete” the term of norm in SVR problem formulation, can it be solved with simplex method?

The problem formulation in Support Vector Regression is, What if we don't want to take the "flatness" term, i.e., $\frac 1 2 ||w||^2$ and delete it; can we find solution from simplex method for ...
1
vote
1answer
33 views

lp_solve starting basis

I'm working with some fairly large LP problems in R and running into very slow computation times. I'm using the 'lp_solve' solver R wrapper ( through lpSolve and lpSolveAPI packages ), and found the ...
0
votes
2answers
999 views

How to use equalities as constrains with constrOptim in R

I want to solve a matrix system which have several solutions (infinite since it is overdetermined - 6 equations with 8 unknowns). However, the way I want to do it is to a criterion for the variables, ...
1
vote
0answers
36 views

Converting general form to standard form in linear programming

I am new to linear programming and I am currently trying to convert a general LP problem to standard form. The general form the problem is as follows: I have the following objective function, in ...
0
votes
0answers
35 views

Is there a method to fit a bound to the plot of an linear inequality?

I have a physical dataset that is bounded by several different processes, and thus the plot takes the form of a linear inequality: I'm specifically interested in studying the upper bound. Is there a ...
1
vote
2answers
346 views

Linear programming with variables in piecewise intervals

Problem: I am working on a linear programming problem, i.e. a linear objective function to minimize: $\mathbf{c}\cdot\mathbf{x}$, where $\mathbf{c},\mathbf{x}\in\mathbb{R}^{N}$ Subject to ...
3
votes
0answers
800 views

AIC/BIC for quantile regression

I am working on Quantile Regression (QR) and want to assess models using goodness of fit (GOF) measures. I have come across the post here, here that says, AIC/BIC can be calculated for QR model ...
12
votes
2answers
3k views

How to solve least absolute deviation by simplex method?

Here is the least absolute deviation problem under concerned: $ \underset{\textbf{w}}{\arg\min} L(w)=\sum_{i=1}^{n}|y_{i}-\textbf{w}^T\textbf{x}|$. I know it can be rearranged as LP problem in ...
1
vote
0answers
180 views

Why is Coordinate Descent not used to solve Least Absolute Deviation?

I have recently been looking into why Least Absolute Deviation (LAD) is not used in place of OLS for machine learning, and it appears the primary reason is due to difficulty in computing a solution ...
4
votes
1answer
143 views

Does every gutter point in SVM have positive multiplier?

I understand that SVM is about solving the constrained optimization such that $$\min_{\mathbf{w}} \dfrac{1}{2} \mathbf{w}^T\mathbf{w}$$ subject to $$y_i(\mathbf{w}^T\mathbf{x_i}+b)\geq{1}, i=1, 2, ....
5
votes
1answer
582 views

Is there a measure to describe the degree of linear separability?

I know that given two sets of points, one can use linear programming to see if there is a solution/hyperplane that linearly separates the two data sets. But this holds for completely linearly ...
1
vote
0answers
29 views

Reference for infinite horizon constrained Markov decision process

I am looking for some introductions or reviews material for solving infinite horizon constrained Markov decision process. The book I am reading upon is constrained Markov decision process by Eitan ...
0
votes
1answer
20 views

Binary Stochastic Programming with Independent or Positively Correlated Co-efficients

A manufacturer can select a maximum of $N$ stores to fulfill orders from a total of $M$ stores who are looking for inventory, $N\le M$. The case when $N\geq M$ is trivially solved when all stores ...
1
vote
0answers
52 views

Looking for canonical problems or seminal work it the intersection of constraint programming and statistics

I'm interested in exploring the area (if it exists) at the intersection of constraint programming and statistics. My primary interest is on problems that require a combination of both statistical and ...
1
vote
1answer
101 views

Optimization based on regression result

I am trying to find the optimal values for a given attributes. In particular, my objective is to maximize the profitability based on some parameters. If we call the profitability $p$, and the ...
0
votes
2answers
81 views

How to convert minimize $\| Ax - b \|_\infty$ to an equivalent linear program step by step?

Given this question: $$\text{minimize } \| Ax - b \|_\infty$$ Then this question is equivalent to $\text{minimize } \max |Ax - b|$ = $\text{minimize } \max\limits_i |a_i^Tx - b_i|$ Let $t = |a_i^...
0
votes
1answer
4k views

How to use MATLAB's Linprog to solve LP model of L1 regression

A L1 regression problem is given as: $\min\limits_{a,b} \sum\limits_{i=1}^n |y_i - ax_i - b|$ It has an equivalent LP model: $\min \sum\limits_{i = 1}^n z_i$ $|y_i - ax_i - b| \leq z_i$ where $...
1
vote
1answer
1k views

Linear vs. Quadratic Programming: Complexity and Practical Efficiency

Are quadratic programs harder than linear programs to solve (or vice-versa?) How much harder? I'm interested both in theoretical results and what sort of differences there tend to be in practice.