Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
5
votes
3answers
80 views

Requiring exactly $n_j$ slots for job $j$ (if scheduled)

Let $x_{j}(t)=1$ iff job $j$ is scheduled at time $t$. I want to say that if the job is scheduled at all, then it is scheduled at $n_j$ slots. I wrote this as: $$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{...
5
votes
1answer
168 views

Column generation for a linear optimization problem

I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
5
votes
3answers
953 views

Solving continuous Minimax Optimization problem

I want to solve a linear programming minimax problem here mathematically without using software: $$\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2,x_3\} \\ \text{s.t.} \...
5
votes
2answers
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 ...
5
votes
3answers
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 ...
5
votes
2answers
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 ...
5
votes
2answers
165 views

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$ where $B^n$ is the set of $n$-dimensional $0-1$ vectors. Its LP relaxation will be $$z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\...
5
votes
1answer
520 views

How can I deal with a possibly undefined constraint?

I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal. $$\min_{\mathbf{d}...
5
votes
1answer
154 views

How to model shipment size constraint?

I am working on an LP problem where I have to model a constraint as: "The total number of units of product A and B should be shipped in multiples of $1200$" e.g. $700\text{(product A)} + 500\text{(...
5
votes
1answer
200 views

How to express this constraint?

I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
5
votes
1answer
150 views

Propagate value through a graph

Here is my question where I am propagating distance through the graph, I was wondering if it is possible to do when the graph has cycles, i.e., traveling the same node multiple time then is it ...
5
votes
2answers
218 views

Formulation of a constraint in a MIP for an element in different Sets

I have an element e $\in E$ with $E$ the set containing all elements e and $e \in Y_i$ with $Y_i \subseteq E$. Each set $Y_i$ has different attributes. $G_j$ is a set of sets and the following holds: $...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 &\...
5
votes
1answer
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.
5
votes
1answer
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
4
votes
3answers
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 ...
4
votes
1answer
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.
4
votes
2answers
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. ...
4
votes
1answer
423 views

Having negative value for non basic variable gives a infeasible solution in simplex method?

I try to solve the following linear program with the simplex method: $$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & &...
4
votes
1answer
93 views

Formulating these logical constraint in an ILP

I have these two constraints : $z \leq My$ $t \leq M'y $ where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers. So basically these ...
4
votes
1answer
76 views

In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?

I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices. I have trouble ...
4
votes
1answer
83 views

How to linearize $f(x,y) = (ax+by)/(x+y)$?

I have a problem which is mainly linear but it has a non-linear component. The objective function is obj = Linear_term + $c*f(x,y)$ where, $f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$. The decision ...
4
votes
1answer
87 views

Analytically finding the maximizer of a trace optimization problem

$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$. I have a ...
4
votes
1answer
80 views

Which method to use to solve this multi-objective conflicting objectives

I have the following multiobjective problem. I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
4
votes
2answers
194 views

Output of binary variable greater than one

I am working on a shipping demurrage problem that uses a binary variable to denote the date a specific vessel can be loaded (I have been kindly helped by Wesley on OR before with this). I am confident ...
4
votes
1answer
240 views

How to set these constraints in a linear optimization problem (PuLP)?

I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both ...
4
votes
1answer
159 views

TSP subtour elimination with multiple formulations

Referring to the question here. Given a set $S$, which we need to travel following TSP rules. I was wondering if this sub tour elimination method is good enough or not? Let $b_{i,j}$ denote edge ...
4
votes
1answer
140 views

TSP on a non-complete graph

I have a non-complete graph $G$ with $V$ vertices and a set $D \subset V$ that needs to be traveled by a vehicle and then return to source at last. Binary variables $b_{i,j}$ represent if the edge $(...
4
votes
1answer
51 views

Strict inclusion for facility location formula and aggregate facility location formula

I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
4
votes
2answers
93 views

Modelling a data-sensitivity scenario as an ILP problem

I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve: When publishing data, it is sometimes important to "suppress" sensitive ...
4
votes
1answer
95 views

Physical Interpretation of a dual of an LP

I was recently asked to physically interpret a dual of an LP for an audience who does not know mathematics/OR (without LP, dual, bounds, etc.). Though I attempted it and was very close to what the ...
4
votes
2answers
151 views

Suggest me good books to learn heuristics to solve Operations Research problems using python

Suggest me some good books with implementation of heuristics using python to solve operations research problems
4
votes
1answer
140 views

How to write quantity discount constraint?

In a simple transportation problem like below image, how to model a constraint for shipment discount e.g. if quantity transported from any origin to any destination is more than 100 unit then the ...
4
votes
1answer
232 views

Transforming a Quadratic constraint to SOCP

I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
4
votes
1answer
337 views

CPLEX Python API

I am trying to run the following optimization problem at Python by using the CPLEX API: $$\min \{x_1 + x_2\ | \ x_1 \geq 3, x_2 \geq 2, 2x_1 + x_2 \geq 9\} $$ I just want to give a matrix of ...
4
votes
1answer
68 views

the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side

Consider a linear programming (LP) problem \begin{align} M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}. \end{align} Suppose the LP is feasible and bounded for all values of $b$. We know that $M(...
4
votes
1answer
117 views

Why is the Lagrange Multiplier not equal the Shadow Price (Excel solver, Matlab linprog, Gurobi)?

I have a LP with equality and inequality constraints. When solving the LP with the excel-solver (GRG Nonlinear) the sensitivity report returns the lagrange multiplier for all constraints. When solving ...
4
votes
1answer
120 views

How to set combined stop condition in AMPL/CPLEX?

I would like to set a stop condition combined of a timelimit and a relative MIP gap. So I would like AMPL/CPLEX to look for the solution of my LP for an hour and if there isn't a solution stop if or ...
4
votes
1answer
74 views

How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver

So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA. A client of mine is looking to solve the following problem. I ...
4
votes
1answer
204 views

PuLP Transport Problem - How to add outcomes of decision variables together

I am working on a rail scheduling problem that moves product from a production plant to a storage facility to satisfy demand. I am new to PuLP so finding this difficult to understand why this isn't ...
4
votes
1answer
253 views

Machine Allocation & optimal Utilization using python

Problem statement: Meet the demand which can be met across 2 facilities each having multiple machines where several components are made. The objective is to find the optimal solution to meet the ...
4
votes
0answers
32 views

Linear functions in Lenstra's algorithm

I had asked this question at MathOverflow and was pointed here. I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
4
votes
0answers
106 views

Does anyone have the criss cross algorithm programming code to solve linear programming problems?

I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...