11. Primal feasibility repair


Section 10.2.2 discusses how MOSEK treats infeasible problems. In particular, it is discussed which information MOSEK returns when a problem is infeasible and how this information can be used to pinpoint the elements causing the infeasibility.

In this section we will discuss a method for repairing a primal infeasible problem by relaxing the constraints in a controlled way. For the sake of simplicity we discuss the method in the context of linear optimization. MOSEK can also repair infeasibilities in quadratic and conic optimization problems possibly having integer constrained variables. Please note that infeasibilities in nonlinear optimization problems can't be repaired using the method described below.

11.1. The main idea

Consider the linear optimization problem with m constraints and n variables

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x+c^{f} &  & \\\nonumber{}\mbox{subject to} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x & \leq{} & u^{x},\end{array}\end{math} (11.1.1)

which we assume is infeasible. Moreover, we assume that

\begin{math}\nonumber{}(l^{c})_{i}\leq{}(u^{c})_{i},~\forall i\end{math} (11.1.2)

and

\begin{math}\nonumber{}(l^{x})_{j}\leq{}(u^{x})_{j},~\forall j\end{math} (11.1.3)

because otherwise the problem (11.1.1) is trivially infeasible.

One way of making the problem feasible is to reduce the lower bounds and increase the upper bounds. If the change is sufficiently large the problem becomes feasible.

One obvious question is: What is the smallest change to the bounds that will make the problem feasible?

We associate a weight with each bound:

Now, the problem

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & p &  & \\\nonumber{}\mbox{subject to} & l^{c} & \leq{} & Ax+v_{l}^{c}-v_{u}^{c} & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x+v_{l}^{x}-v_{u}^{x} & \leq{} & u^{x},\\\nonumber{} &  &  & (w_{l}^{c})^{T}v_{l}^{c}+(w_{u}^{c})^{T}v_{u}^{c}+(w_{l}^{x})^{T}v_{l}^{x}+(w_{u}^{x})^{T}v_{u}^{x}-p & \leq{} & 0,\\\nonumber{} &  &  & v_{l}^{c},v_{u}^{c},v_{l}^{x},v_{u}^{x}\geq{}0 &  &\end{array}\end{math} (11.1.4)

minimizes the weighted sum of changes to the bounds that makes the problem feasible. The variables [[MathCmd 503]], [[MathCmd 504]], [[MathCmd 505]] and [[MathCmd 504]] are elasticity variables because they allow a constraint to be violated and hence add some elasticity to the problem. For instance, the elasticity variable [[MathCmd 503]] shows how much the lower bound [[MathCmd 508]] should be relaxed to make the problem feasible. Since p is minimized and

\begin{math}\nonumber{}(w_{l}^{c})^{T}v_{l}^{c}+(w_{u}^{c})^{T}v_{u}^{c}+(w_{l}^{x})^{T}v_{l}^{x}+(w_{u}^{x})^{T}v_{u}^{x}-p\leq{}0,\end{math} (11.1.5)

a large [[MathCmd 510]] tends to imply that the elasticity variable [[MathCmd 503]] will be small in an optimal solution.

The reader may want to verify that the problem (11.1.4) is always feasible given the assumptions (11.1.2) and (11.1.3).

Please note that if a weight is negative then the resulting problem (11.1.4) is unbounded.

The weights [[MathCmd 512]], [[MathCmd 513]], [[MathCmd 514]], and [[MathCmd 515]] can be regarded as a costs (penalties) for violating the associated constraints. Thus a higher weight implies that higher priority is given to the satisfaction of the associated constraint.

The main idea can now be presented as follows. If you have an infeasible problem, then form the problem (11.1.4) and optimize it. Next inspect the optimal solution [[MathCmd 516]], and [[MathCmd 517]] to problem (11.1.4). This solution provides a suggested relaxation of the bounds that will make the problem feasible.

