# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

288 questions
Filter by
Sorted by
Tagged with
80 views

219 views

### Trade off between number of constraints and bounds of a variable

I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver. For fast execution ...
181 views

### Reducing number of suppliers for product portfolio

I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio. What is the best way of finding the solution to "the least suppliers necessary ...
145 views

### Faster implementation of “or” constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
165 views

154 views

247 views

### Can GLPK be used to solve an optimal team selection problem?

My Problem I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows: Given a pool of people, we want to create n teams such to find the optimal ...
52 views

### Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
124 views

### Delayed column generation in Dantzig-Fulkerson-Johnson formulation

In TSP wiki it is said that delayed column generation method is used to solve Dantzig-Fulkerson-Johnson formulation as it has an exponential number of possible constraints. I wanted to know whether it ...
58 views

### Maximizing a Ratio/Percent

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
127 views

### Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...
86 views

### How to linearize difference of absolutes?

How to linearize difference of absolutes? $$|a|\ge k|b|$$ where $a,b$ are variables and $k$ is a constant.
100 views

### Preemptive Goal programming by fixing nonbasic variables with non-zero reduced costs

I have been using the method of fixing nonbasic variables with non-zero reduced costs to do preemptive goal programming. It works for the most part. But I have recently noticed in a certain instance ...
104 views

### Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX

Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
58 views

### Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
93 views

### Construct a direction of recession of the dual that is from growth to dual function

Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
650 views

### Linear programming convexity

Is it possible for a linear programming model to be non-convex ? If it is, please, provide a simple 2 variables example and explain why it is non-convex. EDIT 1: I have been wondering, maybe the ...
837 views

### What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
168 views

### Modeling in integer programming vs modeling in constraint programming

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams). Now I am trying to learn how to model with constraint programming. ...
423 views