Assume that [[MathCmd 518]] is an optimal objective value to (11.1.4). An extension of the idea presented above is to solve the problem

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x &  & \\\nonumber{}\mbox{subject to} & l^{c} & \leq{} & Ax+v_{l}^{c}-v_{u}^{c} & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x+v_{l}^{x}-v_{u}^{x} & \leq{} & u^{x},\\\nonumber{} &  &  & (w_{l}^{c})^{T}v_{l}^{c}+(w_{u}^{c})^{T}v_{u}^{c}+(w_{l}^{x})^{T}v_{l}^{x}+(w_{u}^{x})^{T}v_{u}^{x}-p & \leq{} & 0,\\\nonumber{} &  &  & p & = & p^{*},\\\nonumber{} &  &  & v_{l}^{c},v_{u}^{c},v_{l}^{x},v_{u}^{x}\geq{}0 &  &\end{array}\end{math} (11.1.6)

which minimizes the true objective while making sure that total weighted violations of the bounds is minimal, i.e. equals to [[MathCmd 518]].

11.2. Feasibility repair in MOSEK

MOSEK includes functionality that help you construct the problem (11.1.4) simply by passing a set of weights to MOSEK. This can be used for linear, quadratic, and conic optimization problems, possibly having integer constrained variables.

11.2.1. Usage of negative weights

As the problem (11.1.4) is presented it does not make sense to use negative weights since that makes the problem unbounded. Therefore, if the value of a weight is negative MOSEK fixes the associated elasticity variable to zero, e.g. if

\begin{displaymath}\nonumber{}(w_{l}^{c})_{i}<0\end{displaymath}

then MOSEK imposes the bound

\begin{displaymath}\nonumber{}(v_{l}^{c})_{i}\leq{}0.\end{displaymath}

This implies that the lower bound on the ith constraint will not be violated. (Clearly, this could also imply that the problem is infeasible so negative weight should be used with care). Associating a negative weights with a constraint tells MOSEK that the constraint should not be relaxed.

11.2.2. Automatical naming

MOSEK can automatically create a new problem of the form (11.1.4) starting from an existing problem by adding the elasticity variables and the extra constraints. Specificly, the variables [[MathCmd 523]], [[MathCmd 524]], [[MathCmd 525]], [[MathCmd 526]], and p are appended to existing variable vector x in their natural order. Moreover, the constraint (11.1.5) is appended to the constraints.

The new variables and constraints are automatically given names as follows:

  • The names of the variables [[MathCmd 503]] and [[MathCmd 504]] are constructed from the name of the ith constraint. For instance, if the 9th original constraint is named c9, then by default [[MathCmd 529]] and [[MathCmd 530]] are given the names LO*c9 and UP*c9 respectively. If necessary, the character “*” can be replaced by a different string by changing the
    Env.sparam.feasrepair_name_separator
    parameter.
  • The additional constraints

    \begin{displaymath}\nonumber{}l^{x}\leq{}x+v_{l}^{x}-v_{u}^{x}\leq{}u^{x}\end{displaymath}

    are given names as follows. There is exactly one constraint per variable in the original problem, and thus the ith of these constraints is named after the ith variable in the original problem. For instance, if the first original variable is named “x0”, then the first of the above constraints is named “MSK-x1”. If necessary, the prefix “MSK-” can be replaced by a different string by changing the
    Env.sparam.feasrepair_name_prefix
    parameter.

  • The variable p is by default given the name WSUMVIOLVAR, and the constraint (11.1.5) is given the name WSUMVIOLCON.

    The substring “WSUMVIOL” can be replaced by a different string by changing the
    Env.sparam.feasrepair_name_wsumviol
    parameter.

11.2.3. Feasibility repair using the API

The Task.relaxprimal function takes an existing problem as input and creates a new task containing the problem (11.1.4). Moreover, if requested this function can solve the problems (11.1.4) and (11.1.6) automatically.

The parameter Env.iparam.feasrepair_optimize controls which problem is solved. Its value is used as follows:

For further details, please see the description of the function Task.relaxprimal in the reference.

11.2.4. An example

Consider this example of linear optimization

\begin{math}\nonumber{}\begin{array}{lccccc}\nonumber{}\mbox{minimize} & -10x_{1} &  & -9x_{2}, &  & \\\nonumber{}\mbox{subject to} & 7/10x_{1} & + & 1x_{2} & \leq{} & 630,\\\nonumber{} & 1/2x_{1} & + & 5/6x_{2} & \leq{} & 600,\\\nonumber{} & 1x_{1} & + & 2/3x_{2} & \leq{} & 708,\\\nonumber{} & 1/10x_{1} & + & 1/4x_{2} & \leq{} & 135,\\\nonumber{} & x_{1}, &  & x_{2} & \geq{} & 0.\\\nonumber{} &  & x_{2}\geq{}650 &  &  &\end{array}\end{math} (11.2.1)

This is an infeasible problem. Suppose that we want MOSEK to suggest a modification to the bounds such that the problem becomes feasible. The following example performs this task:

package feasrepairex1; /* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: feasrepairex1.java Purpose: To demonstrate how to use the MSK_relaxprimal function to locate the cause of an infeasibility. Syntax: On command line java feasrepairex1.feasrepairex1 feasrepair.lp feasrepair.lp is located in mosek\<version>\tools\examples. */ import mosek.*; class msgclass extends mosek.Stream { public msgclass () { super (); } public void stream (String msg) { System.out.print (msg); } } public class feasrepairex1 { public static void main (String[] args) { mosek.Env env = null; mosek.Task task = null; mosek.TaskContainer task_relaxprimal_container = new mosek.TaskContainer(); mosek.Task task_relaxprimal = null; double[] wlc = {1.0,1.0,1.0,1.0}; double[] wuc = {1.0,1.0,1.0,1.0}; double[] wlx = {1.0,1.0}; double[] wux = {1.0,1.0}; double[] sum_violation = new double[1]; // Since the value infinity is never used, we define // 'infinity' symbolic purposes only double infinity = 0; try { // Make mosek environment. env = new mosek.Env (); // Direct the env log stream to the user specified // method env_msg_obj.print msgclass env_msg_obj = new msgclass (); env.set_Stream ( mosek.Env.streamtype.log,env_msg_obj); // Initialize the environment. env.init (); // Create a task object linked with the environment env. task = new mosek.Task (env, 0, 0); // Directs the log task stream to the user specified // method task_msg_obj.print msgclass task_msg_obj = new msgclass (); task.set_Stream (mosek.Env.streamtype.log,task_msg_obj); /* read file from current dir */ task.readdata(args[0]); task.putintparam(mosek.Env.iparam.feasrepair_optimize, mosek.Env.feasrepairtype.optimize_penalty.value); System.out.println ("Start relax primal"); task_relaxprimal = task.relaxprimal(wlc, wuc, wlx, wux); System.out.println ("End relax primal"); task_relaxprimal.getprimalobj(mosek.Env.soltype.bas, sum_violation); System.out.println ("Minimized sum of violations = " + sum_violation[0]); /* modified bound returned in wlc,wuc,wlx,wux */ for (int i=0;i<4;++i) { if (wlc[i] == -infinity) System.out.println("lbc[" + i + "] = -inf, "); else System.out.println("lbc[" + i + "] = " + wlc[i]); if (wuc[i] == infinity) System.out.println("ubc[" + i + "] = inf"); else System.out.println("ubc[" + i + "] = " + wuc[i]); } for (int i=0;i<2;++i) { if (wlx[i] == -infinity) System.out.println("lbx[" + i + "] = -inf"); else System.out.println("lbx[" + i + "] = " + wlx[i]); if (wux[i] == infinity) System.out.println("ubx[" + i + "] = inf"); else System.out.println("ubx[" + i + "] = " + wux[i]); } } catch (mosek.ArrayLengthException e) { System.out.println ("Error: An array was too short"); System.out.println (e.toString ()); } catch (mosek.Exception e) /* Catch both mosek.Error and mosek.Warning */ { System.out.println ("An error or warning was encountered"); System.out.println (e.getMessage ()); } if (task != null) task.dispose (); if (task_relaxprimal != null) task_relaxprimal.dispose (); if (env != null) env.dispose (); } }

The output from the program above is:

Minimized sum of violations = 4.250000e+01
lbc[0] = -inf, ubc[0] = 6.300000e+02
lbc[1] = -inf, ubc[1] = 6.000000e+02
lbc[2] = -inf, ubc[2] = 7.080000e+02
lbc[3] = -inf, ubc[3] = 1.575000e+02
lbx[0] = 0.000000e+00, ubx[0] = inf
lbx[1] = 6.300000e+02, ubx[1] = inf

To make the problem feasible it is suggested increasing the upper bound on the activity of the fourth constraint from 134 to 157.5 and decreasing the lower bound on the variable [[MathCmd 73]] to 630.

Wed Feb 29 16:00:43 2012